texts: Covering numbers to show that H is agnostically PAC-learnable

texts:
Suppose $X=[0,1]$ and $Y=[0,1]$, and we use the squared loss

Let's define the hypothesis class $H = {h(x) = (x-a)^2 : a \in [0,1]}$.

Question: How can covering numbers be used to show that this class is agnostically PAC-learnable, and prove an upper bound on $|L_S(h) - L_D(h)|$, which holds simultaneously for all $h\in H$ with probability at least $1 - \delta$.

I'm not sure how covering numbers can be used here, any ideas are appreciated.

Looks like this can be used to prove the upper bound: https://en.wikipedia.org/wiki/Covering_number#Application_to_machine_learning


texts: f(n) and g(n) are monotonically increasing functions. h(n) = max(f,g) => h = O(f) or h = O(g)?

texts:
All functions are from naturals to naturals.

Let f(n) and g(n) be monotonically increasing functions. prove or disprove
h(n) = max(f(n),g(n))  =>  h = O(f) or h = O(g)

I've found close questions regarding max(f,g) being O(f+g) but I couldn't derive anything from them regarding my specific problem. Needless to say, I'm new to algorithms and data structures.

any explanations, solutions would be great :)


texts: Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints

texts:
This is a homework problem for a class that ended 2 years ago, I'm learning it by myself.

Consider a directed graph $D=(V,A)$, $s,t\in V$. $A=\{a_1,\ldots,a_n\}$. Let $P=\{p_1,\ldots,p_m\}$ be the set of all simple paths from $s$ to $t$, There is a capacity function $c:A\to \mathbb{R}^+$. First we are asked to express max s-t flow as a linear program letting each path $p_j$ in $P$ associated with the variable $x_j$, there could be a exponential number of variables.

The formulation,
$$
\begin{align}
\text{Maximize:} & \sum_{j}x_j\\
\text{subject to:} & \sum_{a_i \in p_j}{x_j} \leq c(a_i) &\text{ for } 1 \le i \le n, \\
& x_j\geq 0 &\text{ for } 1 \leq j \leq m\\
\end{align}
$$

The dual is therefore:
$$
\begin{align}
\text{Minimize:} & \sum_{i} c(a_i) y_i\\
\text{subject to:} & \sum_{a_i\in p_j} y_i \geq 1 &\text{ for } 1 \le j \le m, \\
& y_i\geq 0 &\text{ for } 1 \leq i \leq n\\
\end{align}
$$

Assuming we have an optimal solution for the dual, the problem ask us to use complementary slackness to show there exist a formulation of the primal with only a polynomial number of paths, which also obtain an optimal solution. How is this done?


texts: Exactly how many clocks does a Computer consists of and how do they synchronize with each other?

texts:
I am currently trying to understand how Computers are arranged and organized internally (so that I can learn Assembly Language) through an online book called The Art of Assembly by Randall Hyde. Irrespective of whether or not I'll learn Assembly, I'm finding it difficult to understand exactly how is everything synchronized in the Computer. I'm currently at 3.2 - System Timing topic.

Below are my observations and the things I currently understand not only from the book but also from the things I learned through understanding computers in general.

Reading the book, I've came to understand that there are atleast 2 clocks in the whole system. One is the System Clock which makes one of the lines within the Control Bus go HIGH and LOW periodically. The CPU also has it's own Internal Clock which controls the operations which are done by the CPU. Now the Internal Clock should be in sync with the System Clock for the whole system to make sense which means the control line (which oscillates between low and high) should be connected to the CPU so that both the clock combine and act like a single clock. But then this happened:

The above snippet is from the PDF version of the same book.

I still didn't get confused after reading this. I perfectly understood that the Internal Clock just runs twice as fast as the System Clock which is fine. My confusion came when the Author mentioned the words "On a 5 MHz 8088/8086 CPU the memory access time..." and "On a 50 MHz 80486, the memory access time...". The question is, 'How can CPUs have their clocks running at certain frequencies when their Clock depends on the System Clock?'. 'Shouldn't their Internal Clock run at a certain multiple of the System Clock?'. I've also came across overclocking the CPU and stuff. 'Won't that make the Internal Clock of the CPU go out of Sync with the System Clock?'

Perhaps the main problem in understanding how everything is synchronized in Computer is the understanding of the word 'synchronized'. And also, 'How many clocks are there in the Computer as a whole?'. Because "Zafaria Kansa" says on the following link on Quora that there are 'Internal' and 'External' Clocks on the CPU: https://www.quora.com/What-does-GHz-mean-How-does-it-relate-to-processor-speed (I don't have enough reputation to post more than two links). Does she mean 'System Clock' when she said 'External Clock'? How does everything fit together?


texts: How to find the length of maximum subarray sum in segment tree query?

texts:
Problem: Given an array with size$\ n  $: for each$\ a[i] $, it denotes the value of the house. You are given the task to build the wall that saves the house that is not exceed$\ w $ length. What is the maximum value you can save?

Constraint:

$\ 1<=n<=6,000,000 $;

$\ -500,000<=a[i]<=500,000  $;

$\ 1<=w<=100,000  $;

For instance: n = 7, w = 3

3 2 5 1 4 -7 10

So the maximum value will be 10 and the maximum size will be
1 (10) or 3 (5 1 4).

but the answer must be the minimum of length if there are more than one possible answers.

So the length will be 1.

Is there anyway to achieve this using segment tree?

I have tried: Maximum subsegment sum using the prefix and suffix sum. But I cannot find the length.


texts:
Classically, there are 3 popular ways to think about computation: Turing machine, circuits, and lambda-calculus (I use this as a catch all for most functional views). All 3 have been fruitful ways to think about different types of problems, and different fields use different formulation for this reason.
When I work with quantum computing, however, I only ever think about the circuit model. Originally, QC was defined in terms of quantum Turing machines but as far as I understand, this definition (although equivalent to quantum circuits if both are formulated carefully) has not been nearly as fruitful. The 3rd formulation (in terms of lambda-calculus or similar functional settings) I am completely unfamiliar with. Hence my questions:

What are useful definitions of quantum lambda-calculus (or other functional paradigms)?

What subfields of QIP gain deeper insight from using this formulation instead of the circuit model?

Notes
I am aware that I am ignoring many other popular formalisms like cellular automata, RAM-models, etc. I exclude these mostly because I don't have experience with thinking in terms of these models classically, let alone quantumly.
I am also aware that there are popular alternatives in the quantum setting, such as measurement-based, topological, and adiabatic. I do not discuss them because I am not familiar with the classical counterparts.


texts: Is it possible to implement a dictionary with efficient access according to insertion order?

texts:
I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the indices in which keys and values were put in, like arraylists do but in a complexity of $O(\log n)$ or less.

I tried to work around a solution to this problem and created various TreeMaps that has Integer indices and values and vice-versa, and the same with keys.

Just to make it more clear, the indices symbolize the insertion order from the user. So if I had 3 elements then their index values are 0, 1, 2 and if element 0 was deleted then I need to push 1 to 0 and 2 to 1 and a new element would be added with index 2.

My problem is when I remove a key and its value, if I want to insert the next key and value in the right index I have to make sure all the old ones were set back by 1. I don't know how to do it and not to fall into $O(n)$ complexity.

My goal is to use existing data structures and mix them to get this result, please take a look at the methods I implemented as I need those.

What I am asking is how can I create a data structure for keys and values that has the put, remove, get, getValueByIndex, getKeyByIndex, getIndexByKey methods in it while each method takes $O(\log n)$ or less and the indices change at each deletion.

Is it possible? And if so what is the mixture of Data-structures to create this?


texts: How can I find matchings in a Bipartite graph beginning with specific vertices?

texts:
Context: I'm modelling kidney exchanges through directed acyclic graphs. I convert these to Bipartite graphs (by splitting each node into a donor and receiver, and the edge from the original graph exist between corresponding donors and receivers). I want a way to find maximum number of edges through disjoint chains and I've been trying to do so through maximum wtd matching.

I know I can use ford-fulkerson to find a maximum wtd perfect matching, however, the main problem I'm facing is that the matchings can only exist for chains beginning with specific vertices. For example, if this is my directed acyclic graph:

Turning this into a Bipartite graph and using the maximum wtd matching way, I get the chain 0->1->3->5->6 but I also get 2->4. However, I can only have chains beginning with 0 so 2->4 should not come up.

I wanted to know if there were any ways to work around this problem? Someone suggested making this a minimum cost perfect matching problem but I'm confused how.

I realise this is a weird question but any help would be appreciated!


texts:
I'm trying to implement an Hopfield Network for pictures of 32x32 bits either 1 or -1;

I have these 3 pictures and I transform each of them in a vector of 1024 elements.
Then I take the 3 vectors and I build a matrix M:

U = [v1 v2 v3]

So I compute:

