texts: Is this formal grammar context-free (CFG) but not context-sensitive (CSG)?

texts:
I have the following formal grammar: $$G= (\{S,A,B\},\{a,b\},R,S)$$ $$R=\{S \rightarrow A\ |B, A \rightarrow \varepsilon\ | aA\ |bA, B \rightarrow \varepsilon\ |Bb\ | b\}$$

Now, we see, the production rules $A \rightarrow \varepsilon$ and  $B \rightarrow \varepsilon$ implies that this grammar is not context-sensitiv ($CSG$). But on the other hand, we see this grammar satisfies the conditions for a context-free ($CFG$) grammar, because every production rule has just one NON-terminal on the left side.

We know, according to the Chomsky hierarchy, a contest-free grammar imples a contest-sensitive grammar: $CFG \implies CSG$

Now i am confused, is my grammar context-free or it is not, even if it satisfies the conditions? Can it be $CFG$ without being $CSG$?


texts: New Idea for accessing memory across an inter-network connected system

texts:
I have the following idea for a network-based operating system.

Suppose we have two computers A and B in a network. If computer B wants to access the memory of computer A, it can access by using the following addressing method which uses Media Access Control (MAC) address of the machines,

(MAC Address of target machine).(memory address on target machine)

This should work both ways as well as all the computers connected in a network. This will also remove the constraint of passing reference of variables in Remote Procedure Call (RPC).

Is the above method feasible ? What sort of modifications are required to make this possible, if feasible ?

NOTE:-I am also assuming that there is no MAC spoofing.


texts: NFA that accepts all numbers not divisible by 105

texts:
I have to create an NFA that accepts the following language L with no more than 15 states.

$L = \{a^n \mid n \geq 1$ and $n \mod105 \neq 0 \}$.

To me it seems that all multiples of 105 have the same properties:

sum of digits is divisible by 3
the last digit is 0 or 5

I would appreciate if someone could help me here.


texts: Algorithm to compute average length of a simple path

texts: Given a connected graph and two nodes s and t, there can be many different simple paths (without cycles) from s to t.  Is there an efficient algorithm to find the average length of these paths?


texts: If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?

texts: Many seem to believe that $P\ne NP$, but many also believe it to be very unlikely that this will ever be proven. Is there not some inconsistency to this? If you hold that such a proof is unlikely, then you should also believe that sound arguments for $P\ne NP$ are lacking. Or are there good arguments for $P\ne NP$ being unlikely, in a similar vein to say, the Riemann hypothesis holding for large numbers, or the very high lower bounds on the number of existing primes with a small distance apart viz. the Twin Prime conjecture?


texts: Difference between Elman, Hopfield & Hemming Recurrent Neural Networks

texts:
What is the main difference between Elman, Hopfield & Hemming Recurrent Neural Networks?

Python Neurolab Library examples:

Elman Recurrent Neural Network
Hopfield Recurrent Neural Network
Hemming Recurrent Neural Network

I properly understand the main difference of Hopfield Network:

  The Hopfield network is of historic interest although it is not a
  general RNN, as it is not designed to process sequences of patterns.
  Instead it requires stationary inputs. It is a RNN in which all
  connections are symmetric. Wikipedia

But the other two is missing for me.


texts:
2-SAT is unsatisfiable iff it contains unsatisfiable XOR-2-SAT.

So, first, we just need to combine every clause that contains share same variables (both of them). Then, all of those which remain uncombined are "uninteresting" (don't affect satisfiability).

Example:

$\Phi = (x \lor y) \land (\overline x \lor \overline y) \land (x \lor \overline z)\land(\overline x \lor z)\land (\overline y \lor z)\land (y \lor \overline z)\land (z \lor t)$

Now I can replace this formula by equisatisfiable (under log-space reduction):

$\Phi' = (x \oplus y)\land(x \oplus \overline z)\land(y \oplus \overline z)$

As you can see, clause $(z\lor t)$ was removed as "uninteresting".

Ah, well, I need to see if there are cycles in implication graph. So, finding a cycle in directed graph that contains two given vertices is $\mathsf{NL}$-complete problem, right?


texts: Why can't OSes swap out processes that are waiting for I/O?

texts:
In the book, Operating System Concepts, 9th Edition, there is this paragraph that I don't quite wrap my head around.

  Swapping is constrained by other factors as well. If we want to swap a
  process, we must be sure that it is completely idle. Of particular
  concern is any pending I/O. A process may be waiting for an I/O
  operation when we want to swap that process to free up memory.
  However, if the I/O is asynchronously accessing the user memory for
  I/O buffers, then the process cannot be swapped. Assume that the I/O
  operation is queued because the device is busy. If we were to swap out
  process P1 and swap in process P2, the I/O operation might then
  attempt to use memory that now belongs to process P2. There are two
  main solutions to this problem: never swap a process with pending I/O,
  or execute I/O operations only into operating-system buffers.
  Transfers between operating-system buffers and process memory then
  occur only when the process is swapped in. Note that this double
  buffering itself adds overhead. We now need to copy the data again,
  from kernel memory to user memory, before the user process can access
  it.

This is quite a handful for me to swallow for now. I have a lot of questions.

What are I/O buffers? Are they located in the I/O device?
How and why does the I/O asynchronously access user memory?
Why would an I/O operation attempt to use P2 memory when P1 gets swapped with P2?

To probably generalize my questions, why shouldn't we swap processes with pending I/O? If we do so, would there be memory corruption or segmentation faults?


texts: What is a conventional format for presenting algorithms?

texts:
I'm writing a technical paper and the review committee wants my methodology to be represented in a conventional algorithm format.

I've been searching all over the web for the conventional structure of an algorithm with little luck. Can someone tell me the conventional format of an algorithm or any specification from IEEE for writing algorithms?


texts: What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages

texts:
I've looked around the net for an answer to this question and it seems as if everybody implicitly knows the answer except me. Presumably this is because the only people who care are those who have had tertiary education on the subject. I, on the other hand, have been thrown in the deep end for a high school assignment.

My question is, how exactly are programming languages related to formal languages? Everywhere I read, something along the lines of "formal languages are used for defining the grammar of programming languages" is said.

Now from what I've been able to gather, a formal language is a series of production rules that apply to a specific set of symbols (the language's alphabet). These production rules define a set of transformations, such as:

b -> a

aaa->c

This can be applied such that:

abab->aaaa aaaa-> ca

Just as a side note, if we define that our formal language's alphabet as {a,b,c}, then a and b are non terminals and c is terminal as it can not be transformed (please correct me if I'm wrong about that).

So given all that, how on earth does this apply to programming languages? Often it is also stated that regex is used to parse a language in it's text form to ensure the grammar is correct. This makes sense. Then it is stated that regex are defined by formal languages. Regex return true or false (in my experience at least) depending on if the finite state automata that represents the regex reaches the goal point. As far as I can see, that has nothing to do with transformations*.

For the compiling of the program itself, I suppose a formal language would be able to transform code into consecutively lower level code, eventually reaching assembly via a complex set of rules, which the hardware could then understand.

So that's things from my confused point of view. There's probably a lot of things fundamentally wrong with what I have said, and that is why I'm asking for help.

*Unless you consider something like (a|b)*b*c->true to be a production rule, in which case the rule requires a finite state automata (ie: regex). This makes no sense as we just said that


texts: What does the processor do while waiting for a main memory fetch

texts:
Assuming l1 and l2 cache requests result in a miss, does the processor stall until main memory has been accessed?

I heard about the idea of switching to another thread, if so what is used to wake up the stalled thread?


texts: Why isn't energy wasted with reversible computing? Isn't information discarded when we feed the function with a new input?

texts: I understand that irreversible computing consumes energy because it has to "get rid" of outputs which have been used. With reversible computing that information is not "wasted" because with the outputs we can calculate the inputs again. But what happens after that? Is there a endless loop of back-and-forth calculation input -> output, output -> input? And what happens when we want the gate to calculate the output of some other inputs? Won't it have to discard the previous input/output which leads to the same information/heat dissipation?


texts: Least constraining value heuristic in Sudoku

texts: I was trying to implement Least Constraining Value Heuristic in Sudoku but wasn't getting the idea on how to do it. Can someone share their idea for the same ?


texts: Generating sparse connected Erdős–Rényi random graphs

texts:
Given a random graph $G(n, p)$, where $n$ is the number of nodes and $p$ is the probability of connecting any two edges, it is known that $t = \frac{\ln(n)}{n}$ is a threshold for the connectedness of the graph: if $p$ is greater than $t$ the graph will be almost surely connected, otherwise disconnected. The farther you move $p$ from the threshold the higher the chance that the resulting graph will be disconnected/connected (source: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model).
I am currently trying to output from an Erdős–Rényi process a graph that is as sparse as possible. In my case $n=10000$ and therefore $t=0.00092$, which means that a connected random graph of 10000 nodes should have on average 46000 edges. Through testing with igraph I could go as low as 37000 edges: $t=0.00074$. Now I'm stuck (because the probability of outputting a sparser graph is too low) and I don't know how to further lower the degree of the graphs. Is there a way to generate sparser random graphs? I know I'm already far below the threshold. In case no solution is found for this model what is the best way to generate a very sparse connected graph?


texts: Is the prime factorization problem not an instance of the change making problem?

texts: When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can be used to make the total. But then the change making problem is listed as non NP problem, but the prime factorization problem is found to be NP complete. Can anyone explain why this is?


texts: I am studying DFA's, but I've been struggling to find an explanation of what does the final state mean? I know that it is indicated by double circle on the graph, but what does it imply?


texts: computer vision - How to construct a 3d map?

texts:
I have some good basics -I think- in computervision (using openCV) and am considering to build a quadcopter to create a 3D maps while flying.

I would like to place a camera on each side of the quadcopter (ie, left, right, front and back) to continuously provide +/- 360 degrees images. Then stitch those four images together to get a -roughly speaking- 360 degree view.

I know that slam very often used for this types of things.
However I am kind of lost on where would be the best place to start and what algorithms I should look at.

What algorithms should I read about in order to be able to do this?

What would be the easiest way to proceed?

(The endgoal would be to eventually do object tracking in this 3d map)

Thanks


texts: Determining the optimal threshold value for a one-dimensional decision stump classifier

texts:
I'm currently trying to find an efficient algorithm to solve a discrete optimization problem that arises when constructing decision trees. The problem is as follows:

Say we are given $N$ ordered data points on the real line: $x_1,\ldots,x_N \in \mathbb{R}$ such that $x_1 < x_2 < \ldots < x_N$.

Each of the points $x_i$ has a label $y_i \in \{0,1\}$. We are asked to predict this label using a decision stump classifier, $h(x;t) = \mathbb{1}[x>t]$. The decision stump classifier predicts $\hat{y}_i = 1$ if $x_i > t$. Thus, the accuracy of this classifier depends on the threshold parameter $t$.