M = (U*U')/1024

where M is a matrix of 1024*1024 elements and I set the diagonal to 0.
in order to get the correlation matrix scaled by 1024 (Hebbian rule).

Now, theoretically each vector v should be a fixpoint. So I compute M*v. I take the sign and I compare with v. The problem is that they are different, so v is not a fixpoint. What am I doing wrong?


texts: Given a set of irregular polygons finding a set of vertices (one on each polygon) such that distance between points is maximized

texts:
Given a set of irregular polygons with the same number of points, where $polygon_i$ is completely contained within the boundary of $polygon_{(i+1)} $.

I need to find a set of vertices (one vertex from each polygon) such that the pairwise distances between all of the points selected are maximized.

What kind of algorithm should I be looking at to solve this problem? The practical use case of this would be a case with 4-8 polygons with roughly 1000-3000 vertices each, I am looking for an approach that could work under these parameters, but am also interested in the classification of this problem from a theoretical perspective.

It seems like this is case of treating each point as the center of circle that is a member of an independent set in a geometric intersection graph, and then moving the points along the polygon boundary that they lie on such that the radius is maximized while keeping the set independant.

Potential Simplifications here are:

Each polygon has the same number of vertices.
All vertices of $polygon_i$ are contained entirely within the area of $polygon_{(i+1)} $
All polygons lie on the same 2D plane.


texts: Partition into pairs with minimum absolute difference, NP-hard?

texts:
I have a set $S$ of an even number of positive elements $2m$ and $m$ values $t_1,t_2,\ldots,t_m$ where each $t_i\leq1$ for all $i$.

The question is: can you select $m$ disjoint pairs $(a_i,b_i)$ from $S$ such that $|a_i-b_i|\geq t_i$?

I was trying to prove that this problem is NP-hard by a reduction from 3-Partition Problem. I failed because if I choose the numbers as in 3-partition I cannot guarantee that their absolute difference is at least $t_i$.

Do you have any hints?


texts: Algorithm for estimating lossless compression factor

texts:
Is there any algorithm for estimating how well certain array of bytes could be compressed in lossless manner?

Usage for me is to automatically choose "best" data reorder method without knowing what compression method end user is going to use. I don't need perfect/optimal result, I just need some kind of numerical result that I can use to compare different permutation runs.

For example string "AAAABBBBCCCCDDDD" should compress better than "ABDABBABCDCCDACD" but if I use e.g. Shannon Entropy for estimation then I get identical results.


texts:
I'm trying to figure out the complexity of the following algorithm.

for(int i=1; i <= N; i++)
        for(int j=1; j <= i; j++)
            for(int k=1; k <= i*sqrt(j); k++)

I'm trying to figure it out using a method similar to rizwanhudda's solution in this similar question. I'm having some trouble though because the innermost loop references both i and j. Can somebody translate this problem into something similar to rizwanhudda's approach (ie count the number of triplets (i, j, k))? Thanks!


texts:
I was wondering how do I solve this, I've been trying any possible way to but I've failed:
$$\begin{align*} T(n) &= T(n-1) +3n^2 - 2n +1 ,& n \ge 1 \\
T(0) &=2 &\\
\end{align*}$$


texts: Any algorithm polynomial time with infinite space?

texts:
If I had an arbitrary amount of space at my disposal, couldn't I vectorize/parallelize any program in such a way that it would only need one step? For example, I could let my CPU have an inbuilt look-up-table for the function (x+y)/z with 3 input values instead of doing the calculation in 2 steps.
Does there exist any proof that something like that isn't possible?


texts: How does the TLB identify a particular process?

texts: I have read that the translation lookaside buffer (TLB) is implemented in hardware and stores the page numbers and the corresponding frame numbers for faster lookups. Now suppose there are two processes, A and B. Page 2 is mapped to a particular frame number. Now if we are searching for page 2 in the TLB, it can belong to either process A or Process B. So how will the TLB determine which process the page belongs to? Or it is flushed each time a new process is brought into running state? Also, what mechanism is used in TLB lookup?


texts: Is graph search of shortest (optimal) path an instance of optimisation?

texts:
I am familiar with mathematical (gradient-based) optimisation methods, some heuristic methods like GAs or linear programming methods like simplex algorithm.
I am not too familiar with graphs / trees and their search.
But it does seem like all possible solutions can be represented as a graph and a graph search algorithm can then be used to explore the space and determine the "shortest" (or could be some other criterion) path. It seems that this is what Breadth First Searcha and Dijkatra algorithm are doing. Is this correct? Is tree search actually linked to a more general concept of optimisation?


texts: I have a problem understanding a solution for number theory problem from SPOJ

texts:
Problem statement can be found here or down below.

The solution which I'm trying to understand can be found here or down below.

Problem Statement.

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

Example
Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

Solution

Concept: The idea behind solution here is to generate all the prime numbers that could be factors of numbers up to the maximum endpoint 1 billion. That square root happens to be around 32000. Using this array, do a bounded Sieve of Eratosthenes only in the range requested.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

int main() {
int primes[4000];
int numprimes = 0;

primes[numprimes++] = 2;
for (int i = 3; i <= 32000; i+=2) {
    bool isprime = true;
    int cap = sqrt(i)+1;
    for (int j = 0; j < numprimes; j++) {
        if (primes[j] >= cap) break;
        if (i % primes[j] == 0) {
            isprime = false;
            break;
        }
    }
    if (isprime) primes[numprimes++] = i;
}

int T,N,M;
scanf("%d",&T);

for (int t = 0; t < T; t++) {
    if (t) printf("\n");
    scanf("%d %d",&M,&N);
    if (M < 2) M = 2;

    int cap = sqrt(N) + 1;

    bool isprime[100001];
    memset(isprime,true,sizeof(isprime));

    for (int i = 0; i < numprimes; i++) {
        int p = primes[i];

        if(p >= cap) break;

        int start;

        if (p >= M) start = p*2;
        else start = M + ((p - M % p) % p);

        for (int j = start; j <= N; j += p) {
            isprime[j - M] = false;
        }
    }

    int start = (M % 2)?M:M+1;

    if (M == 2) {
        printf("2\n");
    }
    for (int i = start; i <= N; i+=2) {
        if (isprime[i-M]) printf("%d\n",i);
    }
}
return 0;
}

I know how Sieve of Eratosthenes works and I also ran this program using pen and paper. It works fine but I 'm not able to understand why it works and how do I prove that this program and the algorithm used in it are right?
I spent hours but could not prove.
Any help would be appreciated.


texts: Best algorithm for Renyi–Ulam Game with lies

texts:
Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type).

Game :

$A$ chooses an element in $\{1,2,\dots,n\}$.
$B$ tries to guess this number by asking Yes/No
questions.

Binary search is a way to solve the problem, so $\log n$ many queries will be sufficient to solve the problem when player $A$ does not lie. If player $A$ lies exactly once then we can problem with $2\log n$ many queries (by just asking the same query two times). What if $A$ may lie many times, but with a rule that they may not lie twice in a row and should say the truth when we find their number?

I was thinking of this and I found a relevant paper which was hard for me to understand. Could anyone give a simpler version of the algorithm when $A$ can't lie twice in a row and says the truth when their number has been guessed?


texts: Most efficient algorithm to print 1-100 using a given random number generator

texts:
We are given a random number generator RandNum50 which generates a random integer uniformly in the range 1–50.
We may use only this random number generator to generate and print all integers from 1 to 100 in a random order. Every number must come exactly once, and the probability of any number occurring at any place must be equal.

What is the most efficient algorithm for this?


texts: Check whether all elements are different

texts:
Assume we have $n$ double elements $a_1 \dots a_n$. We want to find out if two of the elements of the array are identical. And we have a hash function $h(x)$ which assigns each double value an integer between $1$ and $n$ and which can be calculate in $O(1)$ time. Let $m := \{(i,j) : a_j  \neq a_i \text{ and } h(a_j) = h(a_i)\}.$

How can i check if all $n$ elements are different in $O(n+ |m|)$ time and $O(n)$ memory?

1) The naive approach would be to check all $n$ elements if there is another element with the same value, which requires $O(n^2)$ time.

2) A better way would be if i sort the elements, which needs $O(n \cdot \log(n))$ time and then check each adjacent pair of elements. In total it would be $O(n \cdot \log(n))$.

But i don't know how i can solve this problem quicker. I think neither approach 1) nor 2) can be further improved. Apparently I have to use the hash function somehow, but I don't see how.


texts: Difference between a TM with an empty language and the one accepting empty string

texts:
If a TM(Turing Machine) accepts NO input string(even the blank), then its language is empty.

If a TM ONLY accepts the blank string(meaning that there is nothing on the tape except for the default blank characters), then its language has only one item and it is the blank string.

Are these definitions correct?

Could you describe the TM for each?

Also, this might be irrelevant but let me ask: I saw somewhere that there must be at least two states for a TM. Which states must be there all the time in a TM?


texts: Consider a Turing Machine which (1) reads all its input and (2) accepts inputs arbitrarily large. Given the affirmative answer to the previous question that there must be a loop in the finite-state control as its inputs get larger, could we conclude that there may be more than one loop in such a machine? That is, there could be several loops, not just one?


texts:
Apologies if a duplicate. New to this community and did try to search.

I want to create a mapping document that equates defect severity levels together so it looks like

|| System 1 || System 2 || System 3 ||
| level1-1 | level1-2 | level1-3 |
| level2-1 | level2-2 | level2-3 |

So that I can effectively do a lookup with a key of "level2-2" and get the row back. Similar I guess to a SQL row and being able to match on a column

Is there a name for this data structure?


texts: Solving for Hit Ratio of a Theoretical Memory System

texts:
Long time lurker, first time poster. The book I am reading is William Stalling's "Operating Systems: Internals and Design Principles" Seventh Edition.

Stalling's definition of hit ratio according to the book is thus: "the hit ratio is defined as the fraction of all memory accesses that are found in the faster memory."

One of his questions is that given a memory system with a cache memory access time of 100 nanoseconds and a main memory access time of 1,200 nanoseconds; "If the effective access time is 10% greater than the cache access time, what is the hit ratio H?"

I have already found an answer online after attempting this question myself,

  (0.10 x 100) = (1-H)1200

However, I was wondering if someone could explain two things:

Where did this formula come from? (I have searched the chapter prefacing this question and, so far, Stallings has not derived or discussed any formulae.)
Why is it 0.10 x 100? If the effective access time is 10% greater than the cache access time, would it not be 0.90 x 100? As 10% faster would be 10 nanoseconds less, not 10 nanoseconds total.

Pre-post edit:
 Looking through other threads I noticed that the miss ratio is 1 - hit ratio (which is logical). Staring at the answer I found for a minute afterwards brings me another question:
 Is the formula that was used to answer this stating that the effective access time of the fastest memory is equal to the effective access time of the slowest memory?

Edit:
After digging around in StackExchange and Google, I found an excerpt from Silberschatz that deals similarly with this problem.

Given his formula:

  effective access time = H*cache access time + (1-H)*main memory (in this case)

Using values from the above problem:

  1.10*cache access time = H*cache access time + (1-H)*main memory access time

Substituting real numbers:

  1.10*100 = H*100 + (1-H)*1200

Solving finds 1090/1100 or H to be approximately .9909, giving a hit ratio of approximately 99.1% Close to the "found" answer online, but I feel a lot better about this one.


texts:
I need to prove that $n^4+2n = \Omega (n^2)$

Which means I need to point two constants $c_1,c_2$ that from $n_0$:
$$ c_1 \leq \frac{\log(n^4+2n)}{\log(n^2)} \leq c_2$$

Now I know that:
$\lim_{n \to \infty } \frac{\log(n^4+2n)}{\log(n^2)} = 2$ so I can choose $c_1 = 0.5$ and $c_2 = 3$ but how do I do I calculate the $n_0$ that this sentence become true to?


texts: What is the complexity of Hamming nearest neighbor to a subspace ...?

texts:
Suppose that $F_2$ denotes the field with $2$ elements. We are given $m$ vectors $\{x_1, \ldots, x_m\}$ in $F_2^d$ which are a basis for a subspace $W$.

Suppose we have a vector $v \in F_q^m$, and we want to find a $w \in W$ that is closest to $v$ in the Hamming metric.

What is the complexity of this problem, as a function of $md$?

1) It's clear that there is an algorithm taking exponentially many steps. $W$ has $2^m$ elements, each of which takes $d$ bits to describe. So we just search through them.

2) It's unclear to me if this problem is even in $NP$. I can verify in polynomial time whether one vector in $W$ is closer to $v$ than another vector in $W$, but I do not know how to verify if one is the closest (or minimizes the distance). I suspect that it is impossible to do. Can anyone outline or refer me to a proof that this problem is not in $NP$?

3) If it is in $NP$, then is it $NP$-hard?

I guess this is well known, and presumably already discussed on this webpage. I poked around for a bit and couldn't find it, however. A reference would be welcome.


texts: Find the number of words in a language of given length

texts:
I was asked the following question:

  Consider the language $S^*$, where $S = \{ab, ba\}$, write out all the words that have seven or fewer letters?

How do I go about calculating the number of words? Are there any resources that break this down to the most basic level?


texts:
int a = 0;
    for (int i = 0; i < n*n; ++i) {
        for (int j = 0; j <= i; ++j) {
            a += j;
        }
    }

Could someone help prove to me that this is function is $O(N^4)$.

I remember doing this problem a while back, but now I do not see it.

I understand that the outer loop is $O(N^2)$ but I am unsure of how this would cause the inner loop to be $O(N^2)$ as well


texts: What are the key differences between Spiking Neural Network and Deep Learning

texts: Deep Learning, now one of the most popular fields in Artificial Neural Network, has shown great promise in terms of its accuracies on data sets. How does it compare to Spiking Neural Network. Recently Qualcomm unveils its zeroth processor on SNN, so I was thinking if there are any difference if deep learning is used instead.


texts: Expected number of common edges for a given tree with any other tree

texts:
So I am working on a problem where I have a set of (labeled) nodes and I have a tree structure (rooted) over that set of nodes. The goal for me is to automatically generate that tree structure. To find the performance of my algorithm, I am trying to use the score as the fraction of edges that I have common in the generated tree and the given tree. I want to compare this score with an expected value of the fraction if we generate the tree randomly (equal probability for all tree structures). What should be my approach to find this? Is there a computable efficient method for this? The brute force method (with some optimizations so that I only iterate on the structure without the labels) usually fails over n>10.

I understand if there is some efficient method to find no. of trees with k common edges then my problem is solved to much extent, but I am having a hard time to solve this as well.

EDIT: The edges are considered to be directed, towards the root.


texts:
Lets there are n stores.

A customer order x items. All the stores might not have all the items from the order.

So find the store/combination of stores that can serve the order request such that the combination that contain least number of stores.

Edit:

Example: Lets say there are 4 stores. User is ordering item 1, 3, 6, 7

Store 1 sells item 1, item 6
Store 2 sells item 1, item 2, item 3, item 4, item 5
Store 3 sells item 6, 7, 8, 9, 10
Store 4 sells item 5, item 7

The combinations of stores that can fulfil the orders
{ 2, 3 } , { 1, 2, 4}

So optimal solution in this case is {2,3}

P.S: I was asked this question in an interview. What would be the algorithm that would fit into the problem?


texts: The rightmost derivation is possible with the same rule of leftmost derivation

texts:
Can someone please help me in understanding the statement. What does it exactly mean?

What I think it means is that:
the derivation produces by the leftmost derivation is also possible with rightmost derivation.

What do you think guys?


texts: modeling DNS server CPU utilization on simulator framework

texts:
I'm creating my simulation framework, the DNS system. I have two related questions about the name server.

I would like to know how much time the Authoritative Name server spends time to resolve one packet when the packet arrives at the server?.i

I'm modeling the resource utilization at the DNS server in my simulator, I need to specify many parameters like maximum/avg/minimum CPU usage per one process. Those parameters need to be gotten from the real server. However, sadly, I don't know where is I can get from? It would be nice if you guide me on how to get them.

Because I'm simulating the Authoritative Name server in SimPy, but it seems like I need some specific values from the real server to define to my simulator.


texts: Simple discrete math problem: A and B in 3CNF

texts: I need to write (A and B) in 3CNF, and for whatever reason, I can only come up with (A or B) in 3CNF (A OR B OR X) AND (NOT(X) OR A OR B). Any help is greatly appreciated!


texts: Hardware protection needed for operating system kernel

texts:
I have a question related to the hardware protection needed to implement an operating system kernel:

  Identify at least three hardware level mechanisms that are necessary to protect an operating system kernel from malicious or erroneous user programs.

I can't work out what that would be from the Wikipedia article.


texts: Name of Generating One Value at a Time in Sequence Generation vs Encoder Decoder