I am looking for an efficient algorithm to determine the value of $t$ that maximizes the number of correctly classified points. That is, solve the problem:

$$\max_{t\in\mathbb{R}} A(t)=\sum_{i=1}^N \mathbb{1}[y_i=0]\mathbb{1}[x_i\leq t] + \mathbb{1}[y_i=1]\mathbb{1}[x_i>t]$$
Some insights:

Since there are $N$ data points, we only need to consider $N+1$ values of $t$. These are values that lie in the $N+1$ intervals $(-\infty,x_1), [x_1,x_2),\ldots, [x_{N-1},x_N), [x_N,\infty]$.
When $t < \min_{i}x_i$, the decision stump predicts $\hat{y}_i=1$ for all $i=1,\ldots,N$. Here $A(t) = \sum_{i=1}^N{\mathbb{1}[y_i=1]}=N^+$.
When $t \geq \max_{i}x_i$, the decision stump predicts $\hat{y}_i=0$ for all $i=1,\ldots,N$. Here $A(t) = \sum_{i=1}^N{\mathbb{1}[y_i=0]}=N^-$.
The number of correctly classified points $A(t)$ can be decomposed as $B(t)+C(t)$, where
$$B(t) = \sum_{i=1}^N{\mathbb{1}[y_i=0]\mathbb{1}[x_i\leq t]}$$
is the number of correctly classified points with negative labels and
$$C(t) = \sum_{i=1}^N{\mathbb{1}[y_i=1]\mathbb{1}[x_i>t]}$$
and the number of correctly classified points with positive labels. Note that $B(t)$ is monotonically increasing in $t$ while $C(t)$ is monotonically decreasing in $t$.


texts: Axiomatisation in the presence of recursion

texts:
I read Klaus Havelund's thesis on the Fork Calculus:

http://havelund.com/Publications/thesis.ps

He develops the Fork calculus for reasoning about concurrent functional programs, the motivation being Concurrent ML.

In chapter 5, he writes:

First, we add a recursion operator, allowing us to define processes
with infinite behaviour. Recursion is not difficult to deal with
(thanks to the use of operational semantics), except that the
axiomatisation cannot be shown complete in presence of recursion.

There is no literature reference here, so I ask you: where can I read about why recursion makes a programming language's axiomatisation cannot be proved complete, and in precisely what meaning?


texts: What would be some implications of $NL$$=P$? Would it be possible to get recommendations on good sources/papers I can read to learn more about this? Thank you


texts: How does an automaton actually "compute"?

texts:
In my studies in computability I have come across the notion of the "machine", an abstract representation of a device that essentially computes. I have read about Turing Machines and Wolfram's binary cellular automata and I understand them.ie. the rules, states, colours, etc. and how they work. They begin in some state and run forever(unless a terminating state is specified). The point I'm trying to make here is that they receive no external input and are essentially functions of themselves:their current state is some function of its starting state, unlike realistic computers.

For the above reasons I'd like to know why automata are used to represent computers. More generally how can a machine be used to represent a computation?


texts: Secretary Problem with 2 positions - Maximizing the difference

texts:
Synopsis

Imagine the secretary problem, except the goal is to hire two secretaries with the greatest possible difference between the two.

The Problem

I'm not particularly comfortable with this type of math so below are the modified constraints. The original constraints are from Wikipedia's page on the secretary problem.

There are 2 positions to fill
There are n applicants for the positions any applicant may fill any position, and the value of n is known.
NOTE: It is fine to put one person in both positions, but wouldn't be the optimal solution unless n = 1.
The applicants, if seen altogether, can be ranked from best to worst unambiguously.
The applicants are interviewed sequentially in random order, with each order being equally likely.
Immediately after an interview, the interviewed applicant is either accepted or rejected, and the decision is irrevocable.
The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
The objective of the general solution is to have the highest probability of selecting a pair with the greatest difference read (The best and the worst). This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant/worst applicant pair and zero otherwise.

For Context

I realized that at work that many of the problems I'm working on at the moment are normally treated as a single optimization problem. However in reality they are pair values, and since the goal is often to maximize the distance between choosing two values over a given number of days it seems to be very close to the secretary problem. I'm not comfortable enough yet with the math to solve this myself. My intuition is that this problem is equal to having two instances of the stopping problem however I'm not sure if this is mathematically equal.

Research

I've found papers on the Secretary Problem for TradeOffs, IE. The secretary's are evaluated on two rankings, and Random Walk, IE. dependent variables, while trying to answer this question. I have not managed to find anything directly related to this variant of the problem.

Answers

Thank you for reading my problem. Any insight into solving this problem is appreciated!


texts: Find the bitwise AND of a subarray closest to given number

texts:
It was a question I was asked in an online assessment for a company.
Please help me in this question-

Given an array, $A$ of size $N$ and an integer $P$ , find the subarray $B = A[i \dots j]$ such that $i \leq j$ and compute the bitwise value of subarray elements i.e say $K = B[i] \mathbin{\&}B [i+1] \mathbin{\&} \cdots \mathbin{\&}B[j]$.
Output the minimum value of $|K-P|$ among all values of $K$.
Size of array: $1 \leq A.\mathrm{size} \leq 100000$
$0\le A[i]\le 10^8$

I could only think of brute force.


texts: Can all optimizations be expressed in source code?

texts: If someone compiled a program with all optimization settings enabled, would it be possible to create source code that, if it was compiled with all optimizations disabled, produced an identical binary? We'll assume that inline assembly and similar features are not used. If this is not always possible, (and I suspect it probably isn't) what language features or particular types of compiler optimizations make "fully pre-optimized" source code impossible?


texts: Why the negative reward function in linear quadratic regulation encourage to be at original state?

texts:
I was reading Stanford's CS 229 materials on Linear Quadratic Regulation ( Lecture note 13, youtube Lecture 18, around time 36 min).
And it mentions that:

" the quadratic formulation of the reward is equivalent to saying that we want our state to be close to the origin.For example, if $U_t = I_n $(the identity matrix) and $W_t = I_d$, then
$R_t = -\Vert(s_t)\Vert^2-\Vert(a_t)\Vert^2$, meaning that we want to take smooth actions (small norm of $a_t$) to go back to the origin (small norm of $s_t$)."

but why is that? Why the norm of the origin is smaller? $s_t$ for any time point are just a vector of n dimension which can take any value, right?


texts:
I read that recursive definitions, refer to the definition of a function in that function body, cannot be done in $\lambda$-calculus, but recursion can be achieved by using $Y$ combinator.

As I know, nominal logic is the theory of handling bindings. So wondering how it handles recursive definition  of functions? Does it still use combinators as it is done in $\lambda$-calculus? nominal logic

I think higher-order abstract syntax takes the same approach taken by $\lambda$-calculus, since it is based on $\lambda$-calculus. am I right?

If there is a good technique for handling recursive definition different than using a combinator as mentioned above, Please point it out. I want to know.
What is the common  way to handle recursion?

Could anyone clarify these to me, please?
Thanks in advance.


texts: Math behind leetcode problem 47 permutations II

texts:
Please tell me why the expression i>0 && nums[i] == nums[i-1] && !used[i-1] works on getting unique permutations. And what is the math behind it?
The problem is as follows:
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Here is the code:
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> temp;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtrack(nums, temp, result, used);
        return result;
    }

    void backtrack(vector<int>& nums, vector<int>& temp, vector<vector<int>>& result, vector<bool>& used){

        if(temp.size() == nums.size()){
            result.emplace_back(temp);
        }else{

            for(int i=0; i<nums.size(); i++){
                if(used[i] || i>0 && nums[i] == nums[i-1] && !used[i-1]) continue;
                used[i] = true;
                temp.push_back(nums[i]);
                backtrack(nums, temp, result, used);
                used[i] = false;
                temp.pop_back();
            }
        }
    }
};


texts: Making a career in CS vs Software engineer

texts:
this might be a bit philosophical question , but i haven't really gotten a good answer.
Theoretical computer science vs Software engineer / developer whatever, which one is better for making good money.

I love maths and theoretical computer science. I am very ambitious, slightly arrogant guy from Estonia. I am first yeah Bachelor student, but I don't know where to go from here. I study a lot and i want to be successful and the best at what i do, so all tips are welcome if you think of something that could help me.
I think 95 % or more of my coursemates don't like maths, they just like programming. I minor in mathematics also , i understand it well and i am the best out of 160 persons in maths. I have done some projects in CS and it is okay, i kind of like it,but i feel like it's not my calling.

I also always look for business oppurtunities, have failed 2 or 3 projects due to funding and other reasons, i won't go into that right now.

My second question is : What CS field i should focus on ? Right now i am thinking of parallel computing, computational neuroscience, artificial intelligence and cryptography. I think these are the fields where i might make some money.

If people ask me where do i see myself in 10-20 years, i usually say that i will be my own employer or something. I understand maths very well and i study it a lot. I also study electrical engineering, chemistry , physics at introductionary level, for fun :). (From coursera, mit open courseware and so on ... ).

My third question is : What I should study to make something innovative in the future, that is high end ? ( this is why I study physics and electrical engineering )

Fourth : Is there a theoretical CS field that I could make my own start-up on ?

Sorry for bad English , I'm learning it also right now :)


texts: find all paths between two nodes in a Directed acyclic graph

texts:
Given a directed a-cyclic graph G (unweighted), give algorithm which count all the   paths from node s to node t, and calculate the run time complexity.

so I thought about the naive way to do this :
1)hold a counter (counter=0 at beginning) and start from vertex 's', loop through all 's' neighbors.
2) if one of the neighbors is 't', we increase counter +1 and function will end. else if it is not 't' but has neighbors continue recursively with 's' neighbor , otherwise function will end without changing counter value.

my problem is that i'm very confuse about run-time of this function and about the  efficiency (I suppose it is very uneffiecent).
I thought about using memorization, so that I would hold an array of all the vertex, and each index will represent the sum of the paths between vertex 'i' to. 't' but also here i'm  very confused with the implementation and run time.

it will be great if some could help me with figuring out the run time of my suggestion (and the memorization idea also), and if there are another ideas to implement it efficiency it will be great .

thank you.


texts: Time complexity by solving recurrence relation

texts:
I was working on recurrence relation and came across this example

T(n) = 2T(n/2) + log(n)

What will be the time complexity, ie, big O for this relation.

Thanks for any help in advance.


texts: how to make a Turing machine of a cipher?

texts:
For example, lets consider the simplest model of cipher: the Caesar cipher. According to the theory I read the Caesar cipher consist in substitute a letter by another in considering a shift in an alphabet given by a certain number.

I know that a Turing machine consist of: a tape, a header that writes or reads information from that tape, and a set of states that consist in moving to the left or right on the tape. Also the initial state and the final state and reject states.