texts:
a question about machine learning, specifically recurrent models:
For machine translation recurrent neural networks show great promise, common here is an encoder-decoder architecture which takes a source sentence, reads it, and then based on a compressed representation outputs a target sentence.
In opposition to that, for sequence generation you can also output one symbol at a time (let's stick with characters), e.g. like the char-rnn. You condition your model to learn the next character based on the ones you have read, so the model can e.g. create h-e-l-l-o, one character at a time. How would you call this second approach, does it have a name?
Thanks


texts: Why is it impossible for program contents to be modified by the program itself in case of Harvard architecture?

texts:
In the below link , it is mentioned that in case of Harvard Architecture it is impossible for the program memory to modify its contents so how can it happen  since instructions are fetched from the Program Memory only , and there will be instructions to modify  contents pertaining to that data only so how can it happen that the program cannot modify its own contents ?

http://spiroprojects.com/blog/cat-view-more.php?blogname=Difference-Between-Von-Neumann-Architecture-and-Harvard-Architecture&id=130


texts: Using LP to prove the max matching - min cover theorem

texts:
Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following proof, based on primal-dual linear program, is valid. This is mainly an exercise in understanding this primal-dual concept.

Step 1: define an LP for the maximum matching. For every edge $(u,v)\in E$, define a variable $z_{uv}$ whose value is 1 if the edge is in the matching. The LP is:

\begin{align}
\text{maximize} && \sum_{(u,v)\in E} z_{uv} &&
\\
\text{subject to} && \sum_{v\in Y} z_{uv} \leq 1 && \forall u\in X
\\
                  && \sum_{u\in X} z_{uv} \leq 1 && \forall v\in Y
\\
&& z_{uv}\geq 0  && \forall (u,v)\in E
\end{align}

Step 2. Create the dual LP using the recipe:

Each primal constraint becomes a dual variable - so there is a variable $x_u$ for each $u\in X$ and a variable $y_v$ for each $v\in Y$.
The sign of each dual variable is opposite to the sign of its primal constraint - so $x_u\geq 0, y_v\geq 0$.
The dual objective is minimization, where the coefficient of each dual variable is the number on the right-hand side of its primal constraint - in this case it is always 1. So the objective is "minimize $\sum x_u + \sum y_v$".
Each primal variable becomes a dual constraint.  The coefficient of a dual variable in the dual constraint is the coefficient of its primal variable in its primal constraint. In this case, the coefficient of the dual variable of a node $i$, in the dual constraint of the edge $(j,k)$, should be 1 iff $i=j$ or $i=k$.
The sign of each dual constraint is the sign of its primal variable.
All in all, the dual LP is:

\begin{align}
\text{minimize} && \sum_{u\in X} x_u + \sum_{v\in Y}y_v &&
\\
\text{subject to} && x_u + y_v \geq 1 && \forall (u,v)\in E
\\
&& x_{u}\geq 0, y_v \geq 0  && \forall u\in X, v\in Y
\end{align}

The dual LP finds a minimum vertex cover - it minimizes the number of vertices under the constraint that for each edge, at least one of its endpoints is in the cover.

My question is: is this proof valid?

The main thing I am not sure at is that the LP allows fractional variables, while the original problems are integral. What argument should be added to handle this issue?


texts: Operations under which the class of undecidable languages isn't closed

texts:
Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable languages are not closed under these operations?

What can we say about the kleene closure? Do we have examples for it too?  I.e. can the closure of an undecidable language be decidable?

Also, can we generalize such undecidable classes?


texts: Is X+Y sorting problem still an open problem?

texts:
I have found that X + Y sorting is an open computer science problem but that book was too old and then I have google it but didn't find any strong evidence that it is still open or there is an algorithm that can solve it in O(n2) comparison without using Fast Fourier Transform.

Is there any algorithm proposed that can solve it in O(n2) comparison or is it still unsolved?


texts:
I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below.

Consider the correctness of insertion sort, which we introduced at the beginning of this chapter. The reason it is correct can be shown inductively:

The basis case consists of a single element, and by definition a
one-element array is completely sorted.
In general, we can assume that the first n − 1 elements of array A
are completely sorted after n − 1 iterations of insertion sort.
To insert one last element x to A, we find where it goes, namely the
unique spot between the biggest element less than or equal to x and
the smallest element greater than x. This is done by moving all the
greater elements back by one position, creating room for x in the
desired location.

I do not understand paragraph #3. Could someone please explain it to me with an example?


texts: Countability union of all finite and countably infinite sequences over finite alphabet

texts:
Is the set of all finite and countably infinite sequences over $\{0,1\}$ countable?

From my analysis, I think it is countable. I think of this as the set of all strings from a finite alphabet $\Sigma=\{0,1\}$, hence $\Sigma^*$. (is this a good assumption?).

I later show that I can count each string in the following order: $0$,$1$ (length $1$), $00$, $01$, $10$, $11$ (length $2$) and so on.

However, I am very confused from the initial requirement "finite and countably infinite sequences". Does my method account for the countably infinite strings?


texts: I want to describe my search tree in an algorithm and describe how each level of the tree is created. But I cannot find good examples to help me express how to write it in an elegant way. Please if anyone can recommend a good resource for describing a search tree in detail in a pseudo code.


texts: Shortest path between all pairs of vertices in cyclic undirected weighted sparse graph

texts:
Is there any efficient algorithm to find shortest distance between all pairs of vertices?

The graph is:

Cyclic
Sparse (each vertex has either 2 or 3 edge)
undirected(bidirectional)
weighted
non-negative

Since Floyd-Warshall algorithm and Johnson's algorithm are best for finding shortest path for every pairs but:

Johnson's algorithm works on directed
Floyd-Warshall algorithm is best for dense graphs

I couldn't find any algo that is efficient for above graph conditions.


texts:
I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances.
I know that, in general, the complexity of the problem in terms of the number of variables (and computational time) increases with the number of edges in the graph.
I also know that for particular graphs where node degree is fixed (for example 3 or 4), polynomial-time algorithms exist that return the optimal solution.
Therefore, I am playing around with removing the edges with the highest weight from the graph, while ensuring each node retains at least a minimum degree, and seeing how this impacts solution time. As expected, reducing the number of edges in the graph does impact the solution time significantly.
Are there any theoretical results that tie this idea of removing edges from the graph before solving the problem to the optimality of the solution? Is it in some cases possible to conclude, a-priori, that some specific edge will necessarily NOT be part of the optimal solution?


texts: Expressing a logical constraint in integer programming

texts:
Let $x$ be an integer such that $x \in [ - 10,10]$ and $b$ a binary variable. Apply integer programming to express $b = 1 \leftrightarrow x \ge3$

My work:

\begin{equation}
    \begin{cases}
      \text{if}\,\,\,\,\ b = 1, & \text{then}\,\,\,\,\,\,\ x \ge3 \\
      \text{if}\,\,\,\,\ x \ge3, & \text{then}\,\,\,\,\,\,\ b = 1
    \end{cases}
\end{equation}

I got the following encoding $$3 + {M_1}(1 - b) \le x \le 2 + {M_2}b$$where $${M_1} \le- 13{\text{ and }}{M_2} \ge8$$

Checking:

Case: $b = 0$
$$3 + {M_1} \le x \le 2$$For  ${M_1} \le - 13$, we have $x =  - 10, - 9, \ldots ,2$

Case: $b = 1$
$$3 \le x \le 2 + {M_2}$$
For  ${M_2} \ge 8$, we have $x =  3, 4, \ldots ,10$

Thus, by choosing $b = \{ 0,1\} $ we can force $x$ to take any value from its domain.


texts: Rate Monotonic First Fit vs. Rate Monotonic Next Fit vs. Proportionate Fair

texts: What would an example of a set of tasks be, where RMFF, RMNF and P-Fair all result in a different number of processors required?


texts: Solving recurrence relation for asymptotic analysis

texts:
How to solve the recursion:

$
T(n) =
\begin{cases}
T(n/2) + O(1),  & \text{if $n$ is even} \\
2T(\lceil n/2 \rceil) + O(1), & \text{if $n$ is odd}
\end{cases}
$

I know that it can be written as O(n). But I want to find a tighter bound. For example, when dealing with powers of two, T(n) is O(logn), which will most probably allow for a tighter bound overall.

So, how to solve this recursion?


texts: decidability about NFA accepting an input

texts:
Let A = {(B,w) | B is an NFA that accepts w}. To prove that N is a decidable language,

M = "on input (B,w) where B is NFA and w is a string, simulate B on w. If B accepts w, accept. Otherwise, reject"

Is this a false proof? The proof from the textbook says that I have to convert NFA into equivalent DFA but I'm not sure why this would be necessary. Is it not possible to simulate NFA directly without conversion?


texts: When does greediness guarantee optimality?

texts:
I was wondering if there is any theoretical results characterizing under what condition does greedy algorithm actually finds the optimal solution.

Here is a motivating example. Suppose you are trying to find

$$\min_{x \in \mathbb{Z}^2} f(x)$$

where $f$ is convex, and the minimizer happens to be on an integer point $(a,b)$. You start from $(0,0)$ and at each iteration you are allowed to walk to one of the 4 integer points next to you.

The greedy algorithm is that, at each iteration $t$, you check the 4 points and walk to the one with the lowest objective value.

Now, here is a condition under which greedy method actually gives you the shortest path to find the minimum:

For any $x_1$, $x_2$, such that $f(x_1)\leq f(x_2)$, we have $min_{x \mbox{ next to } x_1} f(x)\leq min_{x \mbox{ next to } x_2} f(x)$.

So can the above condition be generalized to other settings? Or are there any general conditions that characterize such optimality? Quick google search didn't give me anything useful.


texts: Finding the maximum substring for which a given predicate is true

texts:
Given a string $S$ of length $N$ and a string predicate $F$, find the maximum substring, $s$, such that $F(s) = \text{true}$.  Assume that $F$ satisfies the following:

If $F(g) = \text{true}$, then any proper sub-string of $g$, above a certain cutoff length $L$, also evaluates true.
Strings below the cutoff length evaluate to false

What is the best strategy to find $s$ which minimizes the function evaluations?

Naive approaches:

Sequential search of the string $\mathcal{O}(N^2)$ function evaluations.

I suspect there must be a better way but anything I look up just sends me to Kadane's algorithm.  I would appreciate it if anyone has any references which might be useful or know the answer.


texts:
Last couple of days I've been pulling my hair trying to find the name of a
bomberman-esque algorithm which finds solutions to the question of where to place a single bomb so as to blow all targets up, either directly if all targets are within the blast radius (and axis) of a single bomb (placed in an empty cell) or via a chain-reaction by exploding nearby bombs which share the same x- or y-axis within the blast radius (hence the graph exploration issue).

I can describe the situation as following: given a square cell matrix S (the board state) of order n, containing symbols which differentiate between different objects(empty cells, rocks, targets and bombs), identify all empty cells P where a bomb with blast radius R can be placed so that all targets T will be destroyed. The other initially untriggered bombs also share the same blast radius.

Edit: The objects function as follows:

Empty cell; The only place where a bomb could be placed. Allows explosions to pass through.
Rocks; Blocks explosion waves.
Bombs; Sits passively in a cell until reached by an explosion wave, at which point it explodes and sends an explosion wave outwards in the the x- and y- axis, up to the defined blast radius-length away.
Targets; If reached by an explosion will be destroyed and counts towards the end goal of finding a solution where all targets are destroyed. Allows explosions to pass through.

I started out with a brute-force variant which simply went through all empty cells and started a search from there, which is quite inefficient if all objects are in one corner of a huge board. I came to the following pre-processing insight:

  Since a solution is only regarded as valid if all targets have been
  destroyed, I can therefore begin my search from any random T and if
  the path generated from that initial T does not destroy all T
  then there is no solution to that particular S.

I've made an algorithm which manages to find some solutions, but not for all boardstates I'm testing with. (currently only works if no other target is within a blastradius-length from the starting target).

Is this description ringing any bells for you?

My first instinct was an MST, but I've been unable to merge that algorithm with my description above.


texts: if I want only one element of the inverse matrix, does there exist a fast algorithm?

texts:
I use Mathematica to solve problems. I have a question about matrix inverse.

if I want only one element of the inverse matrix, does there exist a faster algorithm than using Inverse to calculate the whole inverse matrix and extract the element which I want?


texts: Is {xy | x, y ∈ Σ∗ and x contains more a’s than y} regular?

texts:
I've been asked to write a DFA for:
$\{xy\mid x, y \in \Sigma^*\text{ and }x\text{ contains more }a\text{’s than }y\}$ where $\Sigma=\{a,b\}$.
I don't believe this is possible. Can anyone confirm if this is not a regular language so that I'm not wasting my time if I'm correct.
Edit
Thinking again, while it's impossible to track exactly how many $a$'s are in $x$ or $y$ respectively, we know $x$ must have the number of $a>0$ at the very least and that the number of $a$'s in the string cannot be 2 since the condition of 'more' $a$'s has to be satisfied. Can you just write a DFA accepting strings with inputs containing 1 $a$, and 3+ $a$'s to satisfy the language?


texts: Definition of efficiency versus complexity of algorithm

texts:
When I read introductory textbooks I get contradictory answers. In some cases efficiency and complexity are treated the same and the big-O notation is used to indicate that (for example) for an O(n) algorithm the time to execute is linearly proportional to the input dataset size.

From other sources I have read that efficiency is a measure of the computing resources required to execute an algorithm, but not the same as the complexity of the algorithm. So for example is it possible to have an algorithm (say to multiply two decimal numbers) that is efficient in terms of its resources (it does not need much to execute) but is complex in that as the input dataset increases in size the time to execute is O(n^2) ???


texts:
Short version

The question & answers relate to the following topics:

File as a collection of records vs. file as a stream of bytes
Sequential File
Distinction between file data and metadata
Transfer of metadata along with the file
File size measurement

Original question

According to William Stallings' Operating Systems, the most common structure for a file is the sequential file, which consists of a collection of records. All files have the same amount of records and each record has a predetermined length. This seems very inefficient and doesn't match my previous understanding of files at all.

For example: if I have a JPG file, it would have records indicating things like resolution, creation date, etc. Some record fields would not be relevant for a JPG file and would be empty, but space would be reserved for those fields regardless. Since the actual data of the JPG file would be too large for any record, there would be an "overflow pointer" to where the data actually is.

Stallings also presents an alternative to file-as-a-collection-of-records: file as a stream of bytes. While the book claims it's rare, it is more in line with my understanding of files: a file is just raw data with no universal structure. However, if I move a file from one computer to another, things like "creation date" move along with it, indicating that files have some attributes which are saved within the file (as opposed to in the file management system). If all files have some header information like creation date, and that information is saved within the file, why is it that my Ubuntu claims an empty text file takes 0 bytes space?

I'm guessing that a typical file is simply a stream of bytes with no predetermined structure and that header information like the creation date is somehow transferred along with the file when it is moved. I'm guessing that the chapter about sequential files in the book is some kind of remnant from the 80's. Please correct any misconceptions that I have.


texts: Symmetric Difference of Turing Recognizable and Finite Languages

texts:
Let A be a Turing Recognizable Language and B a finite Language.
I want to prove that their symmetric difference is Turing Recognizable.

My reasoning: B is finite, therefore the finite number of strings can be put through a DTM , M, such that L(M)= A. If M accepts, then remove that string from B and put it in a list, R. * Otherwise, leave it in B. The DTM for the symmetric difference just checks if it is either in B, which it accepts, R which it rejects or if M accepts.

I feel like I have simplified this somewhere, but I would appreciate any pointer in the right direction.

I am unsure how to determine the strings in both A and B. The way I have done it (above) would run forever, because if it is not in A and is in B, it would never halt. This would result in never getting past the * above.

How can it be determined if a string is in A and B?


texts: Difference between data bus, address bus and CPU bit size

texts:
I have some doubts all related to the same basic concept of how a computer works.

1) I always thought that the address bus width defines ultimately how many memory locations the CPU can access (point to), therefore the memory range (i.e. in a 32-bit wide address bus, the CPU can access up to 2^32 memory locations, which is 4GB of memory, given that each memory location is a memory block containing 1 byte).

Is this the right understanding?

2) At the same time, I had the impression that the data bus width is also called the word size, and both refer to the amount of data that the CPU can read from or write to memory at a given time.

Is this correct?

3) Lastly, when we say that a CPU is 32-bits, I always thought that this means that the internal CPU registers are 32-bits. Is this correct or do the address/data bus sizes have any direct effect on whether the CPU is 16, or 32 or 64 bits?


texts: Text on data structures to use along with Lipschutz

texts:
I will be teaching a data structures course this Fall semester for second year computer science undergraduates. The textbook and syllabus currently used follow the text "Schaum's outlines: Data structures with C" by Lipschutz.   I think the Schaum's outlines series are more a supplement to textbooks and that the students should be given another standard textbook as a reference which we can follow closely.  Which text would be good to use?   The text should be at the same beginner's level as Lipschutz's text.  Faculty who are teaching other sections of the course will be using Lipschutz, and all students will be taking a common exam, so I can't avoid Lipschutz entirely.

I prefer the classic Data Structures and Algorithms book by Aho, Hocroft and Ullman.  But I was thinking a modern reference with C implementation and at a slightly more elementary level might be easier for the students to follow.  The students will also be taking a data structures lab course in parallel where they will have to do C implementation.

I found Weiss' "Data structures and Algorithm Analysis in C" online.  Would that be a good text to follow?


texts: What is the fastest algorithm for finding all shortest paths in a sparse graph?

texts:
In an unweighted, undirected graph with $V$ vertices and $E$ edges such that $2V \gt E$, what is the fastest way to find all shortest paths in a graph? Can it be done in faster than Floyd-Warshall which is $O(V^3)$ but very fast per iteration?

How about if the graph is weighted?


texts: Is minimising the total number of one entries in binary matrices $CA$ and $C^TB$ NP-HARD?

texts:
Given a two rectangular binary matrices $A$ and $B$ with dimensions $c\times a$
and $c \times b$ respectively, does there exist an invertible binary
matrix C with dimensions $c \times c$ such that the total number of 1
entries in $CA$ and $C^TB$ is below a target threshold $t$?

Here we are working in $GF(2)$, where multiplication and addition are AND and XOR respectively.
What is the hardness of this problem? Are there approximation algorithms to this problem?
We know this problem is in $NP$, as a valid $C$ can be used as a certificate.
Also, we know how to find $C$ when there exists the a solution for $t = a+b$, by using Gaussian Elimination.


texts: Push down automata what to do when there is no suitable transition

texts:
This is a question that has emerged from a recent quiz I have taken. In short

  Consider the following transitions on a push down automaton. Assume the starting state is q. Which one of the following inputs will lead the automaton to state p with the stack containing the string XXZ?

I am gonna write only the transitions from state q regardless of the input symbol:

 (q, 0, Z) -> (q, XZ)
 (q, 0, X) -> (q, XX)
 (q, 1, X) -> (q, X)
 (q, ε, Χ) -> (p, ε)

Now the thing we note here is that there is no transition from state q when there is an empty stack regardless of the input symbol. How does one answer that question assuming we start from an empty stack? I have omitted the inputs cause I don't really care about the answer to the quiz, all I want to know is how would someone start working on that?


texts:
We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for matching the ith captured subexpression). It is known that such regexes have far more expressive power than the regular expressions defined in formal language theory.

I am interested in the following two categories of arithmetic functions on the unary representation of the natural numbers (i.e., a sequence of $n$ symbols a represents the number $n$):

Transducers

In the first category, a function is given by a search string, a replace string and an operation Replace All, which substitutes the replace string to any occurrence of the search string. For instance:

$\lambda n. 2n$

"a"
"aa"

$\lambda n. \frac{n}{2}$

"(a*)\1a?"
"\1"

$\lambda n. \frac{n}{3}$

"(a*)\1\1a?a?"
"\1"

$\lambda n. n \bmod 2$

"(a*)\1(a?)"
"\2"

Collatz function

"(a*)\1$|((a)*)"
"\1\2\2\2\3"

Smallest divisor greater than 1

"(aa+?)\1+$|(a*)"
"\1\2"

Acceptors

In the second category, a predicate is given by a regex pattern and an operation Match which tries to match the pattern from the beginning of the input sequence. The output is interpreted as True is the match succeeds, and False otherwise. For instance:

is_even

"(aa)*$"

is_odd

"a(aa)*$"

is_not_prime (from Neil Kandalgaonkar)

"a?$|(aa+)\1+$"

Question

Is it possible to devise a transducer for $\lambda n. n^2$ or an acceptor for is_prime? More generally, which arithmetic functions and predicates can be defined in such a model?


texts: Examples of infinite sets of regular and non-regular languages that their union is regular and non-regular

texts:
I have been looking around for a good source to answer the following question.
Have read a few different sources but have not found the answer I was looking for.

The question is:

  Give an example of an infinite set of:

  a. Regular languages whose union is a regular language

  b. Regular languages whose union is a non-regular language

  c. Non-regular languages whose union is a regular language

  d. Non-regular languages whose union is a non-regular language

I've used this post to answer part b, and I understand the method behind it (at least I think I do).

What is the right way to approach this question?

Wouldn't an infinite set of anything constitute a non-regular language, by definition?


texts: Complexity of recursive solution to coin change

texts:
How do you go about analysing coin change recursive solution. i.e,
T(N,K) = T(N,K-1) + T(N-1,K) for K denominations that add up to amount N.

You can find the problem description and pseudo code here - http://www.algorithmist.com/index.php/Coin_Change#Recursive_Formulation


texts: Algorithm with $O(n)$ time and $O(n)$ space to compare two arrays

texts:
$A$ and $B$ are two arrays with $n$ elements each in the range $1$ to $n^2$.

1.How to check if the elements of $A$ are distinct in $O(n)$ time and $O(n)$ space

2.How to check if $A$ and $B$ have a common element in $O(n)$ time and $O(n)$ space.

Both the algorithms shouldn't use Hash sets or any other advanced data structure. A and B are just simple Arrays.


texts:
Disclaimer:
By asking this question i'm assuming that "memory" on a quantum computer works similarly compared to a regular computer in the sense that you can store information deterministically and when needed, retrieve it in the same way.
I'm also assuming that n qubit has 2^n "states" that can be set/read independently/concurrently

Question:

Let's suppose that in a 3 qubits quantum machine, at a certain point in time, after a bunch of other operations, I have set my 3 qBit to "111". In another words, those 3 qubits have a state that says "111" and other 7 states of irrelevant information.
At a later moment, given the superposition effect, how does one guarantee that reading those 3 men addrs will yield me my "111"s? In another words, how can I be sure that I'm reading the state that i set previously?


texts:
In coding theory, 'how good a code is' means how many channel errors can be corrected, or better put, the maximal noise level that the code can deal with.

In order to get better codes, the codes are designed using a large alphabet (rather than binary one). And then, the code is good if it can deal with a large rate of erroneous "symbols".

Why isn't this consider cheating? I mean, shouldn't we only care about what happens when we "translate" each symbol into a binary string?  The "rate of bit error" is different than the rate of "symbol error". For instance, the rate of bit-error cannot go above 1/2 while (if I understand this correctly), with large enough alphabet, the symbol-error can go up to $1-\epsilon$. Is this because we artificially restrict the channel to change only "symbols" rather than bits, or is it because the code is actually better?


texts: Lamport’s fast mutual exclusion algorithm intuition

texts:
Here's Lamport’s fast mutual exclusion algorithm:

want[i]:=true
fast-lock:=i
if slow-lock<>0 then
     want[i]:=false
     while (slow-lock<>0) {//busy wait}
     goto 1
slow-lock:=i
if fast-lock <> i then
     want[i]:=false
     for j:=1 to n do:
       while (want[j] = true) {//busy wait}
     if slow-lock <> i then
         while (slow-lock <> 0) {//busy wait}
         goto 1
CS
slow-lock:=0
want[i]:=false

I understand why eventually all 4 criteria for mutual exclusion hold,
 but i dont understand the intuition behind this algorithm:

In what sense are this locks fast/slow?
What's the point, for    example, after freeing the slow lock, go
back to the beginning of    the algorithm?

I tried to read this article, but it was to complex for me to understand.


texts: Clock variant of the Second-Chance page-replacement Algorithm vs. standard Second-Chance Algorithm

texts:
A sample question for my upcoming Operating Systems exam is:

  Under which circumstances would the clock variant [of the second-chance algorithm] be preferred over the standard second-chance algorithm and why.

I was under the impression that the clock variant is always preferred. Am I missing something? Are there specific circumstances (hardware-related perhaps) where the clock variant would be preferred? Equally, is the standard algorithm ever preferred?

A similar question was asked and answered here but it didn't mention any benefits

EDIT: A comment from @Wandering below led me to ask my lecturer for more clarification, and he is not referring to the two-handed clock variant.


texts: T(n) = aT(n/b)+f(n), I don't understand the difference between a and b

texts: I was analyzing the time complexity for recursive algorithms like merge sort, but when I came across that recurrence, [I think that equation is called a recurrence right?] I couldn't differentiate between a which mean the number of subproblems and b which in my slides it says is the factor by which n is divided by.


texts: I understand that by being clever about the way we navigate the search space of the SAT problem we're going to get better performance than by randomly choosing and testing solutions, though of course both methods have $O(2^n)$ time complexity. What are the specific reasons that DPLL gives better performance than brute-force (sequentially testing solutions from FALSE-FALSE-FALSE.... to TRUE-TRUE-TRUE....)?


texts: Why are Chess, Mario, and Go not NP-complete?

texts:
I have a hole in my understanding of what makes a problem NP.

I understand that Mario, for example, is NP-hard - it can be reduced to the NP-complete problem of 3SAT (see https://www.youtube.com/watch?v=mr1FMrwi6Ew)

Therefore if these games were also in NP, they would be NP-complete (by definition).

My understanding is that NP problems can be solved in polynomial time by a nondeterministic turing machine that "guesses" each step correctly. Why isn't this the case for Mario, Chess, and Go? Can't such a machine just guess the right way, for example, for Mario to go at each gadget thus rendering the problem in NP (and thus NP-complete)?


texts: Is the output of a Mealy/Moore automaton a regular language?

texts:
How can I prove that the output sequence of Mealy Moore Machine is a Regular Language ?
And what if transition outputs more than one character ? How can we prove for this case that the language in (1) and (2) are same ?

Can I do something like this -

The right side one is Mealy Machine. So can I prove like making a machine in left with transitions using output sequence of Mealy Machine ?


texts:
I have completely understood how Aho Corasick works for finding one pattern in a text, and how to construct the automaton for a certain pattern.  I have studied the CLRS book and watched this video. But the problem is that I cannot find any material on how to build an automaton for more than just one pattern. For example given the following words, how can I build an automaton with the required transition function?

P = {vine, vincent, cent, center}

Are there any topics on StackOverflow or any YouTube videos that teach this step-by-step?


texts: determining whether a program halts or not

texts: I have difficulty understanding the halting problem. I know that for all possible Turing machines and strings w, we don't have a Turing machine which can decide whether a TM M halts on input w.Now my problem is that if we have a program p that for example solves the Hamiltonian path problem can we conclude from the halting problem that we can't decide whether this program halts or not?


texts:
The best-, average-, and worst case time complexity of Heapsort for $n$ distinct keys are all $\Theta(n \lg n)$.

  What are the worst-case inputs for heapsort?


texts: How do I compare different optimization algorithms when step-size is unknown?

texts:
I wish to compare different optimization algorithms (gradient descent, Newton, quasi-Newton, conjugated gradient, etc) for a particular problem at hand.
My main focus is on speed of convergence.

The issue is that all methods rely on a step-size $\gamma$. How do I compare the speed of my algorithms when I don't know which $\gamma$ would work best for which model?


texts:
Consider this algorithm iterating over 2 arrays (A and B)
size of A = n
size of B = m
Please note that m <= n
The algorithm is as follows
for every value in A:
    // code

for every value in B:
    // code

The time complexity of this algorithm is O(n+m)
But given that m is strictly lesser than or equal to n, can this be considered as O(n)?


texts: Could two decidable languages ever not have a mapping reduction?

texts: Is it ever the case that two decidable languages $L_1$ and $L_2$ that cannot be reduced to one another (in either or both directions)? Intuitively, I would not expect there to be, but rigorously, are there extreme examples that prove otherwise?


texts: What do two non-terminal symbols on the left hand side of a BNF grammar mean?

texts:
I'm learning BNF, and the text I'm using gives a simple grammar for integer expressions like this:

<expression> ::= <number> | <expression> <operation> <expression>
<operation> ::= + | - | x
<number> ::= <digit> | <digit> <number>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

This makes sense to me, but then it goes on to show that you can have two non-terminal symbols on the left hand side of expression like this:

e,f ::= n | (e o f)
o ::= + | - | x
n ::= d | d n
d ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

I don't understand what it means to have both e and f on the left hand side: what does it mean and what is the point of it?


texts: Point Location Problem in Polygon in Repetitive Mode for a Simple Polygon

texts:
I consider Point Location Problem in Polygon in repetitive mode in the case of simple polygon.

In computational geometry,Point Location Problem in Polygon problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon.

There are few method that work in Single-Shot approach, where the input is a polygon $P$ and a single point $q$ (no preprocessing time). Ray casting algorithm is the famous algorithm for single-shot, it takes $O(n)$ to determine whether a point $q$ belongs to polygon $P$.

In addition, there is a repetitive approach, where instead of single point $q$ we should check the sequence of points, therefore the preprocessing is required. Division wedge is a algorithm that works in repetitive mode. Query time of division wedge is $O(\log n)$ and preprocessing time is $O(n)$. Division wedge assumes that there is a central point in polygon, visible from every vertex of polygon (part of the kernel of the polygon). The problem is a central point can be easily determined in convex polygon as well as in star-shaped polygon, but what to do in the case of simple polygon.

If division wedge is applied in the case of simple polygon how we can determine a central point in simple polygon? If division edge in not applied if there is the more efficient way to solve a problem in simple polygon than in arbitrary planar subdivision.


texts:
$L = \{ w : w  \in \{a, b\}^* \land |w|_a = |w|_b\}$ where $|w|_a$ means number of $a$ in string $w$.

I came up with this grammar:

$S \rightarrow aSb \ |\ bSa \ | \ \epsilon .$

Can someone please tell me what is wrong with it?


texts: Recover NLFSR description from given output

texts:
Given Fibonacci's Nonlinear Feedback Shift Register output, how can I recover the description (nonlinear feedback function and current seed)?

The clean output of consecutive and unmodified is large and the generator is available to ask for next values. The source code of PRNG is not available, the seed is unknown.

For the linear case there is already known Berlekamp-Massey (or Reed-Sloane) algorithm yielding the shortest polynomial. Is there a similar method for nonlinear case?


texts: What is the use case for multi-type-parameter generics?

texts:
In C#, one can define a class/method/function with multiple type parameters. For example,

// function
void foo<T1, T2>(T1 x, T2 y) { /*body*/}

// class
class Bar<T1, T2> { /*body*/ }

I understand how to use it, but I don't understand why I need it. So I'm hoping someone can answer the following questions:

1) What is the use case for multiple type parameters?

2) Based on the use case given in Question 1, what are the alternative solutions for that use case if multiple type parameters is not a feature of the language in use?


texts: Examples of bad statistics in Computer Science

texts:
I am preparing class materials for the applied statistics class for Ph.D. students and want to present them with examples of bad statistics in different fields of computer science. I am especially interested in the examples form the sub-fields represented in our department:

CHI
MIS (with focus on qualitative methods and social experiment design)
Parallel computing and Big Data
Databases
Software engineering (software evolution, software architecture)
Game theory
Networks

Maybe you can recommend good literature regarding this topic?


texts: Greedy algorithm for Set Cover problem - need help with approximation

texts:
I want to approximate how close is the greedy algorithm to the optimal solution for the Set Cover Problem, which I'm sure most of you are familiar with, but just in case, you can visit the link above.
The problem is NP-Hard, and I'm trying to find a bound on how well does the greedy algorithm perform.
I know it looks a lot, but please bare with me. I pretty much did most of the work, I'm just missing that last small piece.

Here is the pseudo code:

Input: $U$ - set of elements, $F$ - family of sets s.t. $\bigcup_{S\in F}S=U$
Output: $C$ - a family of sets; $C\subseteq F$ s.t. $\bigcup_{S\in C}S=U$

initially C is empty

while U is not empty do:
    choose S from F that maximizes the cover of elements in U
    add S to C
    subtract S's elements from U

return C

The algorithm is pretty straight forward, and it is easy to see that it is indeed polynomial.

This is my attempt to approximate:
Claim 1: In a set $U$ of $m$ objects, that can be covered with $k$ sets, there has to be a set $S\subseteq U$ whose size is at least $\frac{1}{k}m$.
Proof: Trivial. (I decided not to prove it)

A corollary is that given the situation described in that claim, the greedy algorithm will choose a set whose size is at least $\frac{1}{k}m$.

Claim 2: Given a universe $U$, if there exist a cover of size $k$, then after $k$ iterations, the greedy algorithm will cover at least half of the elements, meaning at least $\frac{1}{2}n$ elements.
Proof: By claim 1, in the first iteration the algorithm will cover at least $\frac{1}{k}n$ elements. Upon entering the second iteration, there are at most $n-n\frac{1}{k}$ elements, and so the greedy algorithm will at least cover additional $\frac{1}{k}(n-n\frac{1}{k})$ elements. In general, on the $i$'th iteration, the algorithm will cover $\frac{1}{k}(n-n\frac{i-1}{k})$ elements. So after $k$ iterations:
$$\sum_{i=1}^{k}\frac{1}{k}(n-n\frac{i-1}{k})=\sum_{i=0}^{k-1}\frac{1}{k}(n-n\frac{i}{k})$$
$$=\sum_{i=0}^{k-1}\frac{n}{k}-\sum_{i=0}^{k-1}\frac{ni}{k^2}=n-\frac{n}{k^2}\sum_{i=0}^{k-1}i$$
$$=n-\frac{n}{k^2}(\frac{k(k-1)}{2})=n-\frac{n}{2}(\frac{k-1}{k})\geq\frac{1}{2}n$$

OK, now this is where I need help: I know that in the first $k$ iterations, the algorithm picks at least half of the elements. After another $k$ iterations, another half was covered, out of what's left (meaning another $\frac{1}{4}n$). So in general, I know that the bound is $k\log n$, I just can't figure out how to formalize it.
What formula represents this behaviour? $T(ki)=T(\frac{1}{2^i}n)$ and solve for $i$? It didn't work...
What formula or equation should I solve to actually show that the number of iterations is bounded by $k\log n$?


texts:
Does anyone know of an accessible introduction to Cobham's model independent characterization of FP and it's equivalence to the standard definition using Turing machines?  The best source I could find on-line was https://www.cs.toronto.edu/~sacook/homepage/ptime.pdf : a paper by Stephen Bellantoni and Stephen Cook detailing another similar approach.  However, it is a little too difficult for me to understand.

As a side question, does anyone know if researchers are still interested in Cobham's formulation or feel it could possibly lead to resolving open problems?


texts:
A player playing the Minimax strategy should choose moves which minimise their maximum loss.

What should happen when draws can happen? Should we class the draw as a win because we aren't losing? Or should be class it as a loss because we are trying to win the game and a draw isn't a win? Or should we just class a draw as its own end point?


texts:
Asked this at programmers Stack Exchange, was recommend to ask here :

What would be the big o for the algo:

for (i=0; i < n*n; i++)
  for(j=0; j<i*i; j++)

As per my understanding 1st loop will loop upto n^2 times. 2nd loop will go around n^2 times.

Am I right or is it a O(n^6) representation.

Also is there a easy way to say when to use log. I have assumed that whenever the loop variable is multiplied the ln function is applied

eg: for (i=1; i<n*n i=i*2) Big o for the loop as per my understanding is O(ln n^2) ( Am I right again?)

Please clarify, thanks in advance


texts: Construction of a Deterministic Tree Automaton (DTA)

texts:
Let $L \subseteq \Sigma^*$ be a regular language. Let $\Sigma' = \Sigma_0 \cup \Sigma_2$ where $\Sigma_0 =\Sigma$ and $\Sigma_2=\{*\}$.

We define $T_L=\{t \in t_{\Sigma'} \mid \text{The leafs from t are from a word in $L$}\}$ as a tree language.

The task is to construct a DTA for $T_L$.

A DTA A over $\Sigma = \Sigma_0  \cup \cdots \cup \Sigma_m  $ is a four tuple with $A= (Q,\Sigma, \delta, F)$ where Q is a finite state set, F final state set, and $\delta : \bigcup _{i=0}^m(Q^i \times \Sigma_i)\rightarrow Q$ and $Q^0 \times \Sigma_0 = \Sigma_0$.

My idea was to set $\Sigma _0 \subseteq L \subseteq \Sigma^*$. But how can the transition function check whether it is a word in L?


texts: Can a 3 Color DFS be used to identify cycles (not just detect them)?

texts:
Can a 3 color DFS be used to identify all cycles in a directed graph not just detect them?

In other words if I have a directed graph with multiple cycles, can I run a function on them such that the function returns the list of nodes that compose each simple directed cycle in the graph and not just a boolean true or false? Most answers online show pseudocode for detection and not identification (ie functions which return boolean values instead of node lists). You can assume that the graphs I'm referring to are mostly tree like in structure and aren't deeper than 5 nodes or so.

So for example, for this graph:

The list would be [[a,b,e], [f,g], [c,d], [d,h]]

With white, grey, black DFS a cycle is found when a node already colored grey is visited a second time through a different edge. What I'm struggling to wrap my head around is when this happens, how do we back track to identify all of the nodes involved in this detected cycle without increasing complexity or running DFS a second time. In the example below, if we do a DFS (exploring right edges first) starting at A, the stack will look like this [A,B,C,E,D,B] and the cycle will be detected when B is visited a second time. Given this stack how do we deduce that C D and B only are part of the cycle and not E or A?

I am aware that there are plenty of algorithms other than DFS that can do this (such as Johnson's algorithm or Tarjan's with a twist) I just want something simple to implement.


texts:
Can anyone give me a proof as to why

  Any range over a unviverse {1...n} can be reduced to at most  $2log_2n$
  disjoint dyadic ranges?

Where a dyadic range is a range of the form $[x2^y+1....(x+1)2^y]$.

This is in reference to the method for answering range queries with a Count-Min Sketch as mentioned in the original paper on CM-sketches


texts:
For example if
$$ f(x)= \Theta (g(x)) $$

from the definition of the theta notation, there exist c1 and c2 constants such that

$$c_1 g(x) \le f(x) \le c_2 g(x)$$

then if only we took the constants $1/c_1$ and $1/c_2$ we could say from the definition that

$$ g(x)= \Theta (f(x)) $$

Right?


texts: What's the fastest way to find the Kth smallest value in an unsorted list without sorting?

texts:
My initial algorithm:

Compare element 0 with every other element, keeping track of how many elements are less than it.
Repeat for each element until an element that is greater than exactly (k-1) elements is found.

I assume this would take $O(n^2)$ in the worst case. Can a faster runtime be achieved without sorting the list?


texts: What is the difference between 'features' and 'descriptors' in computer vision / machine learning?

texts:
I've read multiple time sentences similar to

  Finally, for standard image classification bag-of-words
  features based on SIFT descriptors have been found
  critical for high performances. We first compute a
  standard SIFT discriptor at regular grid points over
  the whole image.

Source: "Multi-class image segmentation using Conditional Random Fields
and Global Classification" by Nils Plath, Marc Toussaint, Shinichi Nakajima.

What is a descriptor? I thought  SIFT is an algorithm which operates on images and gives features (vectors in $\mathbb{R}^n$, where $n$ is fixed for a fixed size of images and parameters of the SIFT algorithm)?


texts: How to solve recurrence of a binary tree

texts:
I'm trying to solve this recurrence of a function of a binary tree with a recursive tree. But I can't find any pattern to solve it.
This function calculates both the height and if its a balanced tree.
template <typename T>
std::pair<bool, int> balanced_height(const BinTree<T> &tree) {
  if (tree.empty()) {
    return {true, 0};
  } else {
    auto [bal_left, height_left] = balanced_height(tree.left());
    auto [bal_right, height_right] = balanced_height(tree.right());
    bool balanced = bal_left && bal_right && abs(height_left - height_right) <= 1;
    int height = 1 + std::max(height_left, height_right);
    return {balanced, height};
  }
}

And the recurrence, $n$ is the number of tree nodes. I think that $n_l$ and $n_r$ should decrease in each call by 1.
$$
T(n) = \begin{cases}
   T(n_l)+T(n_r) + 1 & \text{if } n \gt 0,
   \\
   1 & n = 0 \\
\end{cases}
\\ \text{Given that }n_l+n_r+1=n
$$


texts: Difference between the two regular expression

texts:
I came across a question to create a regular expression to check whether there are even number of b's in a string of language {a,b}. The expression I came up with is (a+ba*b)*. However I found the solution online to be a*(ba*ba*). Is there any difference? If any where?

Also I know that (a+b)* is equivalent to (a*b*)*. So my solution comes out to be (a*(ba*b))*. So why that extra a*?


texts: What functions can combinator calculus expressions compute?

texts:
A combinator expression (let's say in the SK basis) can be thought of as a function that maps combinator calculus expressions to combinator calculus expressions. That is, one can think of an expression $X$ as a function $X:L \to L$, where $L$ is the set of all syntactically valid combinator expressions in the SK basis. This mapping is performed by applying the input to the expression, and then reducing to normal form to get the output.

Since the SK basis is Turing complete, one might naïvely think that there exists a an SK expression $X$ that implements any computable function from $L$ to $L$. However, this clearly isn't the case, since the result of reduction will always be in normal form. This means there is no way for an expression to have an output that isn't in normal form.

So instead, I could think of SK calculus expressions as mapping $L'$ to $L'$, where $L'$ is the set of SK expressions in normal form. Is it the case that, for any computable map $f:L'\to L'$, there is an SK expression $X$ that implements this map? Or are there further restrictions on the set of functions that can be computed by combinator calculus expressions in this way?


texts: Counting all $x,y,z$ such that $a[x] > a[y] + a[z]$

texts:
Given an array $a$, I want to count all triplets of indices $x,y,z$ such that $a[x] > a[y] + a[z]$.

I can think of two solutions:

Go over all triplets of indices $x,y,z$ directly. This takes time $O(n^3)$ and constant space.
Compute a new array consisting of all sums $a[y]+a[z]$, sort it, and then go over all $x$ and use binary search. This takes time $O(n^2\log n)$ and space $O(n^2)$.

Is it possible to improve on these solutions?


texts: Turing machine - Check if $a^p$ is prime

texts:
Question: Check if number of $a$ are prime with just two tapes in Tuning machine.

I'm not quite sure how to check it but what I've got so far is:

First tape will be the input. For example $aaaaa$

Second tape will be checking the numbers $2$ till $n-1$, meaning $4$ for this example.

We start checking them both from the beginning of the tapes, we write '$aa$' in the second tape, making some checks which I'm not sure, if we fail with these checks, start again but now with '$aaa$', and then lastly '$aaaa$'.


texts:
There is a grammar G given:

    S->XaX
    X->aX|bX|eps

I just replied to the first question that was about showing that this grammar is ambiguous. The second question is to find an unambiguous equivalent grammar of this grammar given. I don't really know how to do it or from where to start. Can anyone help me?


texts: How to collect free/bound variables in Lambda Calculus?

texts:
I am building a simple interpreter for untyped lambda calculus, currently trying to implement alpha-reduction.

According to this document on LC:

  Alpha-reduction is used to modify expressions of the form "λx.M". It renames all the occurrences of x that are free in M to some other variable z that does not occur in M (and then λx is changed to λz).

It appears that I need to collect the information about the scope (free/bound) of variables prior to alpha-reducing the expression.

How should one go about this? My initial idea was to traverse the AST and produce something similar to a symbol table.


texts: Clarification sought for definition of a cut that respects a set A of edges in Graph Theory

texts:
From CLRS (3rd edition), I came have this question on page 626:

Given these definitions from the text,

DEFINITIONS:
Given an undirected graph G = (V,E),
1. A CUT (S ,V-S) of G is a partition of V,
2. A LIGHT EDGE over a cut is any edge crossing the cut with a weight smaller than or equal to any other edge crossing that cut,
3. A cut RESPECTS a set A of edges if no edge in A crosses the cut.

In every example in the text, the set A is coincident with one of the partitions of the cut but I cannot see why this must be. Given an arbitrary new vertex v', it could be added to the partition that contains A and no edge from v' to A would cross the cut. The definition of respects says that a cut cannot divide A, not that A must define the partition.

There is clearly something here I missed since that does not seem consistent with the theorems. Can anyone point out my error?

+++++++++++++++

Amendment.
Thanks for the help. I also now realize that Theorem 23.1 only says that a light-edge is a safe edge but not that such a cut is guaranteed to find every safe edge since some edges may have both vertices in the same partition as A. I see in GENERIC-MST(G) that line 3 only says to find an edge. It is not until Kruskal or Prim algorithms that the method by which we find this edge is explained and neither depend upon the partition being coincident with the set of vertices defined by the set of edges A.

I find it interesting that in Kleinberg Tardos that they take a different approach and define a cut property (4.17, pg 145) that avoids this (what I find awkward) development of the ideas.


texts: Distributional error probability of deterministic algorithm implies error probability of randomized algorithm?

texts:
Consider some problem $P$ and let's assume we sample the problem instance u.a.r. from some set $I$.
Let $p$ be a lower bound on the distributional error of a deterministic algorithm on $I$, i.e., every deterministic algorithm fails on at least a $p$-fraction of the instances in $I$.
[Edit: For a given instance $s \in I$, we use $P(s)$ to denote the set of correct solutions. We say that a deterministic algorithm $A$ fails on an instance $s$, if the output produced by $A$ given $s$ is not in $P(s)$.]
Does this also imply that every randomized algorithm $\mathcal{R}$ must fail with probability $p$ if, again, we sample the inputs u.a.r. from $I$?
My reasoning is as follows:
Let $R$ be the random variable representing the random bits used by the algorithm.
\begin{align}
 \Pr[ \text{$\mathcal{R}$ fails}]
&=  \sum_\rho \Pr[ \text{$\mathcal{R}$ fails and $R=\rho$}] \\
&=  \sum_\rho \Pr[ \text{$\mathcal{R}$ fails} \mid R=\rho] \Pr[ R=\rho ] \\
&\ge p \sum_\rho \Pr[ R=\rho ] = p.
\end{align}
For the inequality, I used the fact that once we have fixed $R = \rho$, we effectively have a deterministic algorithm.
I can't find the flaw in my reasoning, but I would be quite surprised if this implication is true indeed.


texts: Hardness and approximation of a problem with a parameter

texts:
Let $H$ be a decision problem, where we are given an integer $k$ and some object, say a graph or a formula. We know that $H$ is NP-complete for $k \geq c$, where $c$ is some constant like 3 ($H$ could be $k$-SAT, or $k$-vertex coloring, or something like that).

I have a problem $X$ I think is NP-complete as well, and I want to prove it. $X$ is a graph problem, and it has a parameter $k'$ similarly.

Given an instance of $H$ with parameter $k \geq c$ (for example let's say $c=3$), I can build an instance of $X$ (in polynomial time), where $k' = c+8$. I can now prove two things:

If $H$ with $k$ has no solution, $X$ has no solution with $k$. (There might be a solution for $X$ with $k'$, I don't know).
If $H$ with $k$ has a solution, $X$ has a solution with $k'$.

To establish hardness for $X$ with $k'$, should I be able to prove in (1) that $X$ has no solution with $k'$ as well? (Or is my current reduction pretty much useless as it is?) If I were able to do that, would my proof also tell me something about the hardness of approximating $X$? $X$ is a minimization problem.


texts: Single tape Turing Machine that accepts string with at least five G's and at most three T's?

texts: I am looking to create a single tape acceptor Turing machine acting upon the language of any ASCII string, that would only accept strings that contains at least five G's and at most three T's, and rejects any other ASCII string input. I am kind of stuck on how the machine would know that it had encountered greater than or equal to five G's and less than or equal to three T's.


texts: Converting a non-deterministic context free grammar to deterministic

texts:
I have the non-deterministic context free grammar $$I \to abcX | abdY$$
$$X \to X d | \epsilon$$ $$Y \to XX |I$$ and i want to convert it into a deterministic. I know that the rules $I \to abcX | abdY$ and $X \to X d | \epsilon$ are causing the grammar to be non-deterministic so i rewrite them as $$I \to abI', \ I' \to cX | dY $$ and $$X \to \epsilon X', \ X' \to dX' | \emptyset$$ respectively, however a hint in this exercise tells me that the rule $$Y \to XX| I$$ has also a problem (causes the grammar to be non-deterministic) however i can't see why this is the case, can you explain why there is a problem with this rule, and how can i fix it?


texts: Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup

texts:
I tried to prove that the following language is recursive: for $\Sigma=\{0,1\}$, $k$ a positive integer:
$$
L_k= H_{\mathrm{TM},\varepsilon}\cap \Sigma^k
$$
where $H_{\mathrm{TM},\varepsilon}=\{\langle M\rangle\mid M \text{ is a TM that halts on an empty input}\}$

It is easy to prove because $L_k$ is finite, but I didn't notice this and tried to prove it by finding a decider TM for it.
I thought that since the encoding of the TM is of length $k$ then it can't have more than $2^k$ states, and by running it on epsilon for $2^k$ steps, if it halts by then than accept otherwise reject.
I was told that it's incorrect - is it a wrong solution. How can I prove this using this method (and not the way I mentioned about $L_k$ being finite)?


texts:
How to do or implement Lambda Calculus in a Rewriting systems?

Rewriting systems are Turing complete.

But I can't figure out how to do lambda calculus or functions with them.


texts: Can given grammar be parsed using recursive descent?

texts:
I have this Grammar below:
Expr ::= Term "(" Term ")"

Term ::= Ident | "(" Expr ")"

Start symbol: <Expr>
Terminal symbol: Ident ::= [a-z]+

And I wonder if it is possible to construct a recursive descent parser for grammar G2?
I think this won't be able to do that?


texts: Are there any CS-trees named after flora-trees?

texts:
This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real world?

In computer science we have red-black trees, B-trees, quadtrees, and so on. In the biological sense of the word tree, we have palm trees, pine trees, redwood trees, etc.

My question: is there a word $w$ such that a $w$ tree could refer to a physical tree in the real world, or a mathematical object?


texts: Does the 3SAT problems have to have consistent operators?

texts:
What are the rules pertaining to 3SAT as to the actual boolean equation?

The main thing I do not understand is in a given boolean expression within a single clause can you have both AND + OR operators i.e. (x1 & x2 | x3) or do they have to remain consistent i.e. (x1 & x2 & x3) or (x1 | x2 | x3)?

That being said when connecting clauses together do the boolean operators have to be consistent?

i.e. (x1 & x2 & x3) & (x1 & x2 & x3) & (x1 & x2 & x3)

or

i.e. (x1 & x2 & x3) | (x1 & x2 & x3) | (x1 & x2 & x3)

or can they be mixed up like

i.e. (x1 & x2 & x3) | (x1 & x2 & x3) & (x1 & x2 & x3)

or

i.e. (x1 & x2 & x3) & (x1 & x2 & x3) | (x1 & x2 & x3)

Can a 3SAT problem just be a huge jumble of different logic operators or do they have to remain consistent throughout the equation? Ever example I have seen has consistent operators and I cant seem to find the answer to the question anywhere.


texts: Polynomials - using Newton's method, or not?

texts:
I have to find a root of polynomial of degree $n\ge2$. I need to write code to calculate the root for different values of $n$. Only 1 real positive solution is needed.

I can use general Newton's method for all degrees, or only for 5th+, and for 2,3 and 4 I can use algebraic formulas that solve quadratic, cubic and quartic equations. Since algebraic formulas need to use sqrt, acos and similar functions - does it make sense at all to use algebraic formulas - or is it better to use Newton's method for all degrees? I guess the latter will actually be faster?

This is my equation:

$$\frac{1}{(b_1x + 1)} + \frac{1}{(b_2x + 1)} + ... + \frac{1}{(b_nx + 1)} -k = 0$$

and constraints:

$$1 \leq k<n \\ b_n>0 $$

e.g. for $n=3$:

$$b_1 b_2 b_3 (-k)x^3 +\left(b_1 b_2+b_3 b_2+b_1 b_3- b_1 b_2 k-b_3 b_2 k-b_1 b_3 k\right)x^2 + \left(2 b_1+2 b_2+2
   b_3-b_1 k-b_2 k-b_3 k\right)x + 3-k =0$$

which can be written as

$$\sum_{i=0}^n(n-i-k)\binom{\{b_1,...,b_n\}}{i}x^i=0.$$


texts: finding common navigational paths / central nodes within a graph

texts:
I have a directed weighted graph representing street (edges weighted by distance) and street intersections (nodes).
Using this graph, I would like find central nodes that a person might find themselves traveling between. For example, I would expect nodes near bridges to have high centrality.
What algorithms might I use to find key route-planning nodes in < O(n^2)?
This excludes betweenness centrality, though, some sort of modified betweenness centrality might be possible


texts:
I seek the neural network (NN) which satisfies the 100 equations (i=1,2...100)

$\sum_{j=1}^{2000} NN(A_{ij},B_{ij},C_{ij})=Q_i$.

Where A,B,C are 100x2000 matrices

So I know Q, A, B and C
How can one find the NN? (ie train it using this data)
I have a second datset to test it on.
I also have MATLAB neural network toolbox, but that is not a necessity for me to use that.


texts:
I'm stuck on the following question:

How to prove the linear context free languages are closed under gsm mapping?


texts: Why does symmetric starting patterns end up in symmetric ending structures?

texts:
Why every symmetric starting structures in the "game of life" end up to be symmetric as well / disappear completely?
For example:

Becomes:

A lot of examples can be made ...


texts: Prove that $ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $ is $O(5^n)$

texts:
I need to prove that the following recurrence relation is $O(5^n)$:
$$ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $$
And $T(n)=\Theta(1)$ for $n\le 9$.
I am trying induction, and proving that there exists $c$ such that $T(n)\le c\cdot5^n$, but I am stuck at the induction step:
$T(n)=5^n+3T(\big\lfloor n^\frac{2}{5}\big\rfloor)\le5^n+3c\cdot 5^{\lfloor n^\frac{2}{5}\rfloor}\le5^n+3c \cdot 5^{n^{\frac{2}{5}}}=\bigg(1+\frac{3c}{5^{n- n^\frac{2}{5}}}\bigg)\cdot 5^n$.
How can I continue in the induction (turn the parenthesis into the constant $c$)?


texts: Maximum Query String Length in Oracle Turing Machines

texts:
I am learning oracle Turing machines, which is normal Turing machines equipped with a write-only query tape and with access to a query oracle.

My question is, is there a limit of the content that can be written on the query tape?

Here is my try: Suppose the oracle Turing machine is $S(n)$ space-bounded. Then the machine either stop within $2^{O(S(n))}$ steps or loops forever. At each step, the machine can write one symbol to the query tape. So the length of the query content is either no more than $2^{O(S(n))}$ or infinity. (For time-bounded oracle Turing machines, it is trivial.)

I think it is the case, but I am not sure. Also, I couldn't find any information about the size of the query content. Am I correct?

The model I use is similar to the one defined in the book Computational Complexity: A modern approach, namely,

  (Oracle Turing Machines) An oracle Turing machine is a TM $M$ that has a special write-only tape we call $M$’s oracle tape and three special states $q_{query},q_{yes},q_{no}$. To execute $M$, we specify in addition to the input a language $O \subseteq \{0,1\}^∗$ that is used as the oracle for $M$. Whenever during the execution $M$ enters the state $q_{query}$, the machine moves into the state $q_{yes}$ if $q \in O$ and $q_{no}$ if $q \notin O$, where $q$ denotes the contents of the special oracle tape. After the query, the query tape initialised to a blank tape. Note that, regardless of the choice of $O$, a membership query to $O$ counts only as a single computational step. If $M$ is an oracle machine, $O \subseteq \{0, 1\}^∗$ a language, and $x \in \{0,1\}^∗$, then we denote the output of $M$ on input $x$ and with oracle $O$ by $M^O(x)$.


texts:
Is there any problem that can be only solved with recursion, and not with iteration? (haven't been able to find anything online).

If there isn't any, is there a reason why?

Thanks in advance!


texts: How to efficiently select the initial node to start a search in a Skip Graph

texts:
Checked out a few papers on Skip Graphs:

Locally Self-Adjusting Skip Graphs
Adaptive Probabilistic Skip Graphs
Skip Graphs
Family Trees

All of the insertion/deletion algorithms assume that you have selected a start node to begin the search. However, it is not described how the start node is selected. In doing some initial exploration into how to do this, I start thinking in terms of the following:

level1nodechunk1 = count next node node node ....
level1nodechunk2 = count next node node node ....
...

Basically, a level is just a bunch of nodes:

node node node ...

If you are to randomly select a starting node, and they are not contiguous in memory, then you have to navigate your way there. So instead of going one node at a time, I group it into chunks for the particular level, and specify the count and next so you can jump ahead to the next one if desired.

So say you generate a random number x = random num between 0 and totalnodecount. Say it is 20 and each level chunk has 5 nodes. Then you would do:

level1nodechunk1 = [count] [next] (5)
level1nodechunk2 = [count] [next] (5 + 5 = 10)
level1nodechunk3 = [count] [next] (10 + 5 = 15)
level1nodechunk4 = count next node node node node [node5]

You would jump over chunks 1-3 and get to chunk 4, see it has 5 contiguous nodes, and jump to that one. So it's just ~5 instructions instead of 20 (one per node) roughly.

But the problem is if you have 1 billion nodes. Then if each one is only 5 nodes, then you have 200 million chunks, so ~200 million instructions. So maybe you make the chunks to be 10,000 nodes each, that's still 100,000 instructions to find the start node.

I'm wondering how they do this efficiently.

If all the nodes were contiguous then it would be easy, $O(1)$ lookup by index. If you hardcode a chunk count so we only have say 20 chunks, no matter how many nodes, then you have to account for the worst case of lets say 1 billion nodes. So that means each chunk is 50 million nodes. But if you have only currently used 10 nodes out of 1 billion, then that's tons of wasted memory reserved.

The only other thing I can think of is that the start node is always the actual first node in the lowest level of the skip graph, then you navigate to the top-level for that node and work your way back down.

IIRC, the reason to "randomly" select a start node is to prevent hotspots.

Another possible solution is to cycle through the level 0 nodes. Basically:

Start at the start level 0 node.
Cache the next node it points to as the future start node.
Next query, the start node is that cached node. Then set next node to its pointer, etc.

But that would give preference to the first nodes more than the last (i.e. it's not random).


texts: How to find the path for the most negatively-weighted cycle which goes through a specific source node?

texts:
I am trying to find the path for the most negative cycle in a graph G which starts and ends at a specified source node S.

I have studied an application/ extension of the Bellman-Ford algorithm (henceforth referred to as the "Huang algorithm") found here which describes how to find a negative cycle reachable from a specified node. However, this does not ensure that the "full cycle" going from S -> cycle -> S is negative.

Here is my current research into this topic:

On the nth iteration of the Bellman Ford algorithm, if an edge can be relaxed, then the graph contains a negative cycle. Using the Huang algorithm I can retrace the path of the negative cycle through the predecessor dictionary until a vertex repeats. When a vertex repeats, I cease iterating over the predecessor and now have my path for the negative cycle. However, the source vertex is often not in this path. I believe it is also sometimes not the most negatively-weighted path.

I would like to find the most negative cycle of which S is a part. (This can include a cycle with a subcycle detected by the Huang algorithm)


texts:
My goal is to understand the exact differences between SoEMT, SMT and "time-slice multi threading".

Thus far I already found information on SoEMT and SMT and it does not seem to hard to find more on google. However my problem is: Time-slice multithreading. The best I found - apart from a long winded book, was:

– Processor switches between software threads
after a predefined time slice
– Can minimize the effects of long lasting events
– Still, some execution slots are wasted
For Time-slice multithreading I found:

However, this doesn't really go into detail how this things are achieved, for what purpose, its pros, cons and implementations etc.

I would thus be quite happy, if someone knew a good resource, that read up further on that topic. Bonus, if it also compares SoEMT, SMT. As always thanks in advance.