So if I would like to make a TM that accept the Caesar cipher I suppose that the information that would be on the tape, for example, the message "hello", that I want to convert to a cipher text by a shift of n=3 in each character so I will get the word "khoor".

Because I need to put that message on a TM tape I guess that I can convert it into a binary string, would that be necessary or can I work with original characters?

For example if my TM tape look like this (I am supposing that "h" is 0011 and that "k" is 1010 for example):

|0|0|1|1|e|e|e|e|

where e is the empty character and the header is in the leftmost position pointing to 0, so if I want to convert this "h" into "k" I can read one by one each binary digit (from left to right), converting into its corresponding binary digit to the converted letter and writing it in some beginning position at the right. Would that be ok? So I will have something like:

|e|0|1|1|e|1|e|e|

After the first iteration, I have read the leftmost digit, 0, changed into 1 and then copy it after the empty position. I can do the same with all the remaining digits.

Would that approach be good enough, in this case, to simulate the Caesar cipher in a TM, and also if I want to decipher the converted text can I do a similar process?

Bottomline, maybe somebody could show a model for a Caesar cipher using a TM?

Thanks for your help.


texts: Running Time of Ford Fulkerson where all edges have equal capacity

texts:
My intuition says it would simply be the number of edges leaving s.
I'm assuming it's a valid flow network so sum of capacities leaving s is the same as the sum of capacities entering t, so a max flow exists.

This variation simplifies the running time because for any augmenting path, we can add the same amount of positive flow which is equal to any original edge capacity. So no edge leaving s would get used twice and the runtime is simply how many edges leave s.

I think that makes sense, but maybe I'm missing something...


texts:
how can I know what are the recursive calls of this algorithm ?
in line two there are 2 recursive calls and I don't know how to write this as T(n) for the Recurrence relation.
Here is the algorithm :


texts: Correlation between high cpu/ram usage and poor computer performance

texts:
I'm researching electromigration and the effects of high cpu/ram usage on a computer.

There are tons of discussions on these topics taking place via forums and message boards, but I am looking for credible sources that are backed by metrics.


texts: How to show that the set of TMs that accept languages of size two is recognizable?

texts:
I know how to show $\overline{Lx}$ is unrecognizable.
I know how to show Lx is undecidable.

I would like the mapping reduction function that shows that Lx is recognizable or unrecognizable.

For instance, to show $\overline{Lx}$ is unrecognizable, show $\overline{Htm}$ <= $\overline{Lx}$

Given $\overline{Htm}$ = {M description: M is a TM and M loops on ''}

def R(<M>):
    def N(x):
        M('')
        if x == 0 or x == 1 then accept
    return <N>

  If M is in $\overline{Htm}$ then M loops then N will not accept any strings then
  |L(N)| = 0 then N is in $\overline{Lx}$

  if M is not in $\overline{Htm}$ then M halts then N
  will accept either 0 or 1 so |L(N)| = 2 then N is not in $\overline{Lx}$

I would like a similar proof to show that Lx is either recognizable or unrecognizable.


texts: Closure of regular Language - Transition Function : Sipser Proof

texts:
I was going through construction proofs for closure of regular languages under union, star and concatenation operation in the book: "Introduction to Theory of Computation" by Michael Sipser.

I have doubts regarding how he wrote the transition function.

When $Q \in F_1$ and $a=\epsilon$ he wrote $\delta_1(q,a) \cup \{q_2\}$. I couldn't understand why its so. When the input is epsilon, the state moves to $q_2$ and what is the need for writing that $\delta_1(q,a)$

Also if that is so, the $A^*$ example he wrote for the transition function $\{q_1\}$ only  when $q=q_0$ and $a=\epsilon$


texts:
In my code i want to solve the Fermi-Dirac-Integral numerically. This can be achieved with a Polylogarithm.

Actually I'm coding in C#, so my function to calculate this polylogarithm looks like that:

public double PolyLog(double s, double z)
{
    double sum = 0;
    for (int k = 0; k < 1e5; k++)
        sum += Math.Pow(z, k) / Math.Pow(k, s);
    return sum;
}

This actually does it's job pretty well for values |z| < 1.
However, I need to calculate the polylogarithm also for values that are bigger than 1.

Is there any code, that calculates polylogarithms for |z|>1?
Probably this would be done by any kind of analytic continuation.
Although, I'm using C#, I don't care about the language. I can easily translate any code to C#.


texts: Is the complement of $L = \{a^nb^mc^p \, n= m= p\}$ context free language?

texts:
Is the complement of $L = \{a^nb^mc^p \ , n= m= p\}$ a context free language.

I believe that we can write $L^{'} \ as \ L1 \cup L2$ where

$L1=(a^*b^*c^*){'} \  $

$L2={{a^nb^mc^p \ m\ne n \ or \ n\ne p  }}$

Now L1 is context free. I do believe that L2 as context free. Since context free languages are closed under union $L'$ is context free.

However while giving an exam I marked this language as context free. In the answer key it is a wrong answer. Now either I am wrong or the answer key is wrong.

What is my mistake?


texts:
Sorry in advance if this question sounds dumb...

As far as I know, building an algorithm using dynamic programming works this way:

express the problem as a recurrence relation;
implement the recurrence relation either via memoization or via a bottom up approach.

As far as I know, I have said everything about dynamic programming. I mean: dynamic programming does not give tools/rules/methods/theorems for expressing recurrence relations, nor for turning them into code.

So, what's special about dynamic programming? What does it give you, other than a vague method for approaching a certain kind of problems?


texts: Smallest integer i stored as a float such that i+1=i

texts:
So I had an assignment which asked me to find the smallest integer $i$ which when represented as a float is such that $i+1=i$

My approach- By making a simple C++ program , we get $i=16777216$ or $i=2^{24}$ But if we want to do that theoretically, I am unable to arrive at this number.

So a float is 32 bit variable and the first bit represents sign of mantissa and the next 23 bits represent the number in Mantissa. The next bit represents sign of the exponent and the following 7 bits represent the value of exponent.

Now consider $2^{23}$. In Binary, it is represented as $1000,0000,0000,0000,0000,0000$ (the comma's are just to make things readable). Now if we add $1$ to it, it becomes $1000,0000,0000,0000,0000,0001$

Now we store these numbers as float in C++. Both the numbers $2^{23}$ and $2^{23}+1$ are stored as $0100,0000,0000,0000,0000,0000,00010111$ (the 1 in the end has to be scrapped in order to fit the number in 24 bits). So both of them are essentially the same for the computer.

But why does the computer give me answer as $2^{24}$?

The code that I used

#include<iostream>

using namespace std;

int main(){

    float i=1;
    while(1<2)
    {
        if(i+1==i)
            {cout << fixed << i << endl;
                break;}
        i=i+1;
    }

}


texts: Algorithm for finding maximum mutually coprime subset of a multiset of integers

texts:
For a certain problem I am trying to solve given a list of integers, it is advantageous to me to first identify as many of the integers that are mutually coprime as possible. I'm having trouble thinking of a good general algorithm for this, and everything I've found online seems to relate to problems that are slightly different to what I'm going for. For example, given the multiset of integers A = {12, 15, 15, 16}, I would like the algorithm to return {15, 16}.

The first naive solution I could think of was to order the numbers in increasing order, take the first number into my set, then take any number after that which is coprime with all of the numbers in the set. This works for things such as {2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, but it would erroneously give {12} in my example above.

Besides that, the best idea I have is to create a list of sets of the factors of each number, at which point this problem can be reduced to the exact cover problem. However, I feel like this would have a relatively large amount of overhead, especially given the fact that the data sets I'm operating on won't be very large (~1000 elements somewhere in between 1 and 500).

Is there any algorithm I could apply here that would be more simple to implement (even if it is slightly slower) and would guarantee an optimal solution?


texts: Why $R\circ\emptyset$ is not always equal to $\emptyset$

texts:
I was going through the text Introduction to Theory of Computation by Michael Sipser. It is written that $R\circ\emptyset$ may not equal to $R$. I thought $R\circ\emptyset=\emptyset$ always. $R$ is any regular expression.

Couldnt find any example that contradicts that


texts: How can we use the FPTAS for problem B to solve problem A

texts:
Given an optimization problem A which is NP-complete, and can be polynomially reduced to another optimization problem B which is also NP-complete. If we use an FPTAS to solve the reduced problem B' (A $\rightarrow$ B = B'), then under what rules can the solution obtained from solving with the FPTAS be directly associated with a solution to problem A?

For example, Problem A is shortest Path problem and Problem B is knapsack Problem.


texts: Proof of NP-completeness via extra information

texts:
I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$.  I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \in X} I$, then
$E(X) := \sum_{i \in K(X)} |i - \text{median}(K(X))|$, where $|.|$ is the absolute value. $X_i$ might contains duplicated elements and all operations are on multisets; in $K(X)$, $\cup$ is a union of multisets, and in $E(X)$, $\sum$ adds "with repetition" (repeated elements are summed multiple times).
I want to prove this problem is hard, but I don't have a very straightforward way to prove it's NP-complete.
What I did instead was assuming given extra information, suppose I know the median of both $K(L^*)$ and $K(R^*)$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete.  Can I conclude the original problem is at least NP-complete?

For the sake of sharing, a wrong attempt I did on proving NP-completeness of with extra information problem.
I was converting this "given $m_L = \textbf{median}(L), m_R = \textbf{median}(R)$ and $S$, find $L$ and $R$" problem into a integer programming feasibility problem. Thanks to D.W helped me, I should do the opposite. Maybe doing the opposite is also possible. So sharing my effort in case it helps.
We can collect two vectors $A, B$ with length $K$, for every $X_i \in S$, get the imbalance with respect to $m_L$ and $m_R$. Namely $A[i] = \sum_{j \in X_i} sign(m_L - j) $, $B[i] = \sum_{j \in X_i} sign(m_R - j) $, where $$\text{sign}(x) = \begin{cases}
1 &\text{if }x>0\\
0 &\text{if }x=0\\
-1 &\text{if }x<0
\end{cases}$$
Now we can introduce another boolean indicator vector $I = \{0, 1\}^K$. When $I[i] = 0$, we assign $X_i$ to $L$, if $I[i] = 1$, we assigns $X_i$ to $R$.
$$
\langle I, A \rangle = 0 \\
\langle 1-I, B \rangle = 0
$$
Since $m_l$ is the median of $L$, we would definitely have the sum of imbalance equals to 0. The same applies to $m_R$. And here $A, B$ are coefficients and $I$ is the variable. If such a problem has any solutions, then we found $L$, $R$.
And clearly, the newly formed problem is an integer programming problem. Which is well-known NP-complete.  Whether if it is possible to convert any such type of problem into our set partition problem in polynomial time, I still need some help


texts: Is this definition of $\alpha$-equivalence correct?

texts:
I want to extend $\alpha$-equivalence to cover substitution.
That is, I will implement runSubst_Term : Subst -> Tm -> Tm and prove:
  Theorem runSubst_Term_main_property :
    forall sub : Subst,
    forall tm : Tm,
    AlphaSubst sub tm (runSubst_Term sub tm).

where the definitions of Subst, Tm, AlphaSubst are below.
But I don't sure that AlphaEquiv is a correct $\alpha$-equivalence relation.
So it would be appreciated if you could check that the definition is correct.
  Definition IVar : Set :=
    nat
  .
  Inductive Tm : Set :=
  | Var : forall iv : IVar, Tm
  | App : forall tm1 : Tm, forall tm2 : Tm, Tm
  | Abs : forall iv : IVar, forall tm1 : Tm, Tm
  .
  Fixpoint runSubst_Var (sub : Subst) (iv0 : IVar) : Tm :=
    match sub with
    | [] => Var iv0
    | (iv, tm) :: sub' =>
      if Nat.eq_dec iv iv0
      then tm
      else runSubst_Var sub' iv0
    end
  .
  Inductive AlphaSubst : Subst -> Tm -> Tm -> Prop :=
  | AlphaSubstVar :
    forall sub : Subst,
    forall iv : IVar,
    forall tm : Tm,
    runSubst_Var sub iv = tm ->
    AlphaSubst sub (Var iv) tm
  | AlphaSubstApp :
    forall sub : Subst,
    forall tm1_1 : Tm,
    forall tm1_2 : Tm,
    forall tm2_1 : Tm,
    forall tm2_2 : Tm,
    AlphaSubst sub tm1_1 tm2_1 ->
    AlphaSubst sub tm1_2 tm2_2 ->
    AlphaSubst sub (App tm1_1 tm1_2) (App tm2_1 tm2_2)
  | AlphaSubstAbs :
    forall sub : Subst,
    forall iv1 : IVar,
    forall iv2 : IVar,
    forall tm1 : Tm,
    forall tm2 : Tm,
    AlphaSubst ((iv1, Var iv2) :: sub) tm1 tm2 ->
    AlphaSubst sub (Abs iv1 tm1) (Abs iv2 tm2)
  .
  Definition AlphaEquiv (tm1 : Tm) (tm2 : Tm) : Prop :=
    AlphaSubst [] tm1 tm2
  .


texts:
I was wondering for if a single core processor can be MIMD? or MISD? or SIMD?
I thought MIMD's requirement is multicore, but I am not sure about this


texts: What makes neuromorphic computing architecture more efficient than von Neumann

texts:
What makes neuromorphic architectures more efficient (less heat and power consumption) than von Neumann architecture for complex tasks? Except inspiration from biological systems, what are some formal results on this?
Any reference to books or articles is appreciated as well.


texts: Complexity of covering subset of the monoid $(\{0,1\}^n, \text{OR})$

texts:
(At the very bottom of this, I will shortly describe the motivation for this question.)

Assume we have a commutative monoid $(G,\circ)$, i.e. a set $G$ with a commutative binary operation $\circ$ that satisfies associativity and the existence of a neutral element. The task is as follows: given some $X \subseteq G$, find a smallest $U \subseteq G$ such that $X \subseteq \langle U \rangle$, where $\langle U \rangle$ is the submonoid generated by the elements of $U$.

Now, if instead of a monoid we had a vector space, the task would be simple: determine the subspace spanned by $X$, and find a base for it. However, this relies on vectors having inverses, which we can't assume to exist in our monoid.

The monoid can be assumed to be fixed, i.e. we don't have to receive it as input, and the only input we receive is $X$. To be more precise, the set $G$ can implicitly be assumed to be $\{0,1\}^n$ for some $n$, and $\circ$ is the component-wise $\max$ operation, which is the same as $\{\text{true}, \text{false}\}^n$ with component-wise $\text{OR}$.

As an example, assume $n=4$ and we want to cover
$$X= \{(0,1,0,1), (1,1,0,0),(1,0,1,0),(1,1,0,1),(1,1,1,1)\}$$

then one optimal solution would be $\{(0,1,0,1), (1,0,1,0), (1,1,0,0)\}$.

Question: what is the complexity of this problem? I have a feeling it's somewhere between a covering problem and a hull problem, but I can't quite put my finger on whether I've come across a variant of this before or not.

The problem arose when a colleague of mine played around with a building block used in LED clocks. They have the structure

 _
|_|
|_|

and each of those seven lines has its own control wire. We only want to use $10$ of the possible $2^7$ configurations of those control wires, so we tried to figure out whether we can build all $10$ configurations using less than $7$ primitives via OR-ing. Since OR over binary vectors doesn't come with inverses, we only have a monoid.


texts: Transforming the sorting problem into Dijkstra

texts:
To get a lower bound of nlogn I am taking the sorting algorithm, which is well known to have that, and transforming/adapting it to Dijkstra's single source shortest path problem.

I know you need to do create a graph based on the numeric values and that Dijkstra will traverse it in order, any help with the rest and how to evaluate it?
Thank you.


texts: What's the complexity of the problem of optimally distribute n balls in m boxes?

texts:
Assuming that there is a function $f(x)$ (non linear, non convex) where $x$ is the vector $[n_1,n_2,\dots n_m]$ where $n_i$ is the number of balls in the box $i \in \{1,\dots m\}$, and $\sum \limits_i^m n_i = n$.

What is the complexity of the problem of finding the distribution of balls that maximize $f(x)$?
Also what's a good algorithm for solving this kind of problems?


texts: Why do OS and DBMS have their own synchronisation mechanisms, when OS can alone do it and it sits at the bottom of DB?

texts: I know that synchronization is important in the OS, but why do we need a separate topic synchronization and concurrency in the DBMS? The OS concentrates on program synchronization while the DBMS concentrates on data synchronization. Why can't the OS take responsibility for data synchronization?


texts: Could most categories , or a finite part of them be represented on a subset of a complete graph of N vertices (Kn) which is connected. and partly directed? Could all the axioms of category theory be written for such graphs?


texts:
I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, where $E$ is the number of edges in the original graph (not the complement graph).

If $G$ is a graph, the complement graph is defined to be the following graph: $e$ is an edge in the complement graph, if and only if it isn't an edge in the original graph. In other words we delete all existing edges, and add all the edges that were missing from the original graph.

So first I of course thought of "building" the complement graph (replacing the vertices in the adjacency list with those that don't appear there), then running BFS on the new list, but of course that would mean that the run-time would be based on the edges in the complement graph, not the original one.

I also noticed of course that after running BFS on the original graph, any vertex that has a distance from $s$ that is greater than 1 (in the original graph) should become 1 in the complement graph (because if they weren't neighbors in the original graph, they are neighbors in the complement graph). But I couldn't get the algorithm to continue according to some specific rules as to when should the distance be updated and to what.  Any suggestions?


texts: Why is addition as fast as bit-wise operations in modern processors?

texts: I know that bit-wise operations are so fast on modern processors, because they can operate on 32 or 64 bits on parallel, so bit-wise operations take only one clock cycle. However addition is a complex operation that consists of at least one and possibly up to a dozen bit-wise operations, so I naturally thought it will be 3-4 times slower. I was surprised to see after a simple benchmark that addition is exactly as fast as any of the bit-wise operations(XOR, OR, AND etc). Can anyone shed light on this?


texts: Calculating complexity for recursive algorithm with codependent relations

texts:
I wrote a program recently which was based on a recursive algorithm, solving for the number of ways to tile a 3xn board with 2x1 dominoes:

  F(n) = F(n-2) + 2*G(n-1)

  G(n) = G(n-2) + F(n-1)

  F(0) = 1, F(1) = 0, G(0) = 0, G(1) = 1

I tried to calculate the complexity using methods I know such as recursion tree and expansion, but none resulted in any answer. Actually I had never come across such a recursion, where the relations are codependent.

Am I using the wrong methods, or maybe using the methods in a wrong way? And if so, can anyone offer a solution?


texts: Finding shortest paths in undirected graphs with possibly negative edge weights

texts:
The book "Algorithms" by Robert Sedgewick and Kevin Wayne hinted that (see the quote below) there are efficient algorithms for finding shortest paths in undirected graphs with possibly negative edge weights (not by treating an undirected edge as two directed one which means that a single negative edge implies a negative cycle). However, no references are given in the book. Are you aware of any such algorithms?

Q. How can we find shortest paths in undirected (edge-weighted) graphs?
A. For positive edge weights, Dijkstra's algorithm does the job. We just build an EdgeWeightedDigraph corresponding to the given EdgeWeightedGraph (by adding two directed edges corresponding to each undirected edge, one in each direction) and then run Dijkstra's algorithm. If edge weights can be negative (emphasis added), efficient algorithms are available, but they are more complicated than the Bellman-Ford algorithm.


texts: How would a Turing Machine recognize n consecutive characters

texts:
I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters of type a in the string. The formal definition for the input language is:

$$ L=\{ \{w,n\}\in\{a,b\}^*\times \mathbb{N} \mid n\neq 0, \exists \alpha,\beta\in\{a,b\} \text{ s.t. }w=\alpha a^n\beta\}. $$

What I do not understand is how could I hold the count since I need to have exactly n characters.


texts: Are there practical methods for solving ILP?

texts:
Recently I encountered some papers in which the most important part seems to be writing an Integer Linear Program for a problem for which there exist some exact or heuristic algorithms!
Is solving an ILP easy and fast in practice? Is this solution exact or approximate?


texts: Are Test and set primitives as powerful as semaphores?

texts: I get confused because i don't know if it is possible to use Test and Set primitives in case where more then one process can be enter in critical section at the same time.


texts: Why is the running cost of SQUARE-MATRIX-MULTIPLY-RECURSIVE in CLRS $\Theta(n^3)$ instead of $\Theta(n^2)$?

texts:
I am reading Introduction to Algorithm CLRS (3rd ed.), Chapter 4 (Divide and Conquer), page 78, and am not sure why the explanation of why SQUARE-MATRIX-RECURSIVE algorithm takes $Θ(n^3)$.

  Combining equations (4.15) and (4.16) gives us the recurrence for the running time of SQUARE-MATRIX-MULTIPLY-RECURSIVE:
  $$
T(n) = \begin{cases}
   Θ(1) &\text{if } n=1 \\
   8T(n/2) + Θ(n^2) &\text{if } n>1
\end{cases}
$$
  As we shall see from the master method in Section 4.5, recurrence (4.17) has the solution $T(n) = Θ(n^3)$.

The part that I don't understand is that why $8T(n/2) + Θ(n^2)$ becomes $Θ(n^3)$. I only see $n^2$ in the term but why would it become $n^3$?


texts: How to solve the recurrence with two variables?

texts:
$M$  is also a variable.
\begin{equation}
    T(n)=
    \begin{cases}
      16T(n/2)+\theta(1), & \text{if}\ n^2> M \\
      M, & \text{if}\ n^2\le M \\
    \end{cases}
  \end{equation}


texts: Digraph without circuits with negative cost

texts:
Let $D=(V,E)$ be a digraph and let $a\colon E\to\mathbb{R}$ be a cost function on the edges.

How can I prove that $D$ has no circuits with negative costs only if there exists a function $\pi\colon V\to\mathbb{R}$ such that $a(uv) + \pi(u) − \pi(v) \ge 0$, for all $uv\in E$?

I realised that this is true by some examples, but I can't realise how can I prove that this is true in general?


texts: Don't understand closure under string reversal

texts:
I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function,

I having breaking down the syntax to english, my attempt it

for the function delta'' for a given state q and a symbol t the r inside the original set of states Q such that the state q exists in the modified function (in which all final states go to one final state via e-transition) ...

This is where I get confused, its sending r to the modified function delta' but I dont understand what the r stands for and how it comes to be. Furthermore I don't know what Sigma_epsilon means, I assume its the alphabet union with {e}

I also don't see how the induction proof is trivial or easy


texts: Uni-directional synchronization and locking issues

texts:
Suppose there are two databases, $D_1$ and $D_2$.  Let's further assume $D_1$ is always up and $D_2$ can be down sometimes. When it goes up again, it has to restart.

$D_1$ is filled by say a dozen other systems with event messages.  Those messages have IDs and might be updated or deleted. $D_2$ needs to be in sync with $D_1$, which is realized by:

on restart, pull all data from $D_1$.  During this pull $D_1$ is locked, thus all senders to $D_1$ need to wait.
otherwise $D_1$ always informs $D_2$ of updates by sending all updates. (During fetching, the data is locked of course.)

Now the question: what kind of blocking behaviour can we expect from $D_1$ and $D_2$?

In particular I find the following corner case interesting and instructive:

$D_1$ currently has a long list of events and the sender systems send a lot of new events/updates. $D_2$ just went down, goes up now and needs to fetch events from $D_1$, thus blocking the whole chain.


texts:
I need to construct a hash table with initially $7$ empty entries. Now add $6$ values to the table using the quadratic probing function
$$
  s(j,k) = \lceil j/2 \rceil^2 (-1)^j
$$
such that for some search query for key $k$ we need to look at exactly $6$ slots.
So the probing works by looking left and right from the index the hashing function mapped to an input key where the distances grow in a quadratic manner. After each iteration of $j$ we apply the modulo function to ensure we do not grow outside array bounds.
If I understand correctly, we could place $5$ keys first such that no collision occurs. Then, the $6$th key should collide exactly 5 times so we look at $6$ places.
I have tried several examples but I can't find a working sequence :(


texts: How correct was Justin Trudeau's explanation of Quantum Computing?

texts:
Recently, Canada's Prime Minister - Justin Trudeau - gave an impromptu explanation of Quantum Computing, much to the crowd's astonishment. I certainly thought that I "got" Quantum Computing a little bit more, even though it was a simplified explanation.

Here's the YouTube link to the actual press conference.

https://www.youtube.com/watch?v=Eak_ogYMprk

However, some are claiming that we shouldn't jump for joy at his explanation.

I'm wondering, as someone who doesn't exactly understand Quantum Computing, how accurate was Justin Trudeau's explanation of Quantum Computing?


texts: Are all undecidable/uncomputable problems reducible to the Halting problem?

texts:
Theory of computation tells us that there are some languages that cannot be recognized by a Turing machine. That is, there are well-defined problems for which no Turing machines can provide an algorithm which solves the problem.

Many problems that are undecidable seem to have a reduction to the Halting problem: Matyasevich's proof of the undecidability of Diophantine equations uses the Halting problem, the machine equivalence problem uses the Halting problem as well...

The question is: are all undecidable problems (in the sense of Turing) reducible to the Halting problem?

If so, is there a proof of this? If not, is there a counterexample of such a problem that provably cannot be reduced or mapped to the Halting problem.


texts: Name of a type of code similar to block codes

texts:
I've encountered a system where I need to construct a sort of quasi block code:

  We want to encode a symbol $s$ from a finite-sized alphabet $\mathcal{S}$ using $N$ segments of information. The $i^{th}$ segment must come from the alphabet $A_i$.

  We are tasked with designing a code for this encoder. The code will be a 1-1 function:
  $$C:\mathcal{S}\rightarrow A_1\times A_2 \times \dots \times A_N$$

What is the code with the highest possible minimum hamming distance between elements in its range?

Note that this is not the same as a "variable-length block code."

Note that if $|S|=2^m,$ and $\underset{i}{\max} |A_i|=2^n$ we could just examine binary (m,n) block codes, and take the best one that varies little enough that it can be re-written as a function onto $A_1 \times \dots \times A_N$.


texts:
The exercise is

  Given a set of point $S$ and a point $p$. Decide in $O(n)$ time if $p$ is a vertex  of convex polygon formed from points of $S$.

The problem is I am a little bit confused with time complexity $O(n)$. The more naive solution would be to construct convex polygon in $O(n\log n)$ and test if $p$ is one of the vertices.


texts: Sub-exponential time algorithm to compute playoff chances

texts:
There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the top 4 teams (with the highest number of wins) make playoffs (with some tie-breaking procedure that can be done in polynomial time).
After some number of games, we are given the records for each team (including all head-to-head records). Assuming the remaining $g$ games have outcomes which are coin flips, we want to calculate the percentage chance each team makes playoffs.

Here's a brute-force solution. There are $g$ remaining games, so we can consider $2^g$ binary sequences where a 0 in each position means the team earlier in the alphabet wins, and a 1 means the team later in the alphabet wins. For each sequence, we can compute which teams make playoffs. Then, the percentage chance of making playoffs can be computed as the number of sequences in which a given team makes playoffs divided by $2^g$.
This obviously has exponential time complexity (in $g$). Is there a better algorithm to solve this problem - perhaps a polynomial time algorithm using dynamic programming? Is there some way to prove we can do no better than exponential time? Is it possible to show this problem is NP-hard?

One simplification that can be made (which unfortunately does not reduce the complexity) is that we can compute, in polynomial time, teams which are guaranteed to make or guaranteed to not make playoffs. All games between teams in either set will not affect the probabilities for teams in the middle. As $g \to 0$, this gives a substantial practical boost to the algorithm.

Note that 10 teams playing triple round robin are arbitrary and this problem can be generalized to $N$ teams playing a $k$-round robin. Specifically for the brute-force algorithm, it is exponential in $g$ which may not be related to $N$ or $k$. A sub-exponential algorithm should ideally be not exponential in any of $\{N, k, g\}$.


texts: Machine Learning: if test, validation errors are same, the model with lower train loss is better at generalization?

texts:
I tuned some hyperparameters and got 2 best models.

These two models are almost the same "test(not train)" and "validation" errors. But model A has lower "train" error than model B.

In this case, the model with lower "train" error (model A), would show good performance on new data? (good generalization)

Or model A is more overfitting to the dataset so it would work worse in new data?

Thanks


texts: Relationship between proof and algorithm of Ramsey's Theorem

texts:
The following is a problem statement from "Introduction to Theory of Computation" Chapter 0 Problem 0.14:
Let $G$ be a graph. A clique in $G$ is a subgraph in which every
two nodes are connected by an edge. An anti-clique, also called an independent
set, is a subgraph in which every two nodes are not connected by an edge. Show
that every graph with $n$ nodes contains either a clique or an anti-clique with at least $\frac{1
}{2} \log_{2} n$ nodes.
In other words: Prove $R(t,t) \le 2^{2t}$ from this answer, Call it A1
The answer in A1 uses the upper bound
$$R(s,t) \leq R(s,t-1)+R(s-1,t) \leq {s+t-2 \choose t-1} \; \; \;$$
to prove this inequality but the selected answer given in the book uses the following algorithm (modified for readability):
Let $A$ and $B$ be two empty sets, $remNodes(G)$ is a function on $G$ which returns the number of remaining nodes in $G$ ,$discard(n,con|ncon,G)$ be a function that discards all the nodes connected or not by some edge given to $n$ by argument $con$,$ncon$  from the graph $G$, $deg(x)$ is a function that returns degree of node $x$ and $add(x,S)$ is a function to add an element to set $S$.
while (remNodes(G)) do
 Remove x from G
 if deg(x) > (1/2)(remNodes(G))
  add(x,A)
  discard(x,nconn)
 else
  add(x,B)
  discard(x,conn)

The set $A$ now contains nodes that form a clique and
$B$ contains nodes that form an independent set.
Can anyone explain this algorithm and its relationship with the proof of upper bound(if exists)?
In the book the solution is written as follows:
Make space for two piles of nodes: $A$ and $B$. Then, starting with the entire graph,
repeatedly add each remaining node $x$ to $A$ if its degree is greater than one half the
number of remaining nodes and to $B$ otherwise, and discard all nodes to which $x$
isn’t (is) connected if it was added to $A$ ($B$). Continue until no nodes are left. At
most half of the nodes are discarded at each of these steps, so at least $\log_{2} n$ steps
will occur before the process terminates. Each step adds a node to one of the piles,
so one of the piles ends up with at least $\frac{1}{2} \log_{2} n$ nodes. The A pile contains the
nodes of a clique and the B pile contains the nodes of an anti-clique.


texts: How do you detect if an algorithm is running at O(nlogn)?

texts:
Given only input and output(e.g. runtime), how do you know if an algorithm is running at O(nlogn) time complexity?

For example, how does LeetCode detect my code is running at O(nlogn)？
https://leetcode.com/problems/sort-list/description/

  Sort a linked list in O(n log n) time using constant space complexity.

Here's what I think:

I assume the complexity formula looks like  $ f(x) = a\cdot x \cdot\log_{b} x\ $

Then for input $x_2 = 2x_1$, $ \frac{f(x_2)}{f(x_1)} = 2\cdot\log_{x_1}x_2
$

So I take inputs like $2,4,8,16...$, get each runtime let's say $i_1,i_2,i_3,i_4... $. Then check if runtime ratio $\frac{i_2}{i_1}, \frac{i_3}{i_2} ,\frac{i_4}{i_3} \approx \log_{2}4, \log_{4}8,\log_{8}16...$.

If it is, then I would "guess" it's running at O(nlogn).

Can I make a good "guess" based on the "characteristic" I described above?


texts: Single-source shortest paths with even weight

texts:
I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even.
In another words, we have to find the shortest way with the minimum even weight.

I'd like to have some ideas how we solve this.

Thanks.


texts: Is integer factorization reducible to subset sum?

texts:
Is it possible to solve the FACT (integer factorization) problem in polynomial time if we know the polynomial Subset Sum algorithm?

We assume that we know the algorithm solving the problem of Subset Sum with complexity: $n ^ 4 \cdot m ^ 4$ (for example), where $n$ is the number of elements in the set, and $m$ is the size of the largest element (absolute value).

Theoretically, we can perform a reduction from FACT to 3SAT and from 3SAT to Subset Sum.

However, the reduction from 3SAT to Subset Sum has a problem.

After such a reduction (from 3SAT), the numbers in Subset Sum are very large.

For example, let's see page number four in this document.

The search number is: $11133$ for a logic function composed of only three variables and two clauses.

The number we are looking for is always around $ 10 ^ {v + c} $ where $v$ is number of variables and $c$ is number of clauses.

We can solve the Subset Sum in time $n ^ 4 \cdot m ^ 4$ but if $m$ grows exponentially, then the whole grows exponentially.

Is there any way to solve this?

---- Update:

I found this answer. It directs me to the conclusion that there is no classic decimal notation. Maybe this is some unary notation? Do I presume well? I am concerned, however, about the value of "3" in $k$ (the last row in the table on the fourth page in document). How can we encode it in decimal / binary form?


texts: An iterative algorithm for finding the partitions of a set into subsets of a fixed size

texts: The question is whether someone could provide an algorithm for finding all the partitions of a set S into subsets of fixed size (assume the fixed size is 2, to make things simpler, in which case the cardinality of S is even) which is iterative and not recursive and which runs in time proportional to the output (and produces no duplicates).  The algorithm, being deterministic, will produce the output in some sorted way. Ideally, it is possible to give a partition as input and generate all the partitions that follow the given one in the ordering in which the algorithm outputs the partitions.  Please advise if the question is not clear.


texts: When did idea of document file format or markup language first appear?

texts:
I'm not necessarily asking for the first well-formed definition of some markup language, nor the first implementation of parser for one such language.

What I'd like to know is when did people first think they could/should embed formatting (or other) information into pure text. Wikipedia gives one early example of such language, which is actually a complete system, both a language and its implementation: TYPSET and RUNOFF

But I'm guessing there are even earlier examples.

I'd be satisfied even if the first idea was in a SciFi novel predicting that people would (before wysiwyg editors) write things in one way, with formatting tags etc., and later read this content in a processed form.

A very early example might be didascalies from Greek plays, which were parts of text not meant to be read, but were affecting the way these parts are to be pronounced.  However, I'm looking for something less domain-specific. Something that originated with the idea (more or less) of a standarized way to add information to text, whether this is color in which text should be printed, a position information, or something purely semantical like "this is important" (without making this additional information a part of the text itself, as would be in adding something like (!!!) near the important stuff).

I think this question belongs equally to this site and History SE. I'm aware of (perhaps unavoidable, and partly even intentional) vagueness in this question, and hope it's no more vague than it should be. I will appreciate any feedback!


texts: How exactly does a CPU do process scheduling?

texts:
I know in theory how various scheduling algorithms work, such as round robin, where each process is given small time slices to run a few instructions, before the operating system passes execution onto the next process, and so on.

What I don't understand is how this is possible. The operating system is just some code, and so are all of the processes, so why doesn't this happen?

OS passes execution to the first process.
Now that process is running, the OS can't stop it, since the CPU can only run one instruction at a time, and that instruction is the process'.
Now the operating system has no control over the process, and can't stop it.

Now obviously this doesn't happen, but why not? How would the operating system say something like "Okay, you can run 3 instructions now, but after that let the other process run"?


texts: Largest set of vertices that is larger than its set of neighbors

texts:
I am reading a unpublished paper describing an algorithm. In one step of the algorithm, there is a bipartite graph $G(X,Y,E)$, where $X=\{1,...,n\}$.

For every subset $X' \subseteq X$, they define

$$f(X')=\bigcup_{i \in X'} \{j \in Y| (i,j)\in E\}.$$

In other words, $f(X')$ is the set of neighbors of vertices in $X'$.

Then they define:

$$ X^+ = \arg \max_{X' \subseteq \{2,3,...,n\}\ s.t.\ |X'|\geq|f(X')|}\{|X'|\}$$

i.e., $X^+$ is a largest subset of $\{2,3,...,n\}$ such that $X^+$ is at least as large as the set of its neighbors in $Y$ (i.e., the largest subset such that $|X^+| \ge |f(X^+)|$).

And then they do some stuff with this $X^+$.

MY QUESTION IS: Can this $X^+$ be found in polynomial time?

The authors do not prove that it can, but this is implied by the paper (otherwise the algorithm itself cannot be polynomial). Maybe it is so obvious that only I haven't seen this?

EDIT: The following similar problem can be solved easily:

Find the largest set of vertices in X with less than |Y| neighbours.

Solution: find a $y \in Y$ with a minimal number of neighbours in $X$. Return the set that includes all vertices in $X$ except $y$'s neighbours.

What about the following similar problem?

Find the largest set of vertices in X with less than |Y|/2 neighbours.


texts: Using relational algebra to express all with a condition

texts:
I encountered this question while revising for my finals exam on database theory.

The following database contains information about car repair workshops. The following tables are used:
$$Workshop(\underline{rname})\\
Car(\underline{cname},make,model)\\
Repairs(\underline{rname,cname},price)$$
Given two workshops $W_1$ and $W_2$, $W_1$ is more expensive than $W_2$ if for every car $C$ that is repaired by both $W_1$ and $W_2$, the repair price for $W_1$ is higher than the repair price for $W_2$ for $C$. Write a relational algebra query to find all workshops $(W_1, W_2)$ where $W_1$ is more expensive than $W_2$. Exclude workshops that do not repair any common cars.

I attempted to use a join naively:

$\rho_{(w1,car,c1)}(Repairs) \bowtie_{car} \rho_{(w2,car,c2)}(Repairs) \rightarrow A$
$\sigma_{c1 > c2}(A) \rightarrow B$

And then simply project out the $rname$ on a join with $Workshop$. However, I realised that there would exist some Repairs where $c1 < c2$ and $c1 > c2$ are both present, and it would still indicate that $W_1$ is more expensive than $W_2$.
I am thinking of using the division $\text{\\}$ operator, but I am not sure how to proceed.
Update 1: I tried it out in SQL and managed to get the following query.
SELECT * FROM Workshop w1
  WHERE NOT EXISTS (
    SELECT * FROM Workshop w2
      INNER JOIN Workshop w3
        ON w3.cname = w2.cname
        AND w2.rname = w1.rname
        AND w2.cname = w2.cname
      WHERE w2.price < w3.price);

I belive this is the correct answer, but my problem now is translating this back into relational algebra.
Update 2 (Solution): Instead of using a division, the subtraction operator is used.

$\sigma_{car_1 = car_2}(Repairs \times Repairs) \rightarrow All$
$\sigma_{\text{price}_1 \leq \text{price}_2}(All) \rightarrow B$
The answer is selecting all $w1$ from $All - B$

This will find all pairs in which $price_1$ is greater than $price_2$ for all $C$.


texts:
Below is a question based on CLRS, about using an algorithm to reach a balance between a group of friends. I figured the best way to do this, is through the use of a DFS algorithm. Below the question is some psuedocode I wrote using the formal algorithm of a DFS search. My question is, how do I get the algorithm to balance out the debt between every student?

  The input for your algorithm consists of two lists $owing$ and
  $friendship$. The length of the list $owing$ is the total number of
  students; $owing[i]$ is the amount that student $i$ is owing $(0 \leq i \leq
 len(owing)-1)$, and it is an integer than can be positive (owing
  money), negative (owed money) or zero. The list $friendship$ is a list
  of pairs that represent the remaining friendships, i.e., a pair $(i, j)$
  means student $i$ and student $j$ are still friends and can still talk and
  give money to each other. Devise an efficient algorithm which, given
  the two input lists, returns whether or not it is possible for everyone to get
  even.

The algorithm uses three colors (white/grey/black) to measure not visited/visited/cleared. What I want to happen is, it goes through a single cluster of friends, then checks to see if the balance of that friends group is equal to 0 (everyone can pay each other back). If not, returns failure. The issue is, let's say it does pass through that circle of friends- what if needs to go to another friends group? How will it balance out when that friends group might have a different adjacency list. Any advice on how to make sure everyone can pay each other and return 0?

Owing = false
Owed = false
pathTotal = 0

DFS(owing, friendship):
    for student in owing:
        student.color = white
        student.pred = null
        student.area = null

    for student in friendship:
        if student.color == white:
            DFS_VISIT(student, owing, friendship)

DFS_VISIT(student, owing, friendship)
    // Get all students current student is friends with
    for x in friendship:
        if x pair student:
            student.adj = student.adj + x

    // Check if adjacent members have not been visited
    for i in student.adj:
        if i.color != white:
            if owing[i] > 0:
                Owing = true
            else if owing[i] < 0:
                Owed = true

    // If it hasn't been visited
    if student.color == white:
        Owing = false
        Owed = false

        if student.pred == null:
            if owing[student] != 0:
                return "Failure"

        else:
            pathTotal = pathTotal + owing[student]

        // Calculated debt
        student.color = grey

    // Recursively go through the rest of the list
    for t in student.adj:
        if t.colot == white:
            t.pred = student
            DFS_VISIT(t, owing, friendship)

    // All neighbors visited
    student.color = black;


texts: Linear Path Optimization with Two Dependent Variables

texts:
Alright, so this is a fairly interesting problem I have but also slightly difficult to explain so I will try my best.

There are two runners on a line that goes from $x=0$ to $x=100$. The two runners start at $x=50$. The runners are then given an array of coordinate pairs that they must visit. The catch is, the coordinate pair contains the $x$ value for locations runner 1 and runner 2 must be at the same time. So for example, if they are given a coordinate pair $(40, 70)$, to successfully "complete" that coordinate, runner 1 must go to $x=40$, and runner 2 must go to $x=70$. They can't move on to the next coordinate pair until both have reached their destination.

So given a large array of coordinate pairs, the runners have to visit each coordinate pair in any order they chose. The runners can move at the same time and have the same speed. The trick is how to optimize the order in which they visit the coordinates. For example, if runner 1 is at $x=10$, and runner 2 is at $x=90$, it would be inefficient to chose a coordinate pair like $(80,80)$, because runner 2 would only travel $10$ units, and spend a long time waiting while runner 1 is moving $70$ units. This is sort of like the travelling salesman problem, except there are two people involved dependent on each other, and they can visit any point from any other given point in any order.

Does anyone have any ideas how to create an algorithm that would return the best (or at least good) optimized order in which they would visit these coordinate pairs?


texts:
I have some issue but I can't identify a way to solve it. I wanted to ask you what kind of problem it is?

We have a resource - contiguous computer memory. Also we have users which  require some contiguous piece of memory during a period of deterministic time.

In example,
User1 uses 2 bytes from 3rd to 5th iterations (inclusive)
User2 uses 1 bytes from 1st to 4th iterations (inclusive)
User3 uses 3 bytes from 5th to 8th iterations (inclusive)

It's easier for me represent it as table where users by rows, iterations by columns and values - quantity of required memory block.

      | 1 2 3 4 5 6 7 8
------+----------------
User1 | 0 0 2 2 2 0 0 0
User2 | 1 1 1 1 0 0 0 0
User3 | 0 0 0 0 3 3 3 3

The easiest solution - allocate enough memory for every user separately (6 bytes in this case). But I want to allocate some shared memory and distribute pointers so users use only unused memory.

One possible solution here is 5 bytes and (0, 2, 2) that means vector of pointers to memory blocks for every user.

So dynamic process will looks like:

iter 1 | x x 2 x x
iter 2 | x x 2 x x
iter 3 | 1 1 2 x x
iter 4 | 1 1 2 x x
iter 5 | 1 1 3 3 3
iter 6 | x x 3 3 3
iter 7 | x x 3 3 3
iter 8 | x x 3 3 3

(Here x - free bytes, values - byte's user identifier)

I've tried to solve this task with hypothesis that free memory block is also contiguous (in terms of task, we find iteration with the highest memory usage and add fake users that use the rest). Some cases can't proof this hypothesis.


texts: Minimizing concave function with a linear constraint

texts:
The problem can be formulated as:

$\min f(\textbf{x})=\sum_{i=1}^{n} \prod_{j \in N(i)}(1-F(x_i))$ s.t. $\sum_{i=1}^n x_i \leq B$

$N(i)$ is a set of i. And $F_{x_i}$ can be any function with range between [0,1].

if $F(x_i)$ is a convex function and $\prod_{j \in N(i)}(1-x_i)$ is concave, the objective function is a concave function.

Is this an NP-hard problem? Is there any possible ways so that I can get the approximation?


texts: System of congruences with non-pairwise coprime moduli

texts:
I have a set of congruences

x ≡ a1 (mod n)
...
x ≡ ak (mod nk)

And I want to find x, this can be solved by the Chinese remainder theorem and related algorithms: https://en.wikipedia.org/wiki/Chinese_remainder_theorem

Some examples: https://rosettacode.org/wiki/Chinese_remainder_theorem

For this particular example:

x ≡ 1031 (mod 1473)
x ≡ 1141 (mod 1234)
x ≡ 50   (mod 1827)

All the algorithms that I have tried won't work, since the moduli are not pairwise coprime.
However, 1024360583 is a valid solution:

1024360583 % 1473 == 1031
1024360583 % 1234 == 1141
1024360583 % 1827 == 50

What algorithm could find such a solution ?

I have also implemented Garner's Algorithm from the Handbook of Cryptography: it didn't solve that example.


texts: Evaluation of $\beta$-Reduction with Parentheses in $\lambda$-Calculus

texts:
I'm studying $\lambda$-calculus, and had a question regarding an exercise I came across. I understand that $\lambda$-calculus uses three main strategies of evaluation, but I'm having trouble applying it. Specifically $\beta$-reduction.

For example, for $1 + 2$:

\begin{align}
1 + 2 & = \lambda n.\lambda m.\lambda s. \lambda z. m\ s\ (n\ s\ z)\ 1\ 2 \\
& = \lambda s. \lambda z.\ 2\ s\ (1\ s\ z) \\
& = \lambda s. \lambda z.\ 2\ s\ ((\lambda s. \lambda z.s\ z)\ s\ z) \\
& = \lambda s. \lambda z.\ 2\ s \ (s\ z) \\
& = \lambda s. \lambda z.(\lambda s. \lambda z. (s\ (s\ z))\ s\ (s\ z) \\
& = \lambda s. \lambda z.s\ (s\ (s\ z)) \\
& = 3
\end{align}

The particular part that I'm having trouble understanding is the $\beta$-reduction at the last step before deriving the final $\lambda$ expression. More specifically, how $\lambda s.\lambda z. (s\ (s\ z))\ s\ (s\ z)$ reduces to $s\ (s\ (s\ z))$.

My understanding is that in order to perform $\beta$-reduction, we need to identify redexes of the form $(\lambda x.e_1)\ e_2$. Using this understanding, my initial approach would be:

\begin{align}
\lambda s. \lambda z. (s\ (s\ z))\ s\ (s\ z) & = [\lambda s. \lambda z. (s\ (s\ z))\ s]_{redex}\ (s\ z) \\
& = \lambda z. (s\ (s\ z))\ (s\ z) \\
& = [\lambda z. (s\ (s\ z))\ s]_{redex}\ z \\
& = s\ (s\ (s\ z))
\end{align}
Is my approach correct? If so, is it valid for me to drop the parentheses arbitrarily as I did in the third line?


texts: How to improve the accuracy of automatic conflict resolution?

texts:
A little background information from my previous question:https://english.stackexchange.com/questions/318528/conflict-resolution-how-to-decide-if-two-words-are-generally-unmistakable

When a court reporter strokes 2 different words with the same keys, this creates a conflict. Normally, the reporter will fix the error later, but sometimes there is a way for the court reporting software to fix the error for you. This can be referred to as automatic conflict resolution.

My court reporting software's system for accomplishing this is by recording the parts-of-speech before and after the conflicting words.

So for example, if my two conflicting words are Tallahassee and shake and I type the following sentences it will look something like this:

I eat at Tallahassee / shake all the time. (Prep - Determiner)

I eat a Tallahassee / shake all the time. (Article - Determiner)

At first it will make me choose between the two, but after I chose it will then automatically add its defined part of speech in a database, so that if I type something like this...

I eat in Tallahassee every afternoon. (Prep - Determiner)

my computer should correctly pick "Tallahassee" since I already told it that "Tallahassee" occurs after a Prep and before a Determiner. The rule for this is simply pos word pos

I tested the practicality of this conflict-resolution system with 79 random conflicts using parts of ANC's pos-tagged corpus and Excel VBA.

As the data shows, only 10 out of the 79 conflicts showed up with 0 collisions total. This means that in the entirety of the corpus, none of these conflicts had conflicting parts-of-speech which had caused an error.
36/79 conflicts showed up with 5 or less collisions.
32/79 had 10 or more collisions
Each collision represents 1 guaranteed error of real-time translation given the pos word pos rule (per the parsed text from ANC, which was about 4.5 million words long)

These results aren't very good for the kind of real-time accuracy I hope to achieve.  It would be much better if I could get at least 30/79 (as opposed to only 10) to have 0 "guaranteed errors."

How can I improve this system so that I will have fewer real-time translation errors?

My best thought is to change the rule from pos word pos to pos pos word pos in the case of a collision, but that's all I've got. I'm not very experienced on this subject, so I'm not necessarily opposed to the idea of starting over with something fresh.


texts: Formalizing an intuitive linear programming proof

texts:
My professor has asked me to prove the following:

  Prove that we can use an algorithm for linear programming to solve
  linear inequality feasibility problems. The number of variables and
  constraints used in the linear programming problem must be polynomial
  in n and m

I supplied him with an intuitive proof but he has asked me to rewrite it into a formal proof. My question is: How does one turn an intuitive proof into a formal proof?

Here is my proof:

  To prove that a linear programming algorithm can solve the linear
  inequality feasibility problem, let us consider what one would need to
  solve the linear inequality feasibility problem. We need a value that
  will satisfy every inequality. To find that, one could theoretically
  find every value that satisfies every individual inequality and then
  find the intersection. Because this is generally unfeasible in
  polynomial time, we can use a cartesian plane to greatly reduce the
  computation time and still represent all the values we computed using
  the first method. To do this all we would need to do is to is plot the
  inequalities and then shade the part of the inequality that contains
  the feasible values. Repeat this process until all the inequalities
  have been plotted. If there is a value or values, it will be in the
  region that has been shaded by all the inequalities. The process we
  have just described is a linear programming algorithm, therefore the
  linear inequality feasibility problem can be solved by a linear
  programming algorithm.

NOTE: In my proof, I talk about using a Cartesian plane. I know that that is incorrect for an inequality of more than 3 variables and that I should say instead that we should be using $\mathbb{R}^n$ where n is equal to the number of variables but I didn't know how to word that into my proof.

Thanks a mil.


texts: Are there any problems that reduce to the halting problem?

texts: I'm reading through sipser and there is a lot of computability problems that the halting problem reduces to, i.e. if $A_{TM} = \{\langle M,w\rangle : M$ accepts input $w\}$ then $A_{TM} \leq P$ where P is some other language, but is there an example of another language that reduces to $A_{TM}$ (i.e if we could decide $A_{TM}$ then we could decide that problem)


texts: Research on evaluating the performance of cache-obliviousness in practice

texts:
Cache-oblivious algorithms and data structures are a rather new thing, introduced by Frigo et al. in Cache-oblivious algorithms, 1999. Prokop's thesis from the same year introduces the early ideas as well.

The paper by Frigo et al. present some experimental results showing the potential of the theory and of the cache-oblivious algorithms and data structures. Many cache-oblivious data structures are based on static search trees. Methods of storing and navigating these trees have been developed quite a bit, perhaps most notably by Bender et al. and also by Brodal et al. Demaine gives a nice overview.

The experimental work of investigating the cache behaviour in practice was done at least by Ladner et al. in A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation, 2002. Ladner et al. benchmarked the cache behaviour of algorithms solving the binary search problem, using the classic algorithm, cache-oblivious algorithm and cache-aware algorithm. Each algorithm was benchmarked with both implicit and explicit navigation methods. In addition to this, the thesis by Rønn, 2003 analyzed the same algorithms to quite high detail and also performed even more thorough testing of the same algorithms as Ladner et al.

My question is

  Has there been any newer research on benchmarking the cache behaviour of cache-oblivious algorithms in practice since? I'm especially interested in the performance of the static search trees, but I would also be happy with any other cache-oblivious algorithms and data structures.


texts: Intuitively, my problem is a mix of perfect hashing, tree spanning, combinatorial stuff - Ordered Decision Tree?

texts:
The problem I'm trying to solve is difficult to to give a single name, but I'll call it the ordered decision tree problem.

Imagine a row of commands:

A -> Perform X

B -> Perform Y

C -> Perform Z

You read the above as if the data you're looking at is A, perform X, else if it's B, perform Y ...

Now let me add more logic.

A & B -> Perform X

C & D -> Perform Y

E & F -> Perform Z

More complicated.

A & B & C -> Perform X

A & B & D -> Perform Y

A & B & E -> Perform Z

Notice in the above, if I do the normal if/else thing I would have to conditionally check A 3 times, B 3 times and C, D and E once in the case the data dictates that I must perform Z.

This can be optimized as check A & B once, then do an array lookup (or hash lookup) of the last element which will point you to the action to be performed.

Even more complex.

A & B & E -> Perform Z

A & B & C & D -> Perform X

A & D -> Perform Y

C -> Perform W

This would translate to A & B as one check, then within that condition check E or (C & D). If not that, then see if it's A & D, or if it's C.

Another way to reduce the above example could be:

let I = A & B

I & E -> Perform Z

I & !E & D -> Perform X

!I & A & D -> Perform Y

!I & C -> Perform W

I wrote it the above way because that's how I'm thinking I'll represent it in some data structure.

Another piece of info that makes this problem slightly more tractable is that while I've used symbols like A, B, C ... in reality it's something like A means 1 - 100, and let's say C may mean 101 - 200. Therefore if I see A I can safely say C is not possible.

I'm not sure how to think about this problem, but my brain is thinking subset sum, some tree traversal or like building trees of disjoint sets, and ultimately also thinking this all could be represented as perfect hashing.

Is there a name for this problem?


texts: Why the name Recursively Enumerable and Recursive?

texts: Why did the sets of languages accepted/decided by a TM get the name Recursively Enumerable and Recursive, respectively?


texts: In this implementation of Hoare-partitioning Quicksort, why are additional checks for $i \leq j$ needed?

texts:
I am looking at the following implementation of Quicksort that uses Hoare partition scheme (two approaching indices $i$ and $j$ starting from either end of the array).

I am having trouble seeing why in the inner while-loops, the condition $i \leq j$ is needed in addition to checking $M[i] \leq p$ (or $M[i] > p$).

What I've tried:

I tried running through several examples with equal elements, ordered elements etc.
I have compared this implementation to the ones given in CLRS Introduction to Algorithms in hope for hints.

What I've found out so far:

In the implementation given here, the Hoare partitioning scheme is used. However, the pseudocode given in the Wikipedia article does not seem to do this additional check.
There is a potential problem in the given implementation that if all elements in $M[l+1..r]$ are les than $p$, the first while loop would not terminate when not checking for $i \leq j$. However, that does not explain the necessity of checking $i \leq j$ in the second inner while loop.

I don't expect a complete answer but I would be very thankful if someone could point me in the right direction.


texts: Deteremine if Language is in $R$ or $RE$

texts:
$$L =\left \{ \langle M \rangle \mid \exists x\in \Sigma^* \left(\left | x \right |\leq 10000 \wedge H(M, x\right) \right \}$$
Where $H(M, x)$ denotes whether Turing machine $M$ halts on input $x$.
My guess is neither $R$ or $Re$ because I would have to run infinite TM's in order to find out if every TM halts on x or is not halting on x. Is my intuition correct?


texts: Augment the tree data structure for disjoint sets to implement the PRINT operation

texts:
Consider the following new operation for disjoint sets
PRINT(x): print every element in S_x the set containing x
One Approach that I found but couldn't figure out completely :
In addition to tree we store a linked list. And each node in the tree in addition to the element
the tree nodes also stores the pointer to element in  the linked list.
UNION(x,y) : We union the x and y as usual. But we join the linked list for x and y
So here I could simply point the tail of one list to the head of another.
Print(x) : we obtain the s=FIND-SET(x) and print all the elements of the linked list pointed to
by s. This will print all the elements.
Now for this to work in the UNION to merge the linked list has to be done in a proper way so that
the root of the tree always point to the beginning of the list.
This can be done like when I merge Tree2 into Tree1 that is point the root of Tree1 to root of
Tree2 then I point the tail of Tree2 list to head of Tree1 list. In the way the merged list
will start with the root node of the tree (or the extra element stored in the root of tree)
Will this approach work or there are some flaws in this ?
Confusion points :

MAKE-SET(x) It's always mentioned that it takes O(1) time. As we have to create a single node
But what if the element x is already there. Then we don't create the node we have to first
execute FIND-SET(x) and see if it returns anything and then execute MAKE-SET(x).


texts: choose minimum number of M professors in polynomial time in order to design all N course exams

texts:
Think that we have M professors and N courses
every professor can wrote question for at least one course exam.
we want to choose minimum number of professors in order to design question for all N courses exams.

I try to hard but I only could model this question in a bipartite graph that one sections are  professors and the other sections includes courses every professors are connected to every courses that they can design question for them.

we wish to choose minimum professors to cover all courses.
one easy method is to check all cases and pick the minimum one in exponentioal time order...

could any one help me to solve it in polynomial time?

thanks


texts: Relationship between complexity classes XP and W[1]?

texts:
I am reading the introductory chapter in Parameterized Algorithms by Cygan et al. and I am having some problems with the distinction between complexity classes $\mathsf{W[1]}$ and $\mathsf{XP}$.

They explicitly define complexity class $\mathsf{XP}$ on p. 13 as the those problems that, given an instance $(x, k)$ of a parameterized problem, can be correctly decided by an algorithm in $O(f(k)\cdot|(x,k)|^{g(k)})$ time for functions $g, k$. I believe I understand this.

Complexity class $\mathsf{W[1]}$ is not explicitly defined. However, in the discussion of $k$-cliques on p. 9, they give an $O(n^k)$ algorithm for deciding whether a $k$-clique exists in a graph. As I understand it, therefore, the $k$-clique problem must be in $\mathsf{XP}$. However, the authors discuss it as a $\mathsf{W[1]}$ problem in a way that I find confusing.

My question, then, is twofold: (1) Am I right in thinking that $\mathsf{W[1]} \subseteq \mathsf{XP}$? I haven't been able to settle this by looking ahead in the book or by searching online. (2) Intuitively, what is the difference between the two classes? I have found defitions online, e.g. on Wikipedia, but not in language that I have found accessible. I would appreciate, therefore, if someone could provide more of an overview.


texts: Reasonable definition of beta-equivalence in big-step semantics

texts:
Assume, an extension of the lambda calculus with terms $t$ and values $v$ is defined in big-step operational semantics with evaluation relation $t \Downarrow v$.

It is intuitive to assume that $\beta$-equivalence holds, e.g.

(λx. t) unit $\equiv_\beta$ t when x is not free in t

It is however unclear to me, how $\equiv_\beta$ can be precisely defined in such a setting: Obviously, there is no small-step relation $\rightarrow_\beta$ that can be used to express a single reduction step, since the evaluation relates terms and values.

On the other hand, beta-equivalent terms do not evaluate to syntactically equal terms (e.g. when comparing abstractions which already are values).

So how does one define this equivalence in such a case?


texts: Examples of NP Complete key exchange algorithms

texts:
There's a number of questions on the internet (this site and others; e.g. Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems? ) discussing NP hardness of different asymmetric cryptosystems. How well established are NP hard key-sharing systems? That is, systems for establishing a shared key (that can then by used in symmetric encryption) that are based on problems that are known to be NP hard.

I was prompted to this question upon reading about https://en.wikipedia.org/wiki/Anshel-Anshel-Goldfeld_key_exchange and wondering if it could be shown to be NP complete when implemented on $GL_n(F_2)$ or $GL_n(\mathbb{R})$, cause these look like awfully hard constraint-satisfaction or quadratic optimization problems at a first glance. The corresponding problem this is based on is the Simultaneous Conjugacy Problem.

I'm aware that there is an important distinction between problems that are merely NP hard in the worst case -- but easy on most random instances, as opposed to problems that are "average-case NP" -- given a set of random instances, solving half of them is still hard. I'd be interested in hearing about key-sharing systems that rely on either notion of hardness.


texts:
For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?

[Where $w^R$ is the reverse of $w$]

My intuition says it is, as for a regular $L$, the languages $L^*$, $\{y: xyz\in L\}$ and $L^R$ are all regular languages, but I wasn't able to build a DFA/NFA for it, as if I try and "guess" from where to reverse the word I lose track of if it's a word in the original language.
Any hints?


texts: How does $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ imply these two inclusions?

texts:
In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ and (in different parts of the proof) state this implies the following two inclusions:

$\Sigma_3 \mathsf{TIME}(n^c) \subset \mathsf{SIZE}(n^{O(c)})$ for every $c$
$\mathsf{ZPP}^\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$

They also cite this enhancement of the Karp-Lipton theorem, in which the collapse of $\mathsf{PH}$ is to $\mathsf{ZPP}^\mathsf{NP}$.
I suspect the theorem is behind the inclusions in some way, but I just can't make the connection.

What am I missing?


texts: Edge weight changing during execution in shortest path algorithm

texts:
I have an undirected graph with weighted edges, in which I want to find the shortest paths from an initial node to every other node. Obviously Dijkstra's algorithm is usually a good choice, and I have previously used the variant where a min-priority queue (heap) is used to keep the set of tentative nodes $N_T$, and nodes are only added to $N_T$ as they are discovered.

However in this problem edge weights are dynamic. Each edge has a weight $w_{ab}=d_{ab}\gamma_b$, where $d_{ab}$ is the constant distance between nodes $a$ and $b$, and $\gamma_b$ is a dynamic scaling factor. $\gamma$ is first defined when a node is added to the tentative set, and it is fixed when a node is marked as visited. But while a node remains in the tentative set, $\gamma$ can change depending on the nodes visited in other parts of the graph. These non-local changes make it difficult to maintain the queue, since an addition of a new node may cause the weights to change and require the whole queue to be re-sorted.

If it helps: the tentative nodes are in groups, and nodes within a group will change weights uniformly - although groups can sometimes split and merge. So in fact the edge weight is $w_{ab}=d_{ab}\gamma_g$, where $g$ is the tentative node's group.

Illustration of groups during graph traversal from node $n_0$. At first there are two $\gamma$ groups, $g_x$ and $g_y$. Later, they merge into one group, $g_z$. $\gamma$ is constant within each coloured rectangle. The dashed lines show the tentative node set at various times during execution.

What is the most efficient way to  manage the group of tentative nodes, given that the edge weights may change? I am open to other ways to tackle the problem, e.g. run Dijkstra's algorithm in multiple passes, only updating $\gamma$ after each pass.

In terms of problem size, the graph is sparse and there are on the order of:

$\lvert{N}\rvert\approx100k$ nodes
$\lvert{N_T}\rvert\approx1000$ nodes in the tentative set
$\lvert{G}\rvert<\lvert{N_T}\rvert$ $\gamma$ groups


texts: What to study before PBRT(it's a bit hard)?

texts:
I tried reading PBRT but I wasn't able to fully understand the concepts in the book. The following are the two books that I found useful to read before reading PBRT.
http://www.amazon.com/Ray-Tracing-Ground-Kevin-Suffern/dp/1568812728/ref=sr_1_1?s=books&ie=UTF8&qid=1426597005&sr=1-1&keywords=ray+tracing
http://www.amazon.com/Introduction-Tracing-Kaufmann-Computer-Graphics/dp/0122861604/ref=sr_1_3?s=books&ie=UTF8&qid=1426597005&sr=1-3&keywords=ray+tracing
Which one will you recommend?