texts: Algorithm for maximizing correspondence between 2 sets

texts:
I am trying to figure out how to solve the following problem: I have 2 sets of objects, set A and set B. I have a metric that calculates how closely a given object from set A corresponds to an object from set B. I'd like to maximize the overall correspondence of the entire set.

What I tried first was a sort of greedy algorithm, where I went through each object in set A and calculated that object's correspondence with each object remaining in set B. I then replaced the object in set B that had the highest correspondence with the object in set A. For the next object in set A, I did the same thing, leaving out the objects in set B that already had a correspondence.

The problem with this approach is that it works very well for the first part of the sets, but as I near the end, there are fewer objects in set B to match with, so objects from set A tend to have worse correspondence with those objects.

I think that it might be better to do a full calculation of the correspondence of each item in Set A to each item in Set B, and from there choose each item from set A that has the highest correspondence of the next item in set B.

However, I'm left wondering if you could have a situation where, for example, object 1 from set A has, let's say an 95% correspondence to object 6 in set B, but it's next best correspondence is only 50% with object 14 in set B. Meanwhile, object 2 from set A has a correspondence of 97% to object 6 from set B, but it has a 96% correspondence to object 28 in set B. In my mind, I think it would be better for object 1 from set A to be matched with object 6 from set B (95% correspondence) and object 2 from set A to be matched with object 28 (96% correspondence) in set B instead of matching object 2 in set A to object 6 in set B and object 1 in set A to match object 14 in set B.

Is there a name for such an algorithm? I feel like it's related to the Knapsack Problem, but is not exactly the same. There will always be the same number of objects in set A and set B. I suppose it's possible that there will be more than 1 set of mappings that are "most optimal". In that case, I don't care which one is chosen.

In my application there will be between a few hundred to 10 or 20 thousand objects in each set. The average will probably be around 5,000 or so.


texts: Lambda Calculus as a branch of set theory

texts:
This answer to a question about whether C is the mother of all languages contained an interesting tidbit that I am curious about:

  The functional paradigm, for example, was developed mathematically (by Alonzo Church) as a branch of set theory long before any programming language ever existed.

Is this true?  What is the link between these topics that is so fundamental as to make lambda Calculus an outgrowth of set theory?  The best I can come up with is that standard mathematical functions possess domains and codomains.


texts:
I have come across a question that I am having quite a hard time with. I am to draw a design of an SRAM chip with an organization of 2M*128 SRAM that uses 1K*1K arrays of D latches. And then the questions ends with saying, "if this design is not possible then explain why." I have looked at other SRAM designs and have noticed that the multiplication of their d latch arrays, the resulting number is large enough to cover the first number of the SRAM, in this case 2M.

The other example I was looking at had a 32K*8 SRAM chip with 512*64 arrays of d latches. Assuming the array size is also in K, I multiplied 512 by 64 and came up with 32768. This covers the 32K of the SRAM chip. With my first example above, I multiplied 1K by 1K or 1000 * 1000 = 1000000. This does not cover the 2M of the SRAM chip. So am I to believe that it's not possible to design this chip? Also I could be totally wrong. I do not have that much experience in electrical engineering so forgive me.

Any help at all would be greatly appreciated in helping me!

Thank you.


texts: Regular expression for words containing single 1 and even number of 0s

texts: What would be a regular expression for the language of words containing a single 1 and an even number of 0s?


texts: TF-IDF query engine in context of terms weight

texts:
I'm looking for public algorithm which gives the engine these abilities:

Query by ranked terms
Limit outcome by date/time range

Basically, i'd like to concentrate articles (generally title|text|timestamp) identify the source and make N-N correlation to terms (is term for datasource same marking as term for dataentry?)

Given the database of such information

entry_data_type:[type_id|title|description]
entry_data:[entry_id|data_type_id|data_content]
entry:[id|entry_type(data,source)|parent_entry_id|created|updated]
terms(keywords):[id|keyword]
entry2term:[entry_id|term_id|term_weight]

Where keywords are both automatically defined (text frequency analysis) and manually assigned (probably abstract terms in context to entry contents)

I should be able to query by keywords like this: kw1:3 kw2:10 kw3:-2 [range:-7 days]
and output shall be entries sorted by given keyword weights (pattern keyword:weight)

I thought about something similar to EdgeRank, but that is social-graph-oriented, and I'm looking for more straight-forward solution (more selfish, meaning input filter is given by personal preferences, not social-graph-near preferences or social-score ranking)

Also TF-IDF would have to be limited by time, so the document base to calculate the entry score is inserted in given date/time range only. Is there any possible break-down of TF-IDF ranking, eg. to pre-calculate raw-data for each day and then, based on query, merge them for given date-range?

This question is independent of any particular programming language, platform, etc. I'm generally looking for keywords to look for, papers to read or ready implementations to study, but accepted are only answers not using paid or closed-source software parts or non-public-domain patents.


texts: What is the time complexity of this piece of code?

texts:
def find_perms(s):
    """
    Finds permutations of the given string.
    >>> find_perms("abc")
    ['cab', 'acb', 'abc', 'cba', 'bca', 'bac']
    """
    if len(s) == 1:
        return [s]
    elif len(s) == 2:
        return [s[0]+s[1], s[1]+s[0]]
    else:
        perm = find_perms(s[0:len(s)-1])
        last_char = s[len(s)-1]
        lst = []
        for strings in perm:
            for index in range(len(strings)+1):
                string = strings[:index] + last_char + strings[index:]
                lst.append(string)
        return lst

I am trying to figure out the time complexity of this piece of code as I'm working on studying coding questions and their time complexity and I managed to solve this permutation problem using recursion as was required but I am wondering how do I accurately determine the big-$O$ time complexity for this as it is a mix of recursion followed by an iterative loop. I would really appreciate some helpful input on this.


texts: Determining most efficient algorithm for a problem

texts: This is a very straightforward question, and I apologize if it is a repeat. All I want to know is if there is any general method for determining how efficient the most efficient algorithm for some problem is, in terms of time. Barring that, are there any specific methods used that have accomplished the same for a particular problem? If this is not possible in general or at all what are the hurdles to this, and is there any research along these lines?


texts: Can a Kolmogorov complexity oracle solve halting problem?

texts: I can find https://www.nearly42.org/cstheory/halting_to_kolmogorov/ but the halting problem part is unrelated to proof that kolmogorov can't be solved(still that assume it solvable and output a longer uncompressable string)


texts: Name for the tree formed after collapsing cycles

texts:
What do you call a structure which becomes a tree after collapsing cycles (so the new vertices are the old faces)?
For instance, the digraph (given by an NFA; ignore edge labels please) below becomes a tree
$\{a,b,c,d\}$ with edges $(a,b), (b,c), (b,d)$ via:
\begin{eqnarray*}
a\mapsto&\text{the cycle }&S_0,S_1,S_2,S_3,S_4,S_5,S_6,S_7,S_0
\\
b\mapsto &\text{the cycle }&S_5,S_6,S_7,S_8,S_9,S_{10},S_{11},S_{12},S_5\\
c\mapsto &\text{the cycle }&S_8,S_9,S_8\\
d\mapsto &\text{the cycle }&S_{10},S_{11},S_{12},S_{10}
\end{eqnarray*}


texts: Why are FPGA's less efficient than fully hard-coded ASIC's?

texts:
A Field-programmable gate array (FPGA) is generally more efficient than using a "hard-coded" processor like a CPU or GPU for highly specific applications like bitcoin mining or doing structurally identical computations many times over.

however, FPGA as far as I know are beaten in computational efficiency by Application specific integrated circuits (ASIC's) that are specifically designed to the particular problem (again take Bitcoin mining as an example).

My question is: What are the sources of the efficiency gain of ASIC's over FPGA's, given that FPGA's already allow you to setup the circuitry for the specific problem at hand?


texts:
Hi I wrote the following recursive decimal to binary function while studying for Andela.

def binary_converter(q):
    if q>255 or not isinstance(q, int) or q<0:
        return "Invalid input"
    if q==0:
        return '0'
    elif q!=0:
        q, r = divmod(q, 2)
        return str(r)+binary_converter(q)

The code works for the most part, except I haven't figured out a way to get rid of any preceding zeros to the final result.

For example:

      binary_converter(62)
      '0111110'
      That's 0111110 with a preceding 0.

How in the world do I get rid of it without breaking the code?

I've tried returning an empty string for the if condition but that breaks my ability to convert the decimal 0 to it's binary which is still 0.

Edit:
Here's the working code, updated with D.W's answer

def binary_converter_for_realz(q):
    if q>255 or not isinstance(q, int) or q<0:
        return "Invalid input"
    if q==0:
        return ''
    elif q!=0:
        q, r = divmod(q, 2)
        return binary_converter_for_realz(q)+str(r)

def binary_converter(q):
    if q==0:
        return '0'
    else:
        return binary_converter_for_realz(q)


texts: For what reason this function is recursive primitive?

texts:
Let $\forall n \in \mathbb{N}\ \ P(n)$ a primitive recursive predicate such that $\neg P(n)$ for a finite number of values of $n$.
Why this function:
$$
f(x) =
\begin{cases}
1 & \text{ if there are at least $x$ numbers $n$ such that $P(n)$}\\
\uparrow & \text{ otherwise}
\end{cases}
$$
is a recursive primitive function?
This is my reasoning, could you check whether it is correct?
If $\neg P(n)$ for a finite numbers of $n$ (let the set of these numbers be $A \subset \mathbb{N}$ where $|A|< \infty$), then $P(n)$ will be defined for $\mathbb{N}−A^c$ numbers, that is for $\infty$ numbers. Then "if there are at least $x$ numbers $n$ such that $P(n)$" will always be true and for this reason $f(x) = 1$.


texts: Why is integer programming more difficult than (real) linear programming?

texts:
Why is integer programming (IP) more difficult than (real) linear programming (LP)?

I searched a lot on the web, but I didn't find an answer.


texts: How to calculate the average of x numbers?

texts:
I just started a college course and I'm being asked for a flowchart where I explain how to calculate the average of x quantity of numbers. For this assignment I'm asked to follow the problem solving steps, which are:

Identify the problem.
Comprehend the problem. (As in, "is it mathematical?")
Identify different alternatives to solve the problem.
Selecting the best alternative to solve the problem and why.
Construct a list of instructions that allows to solve the problem.
Evaluate the solution.

After this I need the make a flow chart of the steps of pseudo-code. All of this is for a course called Structured Programming where we are supposed to learn Java.

I want to make clear that I don't want you to do my assignment I just want an explanation on how to do it, what should be the function I use and how to structure the flowchart.


texts: Amortized Analysis on Binary Heap, Potential Method

texts:
The potential function of a Binary Heap is given as the sum of levels of every node in the Binary Heap. For example,potential of a Binary Heap with 6 nodes is 0 + 2 ∗ 1 + 3 ∗ 2 = 8.
It is given that the amortized cost for the ADD(X) operation is O(logn).
To show that the amortized cost for the ADD(X) operation to be O(logn). How can we approach this problem?


texts:
I have been looking at the Suurballe node-disjoint algorithm, which is illustrated here:
http://www.macfreek.nl/memory/Disjoint_Path_Finding
What I am a bit unsure about here is "Step 4". So before that each node in the first shortest path is duplicated/divided into an in and out version of itself. And after that a new path is calculated. However, I can't seem to figure out what happens in Step 4. How are the in and out nodes translated into the original nodes seen in the first shortest path ? I mean, what am I supposed to add up here ? Is D_in to E_out path equal to just D = E, or...?


texts: Counting inversions in an array of 1 to N

texts:
Is there a straightforward way to characterise the number of inversions in an array of length N having distinct elements, each element an integer from 1 to N?

It's for a constraint optimization problem, where the number of inversions needs to be minimized.


texts: Effective method for simulating program's cycle

texts:
I'm looking for an effective method to simulate a program. Why I am needing this is because sometimes I can only have the program's description, code, and all I have left is pen and paper when I want to calculate the result at the end, or the n-th loop, or step n-th ..etc..

For example :

Declare @i int

While @i < 1000
begin
    print @i
    set @i = @i + 1
end

needless to say, this is a very simple program, everyone can understand it within a glance, but what about more complicated ones?

I can make it with pen and paper, but it consumes alot of time, and I think maybe there will be some methods, which will make this problem a lot easier!


texts: Name for multiset with fractional amounts?

texts:
What do you call a set which accepts multiples of the same element, even in fractional amount? Is there even an established for this?

Example from a video game about production chains:

For a carpenter to run at full capacity, you need:
1 carpenter
1 sawyer
0.5 woodcutter
0.25 forestry

And knowing the fractional amount is important to know for example that you can build only 1 forestry to feed 4 carpenters.

There is the "multiset", but definitions I've read all say elements must have an integer count. I've search for keywords like "multiset fractional amounts", "multiset fractional multiplicity", but didn't find anything .

There is the "knapsack" that turned out on occasion, but the problem's definitions also say the elements must have an integer count?

Am I just approaching this the wrong way??

(I'm a 1st year undergrad student in a computer science/programming degree)


texts:
I'm studying Distributed Systems and synchronization and I didn't catch this solution of totally ordered multicast with Lamport timestamps. I read that it doesn't need ack to deliver a message to the application, but

"It is sufficient to multicast any other type of message, as long as that message has a timestamp larger than the received message. The condition for delivering a message m to the application, is that another message has been received from each other process with a large timestamp. This guarantees that there are no more messages underway with a lower timestamp."

This is a definition from a book. I tried to apply this definition to an example but I guess that something is wrong.
Example.

There are 4 processes and they multicast the following messages (second number in parentheses is timestamp) :
P1 multi-casts (m11, 5);  (m12, 12); (m13, 14);
P2 multi-casts (m21, 6); (m22, 14);
P3 multi-casts (m31, 5); (m32, 7); (m33, 11);
P4 multi-casts (m41, 8); (m42, 15); (m43, 19).

Supposing that there are no acknoledgments, can I guess which messages can be delivered and which not? Based on definition, my guess is that only m11 and m31 can be delivered to the application, because all the other messages received will have a timestamp greater, but this seems very strange, and I think I didn't understand the delivery condition very well. I have an exam next week and in general I'd like to understand this mechanism.


texts: Are there minimum criteria for a programming language being Turing complete?

texts:
Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete?

From what I can tell from wikipedia, the language needs to support recursion, or, seemingly, must be able to run without halting. Is this all there is to it?


texts: Appreciation of the 5 state process model

texts:
I'm starting out in an Operating Systems module. I have a few understanding questions to think about, which will not be gone through in class.

A process state model is an abstraction (or model) which is used to explain what can happen to a process. Give a state of the process, it tells you what is the next allowed states and what causes the process to be in that state, and so on. A model is only at a certain level of abstraction. In this question, we will be focusing on the 5-state process model from the lecture.

(a) Is it possible for a process to never go to Terminated state. If so, give 3 possible scenarios when this can occur. If not, explain your reasoning.

(b) Suppose a process is in terminated state. Discuss whether you should be able to check at any time if a process is in terminated state at all times. Are there any implications?

5 state process model

I have attempted to answer all these questions, but because of their theoretical nature, I think there might be a lot more dimensions to these.

a)
I think it is not possible for a process to never go to termination, given enough time, because there are multiple ways a kill() or exit() command can be called, depending on their policy and mechanism in the operating system?

b)

I think it is important because a process in termination state still holds some data and requires the OS to do some cleanup. A process might not be running for other reasons other than termination, it could be in a blocked state without any IO activity or just be inside the ready state.

  Can someone check my understanding on these questions? Thanks.


texts:
Source:https://en.wikipedia.org/wiki/Abstract_data_type

Can we say that float data types (or all primitive data types or only integer) are abstract data types?


texts: Is changing or appending data an idempotent operation?

texts: As far as I know idempotent operation is a operation that can be applied many times with the same effect. Also I learnt recently that updating a tuple in a database is also idempotent. I thought that an idempotent operation was like a read-only stateless call (thanks to HTTP world with its famous GET request example). So, is changing data in a file (or database) idempotent? Is appending (extending) data in file/database idempotent? Why?


texts: Gramatical evolution doesn't result on creating good constants

texts:
I'm using Grammatical Evolution for symbolic regression tasks (i.e. searching the space of mathematical expressions to find the model that best fits a given dataset).

I'm evolving solutions according to a user-specified grammar:

 (0)
 <expr> ::= <expr> <op> <expr>      (0)
          | <const>                 (1)
          | <var>                   (2)
          | <unop>                  (3)

 (1)
 <op> ::= *     (0)
        | +     (1)
        | -     (2)
        | /     (3)

 (2)
 <const> ::= 0.1            (0)
           | 1.0            (1)
           | 10.0           (2)

 (3)
 <var> ::= x                (0)

 (4)
 <unop> ::= sin             (0)
          | cos             (1)
          | -               (2)

The population is a collection of arrays of integers. For example:

[0, 1, 2, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]

is the genotype of the individual +(x, +(1, +(1, 1)) (function $x + 3$).

The translation is performed using the integers to look up the table which describe the BNF grammar:

Step  Sequence  Rule   State
  1      0       0.0   <expr> <op> <expr>
  2      1       1.1   <expr> + <expr>
  3      2       0.2   <var> + <expr>
  4      0       3.0   x + <expr>
  5      0       0.0   x + <expr> <op> <expr>
  6      1       1.1   x + <expr> + <expr>
  7      1       0.1   x + <const> + <expr>
  8      1       0.1   x + 1.0 + <expr>
  9      0       0.1   x + 1.0 + <expr> <op> <expr>
 10      1       1.1   x + 1.0 + <expr> + <expr>
 11      1       0.1   x + 1.0 + <const> + <expr>
 12      1       2.1   x + 1.0 + 1.0 + <expr>
 13      1       0.1   x + 1.0 + 1.0 + <const>
 14      1       2.1   x + 1.0 + 1.0 + 1.0

The fitness function is the reciprocal of the sum, taken over the fitness
cases, of the absolute error between the evolved and the target function.

My problem is that, while the algorithm finds the general model, it often has trouble finding the right constants.

For example, if the target function is $x^2 + x - 12$, it finds something like:

$$x^2 + x - (10 + \sin(x))$$

or

$$x^2 + x - (1 + 1) \times (10 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1) \times ((10 - (10 / (1 + 1)) - (10 / (1 + 1 + 1 + 1 + 1)))$$

which is correct but requires a great effort to discover the constant.

Are there efficient techniques for generating numerical constants?


texts: Finding closest line segment intersecting rays

texts:
Assuming we have a fixed set of line segments $S$ such that any two segments are either disjoint or have a common endpoint.
A query would look like this; given a query point $q$ shoot 4 rays from $q$ (both sides horizontally and both sides vertically) and report the line segment in $S$ closest to $q$ intersecting any on these rays.
Is there a way to do this faster than $O(n)$ by preprocessing the data and storing it in some data structure? Or do we have to check for intersections with all segments for each ray and then compute the distances from the intersected line segments to $q$?


texts: To check whether a given number has been computed previously or not

texts:
Given a 64 bit positive integer. How to determine in the most efficient way whether the given integer has ever been seen or not?

Implementation in C++11 (Please do include this fact, while suggesting your opinions)

Intent: I am generating numbers randomly, by flipping one bit at a time. I need to check every time on generation of a number whether it has been previously generated or not? ex: 1,4,8,16,3,5,9,11,12, .... .

Current Solution:
1.I can create an unordered_map. However, I would be wasting memory for storing the value part which is boolean in this case. And also hashing isnt the cheapest operation and also their is a penalty of rehasing.

Can create a list and keep it sorted. Too expensive operations --Sorting and lookup.


texts:
Computing equilibria in games and the complexity thereof is imho still quite a young field in which a lot of work still is to be done (especially the former).

GAMUT (2004) is a very nice "suite of game generators designated for testing game-theoretic algorithms".

An example (2005) of a complexity result is that in normal form games, deciding if there exists a pure Nash equilibrium is a NP-complete problem. There are other types of equilibria each with their complexity results in different types of games.

An example (2014) of an (exact) method that solves said decision problem is a mixed 0-1 linear program.

So we have:

Problem(s) that are considered hard.
Instance generators (GAMUT)
Algorithms to solve said problems.

By hard I mean (most likely) not solveable in polynomial time.

Yet, to the best of my knowledge, no benchmarks have been created for any problem in Game Theory. I think, however, benchmarks could prove very interesting to compare algorithm results in future research.

How would one go about creating benchmarks? What is a good benchmark and what are good problem instances to benchmark? If someone decides to create a benchmark for some problem in some field, how is this process approached?

Examples of benchmarks: Graph coloring, Steiner Trees, equilibria in games (coming soon?), ...


texts: Cost of solving a matrix equation using the FFT

texts:
I am trying to calculate

$$V = (H^TH+I)^{-1} U$$

where $H\in\mathbb{R}^{m\times m}$ is a circulant convolution matrix corresponding to a convolution kernel $h$, and $U\in\mathbb{R}^{m\times n}$. The computation of $V$ can be done using the FFT algorithm.

I am confused about the computational complexity of using the FFT for this kind of problem. I will be most grateful if you could provide some suggestions or ideas for solving this problem. Thank you.


texts: How can I create 10-character, unique codes with no collisions, but without being predictable?

texts:
If we are using numbers and letters, there are $36^{10}$ unique combinations. Collision is already unlikely, but I need it to be impossible, so using hashing is out of the picture(?).

The use-case is users redeeming each one if they have been "activated" as redeemable. Think like Webkinz codes.

An inefficient solution would be to generate all of them at once, have a property on each saying whether it has been activated or not and keep a pool of those that have been redeemed and those that haven't.

Keeping a database of $36^{10}$ codes just because I can't come up with a clever algorithm is pissing me off, so I'm here for your help.

Any ideas?


texts:
I have a data structure that implements the following operations all in $O(1)$:

$\text{insert(x)}$, inserts a value into the data structure and returns a unique key $k$ to the value
$\text{delete(k)}$, deletes the value at key $k$ and returns it
$\text{get(k)}$, returns a reference to the element at key $k$

Internally the storage is simply a contiguous array $A$ of $(x, v)$ tuples. $x$ is either a value or is used to store a freelist. $v$ is a version tag. When $v$ is odd $x$ is a valid item with version $v$. When $v$ is even $x$ is unoccupied and is re-used to store the index of the next unoccupied item after this.

The key $k$ is a tuple of $(i, v)$, an index into the contiguous array and a version. Only when $A[k_i]_v = k_v$ is this key valid and contained in the data structure. Finally, on every insert and delete $A[i]_v$ is incremented.

Now this is very similar to a memory allocator (which returns pointers instead of keys), but the difference is that physical memory locations can be safely re-used here without spurious errors where old pointers point to new items. So from the perspective from the user every key that $\text{insert}$ ever gives is unique.

The question is, what is a good name for this data structure? I've seen similar data structures called "slot maps" in game development, but it's not quite the same. They don't use versioning and support dense iteration through using two indirections (one key -> idx and idx -> item), whereas this data structure can have a sparse memory layout.

It's also very similar to a slab allocator, but again it has added safety of returning permanently unique keys, even when re-using storage.


texts: Do not understand a concept in analysis of open-address hashing

texts:
I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor α=n/m<1, the expected number of probes in an unsuccessful search is at most 1/(1−α), assuming uniform hashing.

In the proof they are saying -

$p_i$ = It is the probability of exactly i probes where we are finding all of the slots to be occupied. i is 0,1,2,…

$q_i$ = It is the probability of at least i probes where we are finding all of the slots to be occupied. i is 0,1,2,…

Then it says -

$$\sum_{i=0}^\infty i\,p_i\, = \sum_{i=1}^\infty q_i$$

How it is so?


texts: Probability with an unusual pseudo-random generator

texts:
I will preface this with the actual question taken from lecture:

  An unusual pseudo-random generator outputs integers between 1 and 4, inclusive, in such a way that each value, v, occurs with a probability that is inversely proportional to v. For example, 4 is half as likely to occur as 2, and 1 is three times as likely to occur as 3. Determine the probability P(v) for all possible values of v. Explain in detail, and give the final answer(s) explicitly, in decimal notation.

This seems like a very simple probability question; however, I just want to make sure I am looking at this the correct way.  It says that each value occurs with a probability that is inversely proportional to v.  I understand that the sample space here is S={1,2,3,4}, but wouldn't this not be possible due to the fact that the probability of 1 would be 1 (which is the inverse of 1).  Thus, P(v) would not sum up to be equal to 1, which is a basic property of probability on events.

Just double checking that I am looking at this question the correct way, and whether or not it is a trick question.  Thanks!

EDIT: I understand that this question lies more as a statistical problem; however, it is from a CS class, so I thought it would still be appropriate to post here.


texts: What algorithm do SVMs use to minimize their objective function?

texts:
Support Vector Machines turn machine learning linear classification tasks into a linear optimization problems.
$$ \text{minimize } J(\theta,\theta_0) = \frac1n \sum_1^n \text{HingeLoss}(\theta,\theta_0) + \frac{\lambda}{2} ||\theta||^2 $$
My question is, what linear programming runs on the background for the minimization of the objective function $J$. Is it Simplex?


texts: Perfect Probabilistic Encryption still requires key length about as long as message

texts:
Let $(E,D)$ be a probabilistic encryption scheme with $n$-length keys (given a key $k$, we denote the corresponding encryption function by $E_k$) and $n+10$-length messages. Then, show that there exist two messages $x_0, x_1 \in \{0,1\}^{n+10}$ and a function $A$ such that

$$\mathrm{Pr}_{b \in \{0,1\}, k \in \{0,1\}^n}[A(E_k(x_b)) = b ] \geq \frac{9}{10}.$$

(This is problem 9.4 from Arora/Barak Computational Complexity.)

My gut intuition says that the same idea from the proof in the deterministic case should carry over. WLOG let $x_0 = 0^{n+10}$, and denote by $S$ the support of $E_{U_n}(0^{n+10})$. We will take $A$ to output $0$ if the input is in $S$. Then, assuming the condition stated in the problem fails to hold for all $x \in \{0,1\}^{n+10}$, we conclude that  $\mathrm{Pr}[E_{U_n}(x) \in S] \geq 2/10$ for all $x$. This implies that there exists some key so that $E_k$ maps at least $2/10$ of the $x$ into $S$ (the analogue of this statement in the deterministic case suffices to derive a contradiction), but now I don't really see how to continue. Is my choice of $A$ here correct, or should I be using a different approach?


texts:
Write the conjunctive or disjunctive normal form of an expression $f$ that is true if the number  $t=(xyz)_2$ is a zero of the following polynomial:

$$p(t)=(t-6)(t-5)(t-4)(t-2)t(t+1)(t+3)(t+7)$$

The zeros of this polynomial are $-7,-3,-1,0,2,4,5,6$. So $t$ has to be $(000)_2$ or $(010)_2$ or $(100)_2$ or $(101)_2$ or $(110)_2$ or... But now I don't know how to represent these negative numbers in binary? In other words how do I write $-7,-3,-1$ in the form $(xyz)_2$?


texts: How to represent semantics with Combinatory Logic

texts: How is Combinatory Logic relevant to software design?  For example, can one transform programs into CL?  If so, how?  Does CL provide a canonical representation for programs?


texts: Functional Core Language representation of tuples

texts:
I am writing a compiler for a simple subset of standard ML (just for fun) and I am stuck on how to represent the core language (I should mention that I write it in Haskell probably).

Basically what I have already is an expression type that looks like the following:

data Expr' e
  = Let Name e e
  | Fn Name e
  | Val Value
  | Var Name
  | App e e
  | If e e e
  deriving (Show, Eq, Functor)

newtype Mu f = In { out :: f (Mu f) }

deriving instance Eq (f (Mu f)) => Eq (Mu f)
deriving instance Show (f (Mu f)) => Show (Mu f)

type Expr = Mu Expr'
type LocExpr = Cofree Expr' SourcePos

(I use Cofree to conveniently annotate the terms with source code position and other information). With this core language I can already transpile simple programs to Scheme (or other langauges), it kind of is like a dynamic programming language at the moment (probably not treating recursion properly at the moment, but it seems to work).

Now I want to support tuples as well, because I want to catch up with  Kennedy's compiling with continuations, continued (https://www.microsoft.com/en-us/research/publication/compiling-with-continuations-continued/). If I understand the paper right, for his example of the untyped ML subset that he implements, he just uses pairs.

I guess however, that I could just add a term Tuple [e]  and indexing terms/case terms (where if I read Kennedy 2007 right, he just implements Tuple e e) to the core language to represent a tuple. Unfortunately, I don't find much about what would be a good way to represent tuples there. I am just a hobbyist, so I might just not look in the right places for that information.

Another resource where I stumbled over a core language was Turon's thesis https://www.mpi-sws.org/~turon/turon-thesis.pdf which is obviously not exactly about SML, but there he also only implements pairs (which makes me think whether tuples might be implemented as (a, (b, unit)) or something.


texts: What is the difference between maximal flow and maximum flow?

texts:
What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a reasonable answer. I believe maximum flow is quite clear as it means maximum amount of flow that can be transferred from source to sink in a network, but what exactly is maximal flow.

Please answer in layman terms if possible.

Thanks.


texts:
I have a question about the Set Cover problem: If I get a universe $U$, and $m$ subsets of size exactly $2$, and an integer $k$. Is this problem is still NP-C or I can solve it on a polynomial time?

Thanks.


texts:
The question is about how to schedule the pairwise SIMD instruction to move the data in proper position.
Say I n SIMD registers, each SIMD register contains n elements.
If each column represent a SIMD register.
They forms a matrix:
\begin{pmatrix}
a_0 & a_1 & a_2 & a_3 \\
b_0 & b_1 & b_2 & b_3 \\
c_0 & c_1 & c_2 & c_3 \\
d_0 & d_1 & d_2 & d_3 \\
\end{pmatrix}
element a_0 is held by SIMD register 0 's first position.
SIMD register 0 holds <a0, b0, c0, d0>
Now the data initialized in the matrix like below.
\begin{pmatrix}
a_0 & a_1 & a_2 & a_3 \\
b_3 & b_0 & b_1 & b_2 \\
c_2 & c_3 & c_0 & c_1 \\
d_1 & d_2 & d_3 & d_0 \\
\end{pmatrix}
Each column still represent a SIMD regsiter.
Except r0 has <a0, b3, c2, d1>.
How can I transform it back using pairwise SIMD masked register element exchange instruction, using as less instruction as possible? (with a general algorithm to deal with any n)
That's is to way I want to make r0 holds <a0, b0, c0, d0> as before.
Using an example to explain exchange instruction:
r0 :  <a,b,c>
r1 :  <e,d,f>
In one instruction e can switch with a, similar b and d, c and f, but not a and d or b and c.


texts: Are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?

texts:
I have searched the site well through, and also using Google and notes and couldn't find an answer to a question I am wondering about.

Given:

$$CF_{TM} =\{ \langle M \rangle \mid \text{$M$ is a TM description and $L(M)$ is a context-free language} \}$$

Are $CF_{TM}$,$\space $ $\overline{CF_{TM}}$ Turing-recognizable?

In order for a machine to be turing recognizable, there should exist a Turing machine that will halt and accept only string on that language, and for strings no in that language, it should reject or not halt at all.

So i am truly wondering about the relationship between context free languages and being Turing-recognizable, are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?


texts: Time complexity, Big-O for this function?

texts:
def f(n):
    if n < 100000:
        return 0;
    for(int i = 0; i < n*n; i++){
        return f(n-1)
    }

What is the time complexity?

My answer is $O((n!)^2)$. Here's my thought process:

The for loop will be running $n^2$ the first time.
However, during the first loop (i.e., $i = 0$), it will call $f(n-1)$, hence
the next for loop will be $(n-1)^2$.
This will keep going until $n <10000$ (base case).  Assuming $n$ is very
huge, the number of calls for each function to base case is essentially $n$ times.
Now, considering all the for loops, the total number of calls is essentially $n^2 \cdot (n-1)^2 \cdot (n-2)^2 \cdots 1!$ (there will be a total of $n$ times multiplication, and each multiplication will be $n-1$ of the previous one because of $f(n-1)$ call).


texts: Are all known algorithms for solving NP-complete problems constructive?

texts:
Are there any known algorithms that correctly output "yes" to an NP-complete problem without implicitly generating a certificate?

I understand that it is straightforward to turn a satisfiability oracle into a satisfying-assignment finder: just iterate over the variables, each time asking the satisfiability oracle to solve the conjunction of that variable with the original problem.

But would such a wrapper ever be useful? Do all sat solvers search over the space of possible assignments?

Or are there some types of NP-complete problems (traveling salesman, subset sum, etc.) in which the solver can, say, exploit a mathematical theorem to prove that a solution must exist? Like doing a proof by contradiction?


texts:
This is a real-world application, not a student assignment.

Suppose a list of events of that have startTime and endTime, and some overlap information. In pseudocode:

class Event {
    Time startTime;
    Time endTime;
    bool overlapsStart;
    bool overlapsEnd;
}

Events are considered overlaping if and only if their times intersect, but it's not considered overlap if some event just "touches" another (starts exactly when some other finishes).

There are two types of event: NormalEvent and EmptyEvent.

What I want?

For each event in the list, I want to:

1) Remove all EmptyEvents that overlap another event of any type. In special, if some EmptyEvent overlaps another EmptyEvent, only one needs to be removed, so that the overlap ceases.

2) The NormalEvents are first ordered by startTime, and then their booleans are set:

overlapsStart is true if the event overlaps some event that comes before it.
overlapsEnd is true if the event overlaps some event that comes after it.

A trivial example:

event1 = 6:00AM ➜ 8:00AM

and

event2 = 7:00AM ➜ 9:00AM

then:

event1.overlapsStart == false
event1.overlapsEnd == true

event2.overlapsStart == true
event2.overlapsEnd == false

Another example:

Now, this is what happens if some event "contains" another:

event1 = 6:00AM ➜ 9:00AM

and

event2 = 7:00AM ➜ 8:00AM

then, first event1 is put before event2, since it starts before. Then:

event1.overlapsStart == false
event1.overlapsEnd == true

event2.overlapsStart == true
event2.overlapsEnd == false

Naive implementation: I could analyze each event in turn, one by one, looking at all other events. That's easy, however this is too slow for a large number of events.

My question: What's an efficient way of solving this?


texts: General term for upcasting and downcasting?

texts: Is there a more precise term than simply "casting"? "Casting" often includes for example integer -> float or pointer -> unrelated pointer; whereas I'm describing exclusively casting up or down the type hierarchy.


texts:
[Input]: the begin and end points of an arbitrary line (small red points) and the line width (green line)
[Example]: begin=(20,20), end=(100,50), width=5

[Output]: The set of pixels (not the total area) that are in the yellow rectangle
[Example]: {(20,20), (20,21), (20,22),...etc.}

How can i calculate the output set?


texts: What is the difference (if any) between transition systems and finite automata?

texts:
is there any difference between transition systems and finite automata? Is it that transition systems consist of both NFA (nondeterministic finite automata)
and DFA (deterministic finite automata)?


texts: Are all context-free and regular languages efficiently decidable?

texts:
I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a subset of all decidable problems because we can solve them but it could take a very long time.

Why are all context-free and regular languages efficiently decidable? Does it mean solving them will not take a long time (I mean we know it without more context)?


texts: Double Write After Write Dependency in out-of-order/in-order executions

texts:
What is going to happen when we have a WAW(write after write) dependency which consists of two consecutive WRITE instructions into the same register.
We know we can solve a simple WAW dependency by having the second instruction put its results temporarily somewhere else.
What is going to happen though when we have 2 consecutive WRITE instructions? Can it be solved the same way (i.e. having a third instruction put its results somewhere else?)


texts:
I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly $p$ points. We also (randomly) place $c$ circle centres. I'm trying to find an algorithm that will allow me to find the radii for the circles that cover as many points as possible, subject to the constraints that:

the radii are bounded (maximum radius $r_{max}$)
circles cannot intersect/overlap.

My approach so far was to compute a rank 3 tensor. Start from a definition: a point is denied by a circle, if the circle, by taking another point, causes that the point cannot be covered by any of the remaining circles without violating the constraints. The size of tha tensor is $C \times P \times P$, where $C$ is the number of circles, and $P$ is the number of points. I initialize it with zeros. I then check whether if circle c takes point p, point p' is denied, which I signify in the tensor by setting the appropriate value to 1.  From this data I'm trying to deduce whether it's worth trying to encircle a point, e.g. if a point is denied by many points, it probably means that it's a distant, isolated point, or that denying point form a cluster. I didn't manage to find a way that would allow me to make general any statements though.

Any ideas how to extend my approach / any suggestions to do it differently would be most welcome!


texts:
I was trying to write my own code for primes in Python. I know that code already exists, but I am doing this to challenge my knowledge and make my own solution. I was wondering if any of you guys would tell me what's wrong with it.

factor_list = [ ]

def integer_test(x):

    if type(x) == int:
        return True
    else:
        return False

def factor_checker(x):

    count = 0
    y = x
    while count <= y:
        print(count)
        count += 1
        if integer_test(x / count) == True:
            factor_list.append(count)

factor_checker(45)

print(factor_list)

When I try to input a number for factor checker and then look at the factor list, I just get an empty list. What is wrong?

Thanks.


texts:
For example,

$T(n) = \log {n} \cdot T(\frac{n}{\log{n}}) + \Theta(n)$

I tried using the substitution method with $ n = 2^m $, but that got me nowhere, since it still ends up with a $m$ and $2^m$. The recurrence tree method also becomes rather complicated. Is there a general approach to follow to solve such recurrences?


texts: Is "ternary search" an appropriate term for the algorithm that optimizes a unimodal function on a real interval?

texts:
Suppose that I want to optimize a unimodal function defined on some real interval.  I can use the well-known algorithm as described in Wikipedia under the name of ternary search.

In case of the algorithm that repeatedly halving intervals, it is common to reserve the term binary search for discrete problems and to use the term bisection method otherwise.  Extrapolating this convention, I suspect that the term trisection method might apply to the algorithm that solves my problem.

My question is whether it is common among academics, and is safe to use in, e.g., senior theses, to apply the term ternary search even if the algorithm is applied to a continuous problem.  I need a reputable source for this.  I'm also interested whether the term trisection method actually exists.


texts:
Given an undirected, weighted graph $G=(V,E)$ and two nodes $s,t \in V$ and weight function $w: E \rightarrow \mathbb{N}$. The weight of a (s,t)-cut $ (U, U^C)$ is given by:

$$ w(U,U^C) := \sum_{\{i,j\}\in V :i\in U \land j\in U^C} w(\{i,j\}) $$

Reduce $$ MinCUT:= \{<G,c,s,t,k>\mid \text{There is a (s,t)-cut with weight} \leq k\} $$ to $$ BinaryProgram:= \{<A,b> \mid \text{There is
 a vector } y\in\{0,1\}^* \text{ such that } Ay \leq b \} $$

I know i have to find a matrix $A$ and a vector $b$ which implement the following constraints:

The weight of the edges which cross the sets of the cut must be $\leq k$
Node $s$ must be in set $U$ and node $t$ must be in set $U^C$
Every node must either be in $U$ or $U^C$

Can somebody give me a hint how implement these constraints into a matrix ?


texts: Path of the binary tree which has the highest number of bends

texts:
It is an interview question:

  Given a binary tree print the path of the tree which has
  the highest number of bends.

I could come up with a solution which will keep track the left or right child being called but interviewer was not satisfied with that solution. Has anyone better solution for this problem?


texts: When solving dynamic programming in a grid, how do you recognize whether the solution should start at the bottom-right of the table or top-left?

texts:
Example of start top-left, Coin Collecting problem in grid:
https://www.youtube.com/watch?v=94FEC_uNwVM

Example of start bottom-right, Dungeon Game problem in grid: https://leetcode.com/problems/dungeon-game/description/

I knew the Coin Collecting problem, so I started trying to solve Dungeon Game the same way, starting from the top-left (although it can also be solved bottom-right). Turns out Dungeon Game is solved from the bottom-right. How do I recognize this earlier?

function initTable(m, n, f) {
  var T = [];
  for (var r = 0; r < m; r++)
    T.push(Array(n).fill(f));
  return T;
}

var grid = [
  [-2,-3,3],
  [-5,-10,1],
  [10,30,-5],
];

function calculateMinimumHPFromTopLeft(dungeon) {
    var M = dungeon.length;
    var N = dungeon[0].length;

    var hp = initTable(M+1, N+1, Number.POSITIVE_INFINITY);
    hp[0][1] = 1;
    hp[1][0] = 1;

    for (var i = 1; i < M+1; i++) {
        for (var j = 1; j < N+1; j++) {
            var need = Math.min(hp[i-1][j], hp[i][j-1])-dungeon[i-1][j-1];
            hp[i][j] = need <= 0 ? 1 : need;
        }
    }

    return hp[M][N];
}

function calculateMinimumHPFromBottomRight(dungeon) {
    var M = dungeon.length;
    var N = dungeon[0].length;

    var hp = initTable(M+1, N+1, Number.POSITIVE_INFINITY);
    hp[M][N-1] = 1;
    hp[M-1][N] = 1;

    for (var i = M-1; i >= 0; i--) {
        for (var j = N-1; j >= 0; j--) {
            var need = Math.min(hp[i+1][j], hp[i][j+1])-dungeon[i][j];
            hp[i][j] = need <= 0 ? 1 : need;
        }
    }

    return hp[0][0];
}

console.log(calculateMinimumHPFromTopLeft(grid))   // 6 (wrong)
console.log(calculateMinimumHPFromBottomRight(grid))  // 7 (correct)


texts:
We are given an undirected graph $G=(V,E)$, $|V| \leq 50$. We are also given a starting vertex $s$. Each vertex $v$ of the graph is associated with a natural number $N_v$. Initially our profit is  $R=N_s$.

Now we have to traverse the graph beginning from $s$ in an order. We can visit each vertex or edge any number of times. Whenever we reach a vertex $v$, $R=R \operatorname{XOR} N_v$. (Note that if we visit $k$ times a vertex $v$, then we will XOR $k$ times with $N_v$.)

Find the maximum value of $R$ that can be obtained while traversing $G$.

Note: Here traversal means  walk beginning from $s$.


texts: Maximizing quantities/length in buckets to match each other

texts:
I have a use case, real one, and I'm trying to come up with an efficient maximization algorithm to solve it.

I'll try to simplify, with a simple analogue, and after will explain the real world use case:

Analogue:

Imagine you have 2 buckets of springs.
Each spring has 2 properties: resting length, and maximum stretching length.
Some springs are basically just rods, and resting length = maximum stretch length.

Your job is to maximize length of joined springs (& rods) in each bucket, such that the length of the 2 joined springs in the 2 buckets match exactly.

Example:

A bucket of springs $S_k$ is a non-empty multiset of intervals $[i,j]$, where $i$ denotes the "resting length", and $j$ denotes the "maximal stretch length".  For example, if the two buckets are

$$\begin{align*}
S_1&=\{[2,4],[2,4],[4,4]\} \\
S_2&=\{[1,1],[2,4],[13,15]\}
\end{align*}$$
then the maximum achievable length is 5, since $2 + 3 = 1 + 4$ and $2 \in [2,4]$ and $3 \in [2,4]$ and $1 \in [1,1]$ and $4 \in [2,4]$.

Note that if the last spring in $S_2$ would have been $[12,15]$ instead of $[13,15]$, the maximum length would have been $12$ (by the choice $4+4+4=12$).  But since lengths in each bucket must match exactly, we end up with only $5$.

Real (boring) problem:

My use case is from the finance world. I'm trying to match buy orders & sell orders for different amounts. Some of the orders can be partially accepted, whilst other must be strictly accepted or rejected. The orders I can partially accept, also specify the minimum amount it must be accepted with.
Each order is a "spring" in the analogy, where "resting length" is minimum accepting amount, and "maximum stretching length" is the full amount. The 2 buckets are the buy orders & sell orders.
Also, note that for now I've been asked to maximize amounts, but a further complication of the algorithm would be to maximize both amount & price. Either by preferring amount over price, and when there's a choice, to prefer the better price (lower for buy, higher for sell), or by maximizing total revenue (sell price * amount - buy price * amount).

Just for fun

Try to generalize to any number of $n>1$ buckets.  In a valid solution, all buckets must end up with the same total length.

P.S. To be clear, I haven't solved it efficiently myself. And I am still looking for an efficient way to do the matching.
I'm interested in the subset of orders, and not just the maximal amount that can be matched.
Also, this kind of reminds me of bean packing problem (NP complete), because of the strict orders (rods), but not quite. Even if it is NP complete, I'm still gonna implement it (inefficiently), since mostly it'll work on a small number of orders (pretty sure it's gonna be OK). But I have a hunch there's a dynamic algorithm somewhere that can be more efficient.


texts:
Consider we have an AVL tree.

Its left subtree A has disbalance coefficient has value +1 (meaning the right subtree has greater depth). Its right son has disbalance coefficient -1 (meaning left subtree has greater length).

If I understand correctly, we're looking for the most right vertex in the left subtree.

After deleting this specific vertex, what are possible cases regarding the tree rebalancing? When will it have to be rebalanced and when not?

Please correct me, if I've made any mistakes.


texts: Example of existence proof in dependent typing?

texts: I understand that $\Pi$ types are generalizations of functions and can be interpreted similar to $\forall$ in logic. I also know that $\Sigma$ types are generalizations of tuples and can be interpreted similar to $\exists$ in logic. But whereas I find it easy to imagine $\Pi$ type examples by thinking in Haskell, I am having a hard time thinking of good examples of $\Sigma$ types. Is there a particular "canonical" $\Sigma$ type that gives a good indication of how it can be interpreted as existence when the type is thought of as a proof?


texts: Differences between the Actor Model and Communicating Sequential Processes (CSP)

texts:
When we look at the Actor Model and Communicating Sequential Processes we see that they are both trying to do concurrency based on message passing, yet they are distinct.

(We see implementations of the CSP Model in go-lang's goroutines (and Clojure's core.async) and the Actor Model in Scala's Akka toolkit)

I'm trying to get a simple list of the differences between the Actor Model and CSP. So far I have:

actors message passing is asynchronous, CSP message passing is synchronous
actors are composable, CSP is not (necessarily)
actors always have unbounded non-determinism, CSP may have bounded or unbounded non-determinism
actors have variable topology whereas CSP has fixed topology
actors have the principle of locality, CSP does not have locality
actors are designed around their behaviour, CSP doesn't not necessarily have this

Is this correct? Is there anything I'm missing?

Assumptions

When I say 'actor model' - I mean the theoretical basis behind the implementation in Scala's Akka framework


texts:
I'm looking at collision detection in communication protocols, in particular Carrier sense multiple access with collision detection (CSMA/CD). According to what I've read on Wikipedia, a collision seems to cause the wave of the outgoing signal and the wave of the incoming signal to overlap. Thus, the signal has values with more amplitude than allowed for a "1-bit". This could be used as a working collision detection algorithm.

However, what's the use of the "Jam signal", as explained in the same Wikipedia article, then? It says that the CRC has to be faulted, but we already have a collision detection algorithm.


texts: TAoCP on quicksort: What are the differences between printings/editions?

texts:
In a footnote to the preface of "The Art of Computer Programming - Sorting and Searching", D. E. Knuth writes in a copy copyrighted 1973:

In this second printing […] The section on quicksort has also been completely rewritten.

What are the differences in presentation between printings&editions?


texts: How to prove that the erosion of a convex set by a convex set will result in a convex set?

texts:
How to prove that given convex sets A and B, the erosion of A by B will result in C - a convex set, too?

I was given this question as a test-preparation, and I think it shuold be a proof, but I don't know how to prove it.

A convex set is a set where every line connecting 2 dots in the set, must be part of the set, too. Now, if I would take a convex set A, I don't see how can I use erosion on it to get a non-convex set. Every example I try to create ends up the empty set, because the "holes" in B that are suppose to the "holes" in C, make C be all-zero.

Can someone help with a direction to a proof?
Thanks


texts: Using Chebyshev to derive an upper bound for Coupon Collecter's Problem

texts:
I'm TA'ing a course and have trouble solving an exercise.

Let $X$ be a RV defined to be the number of trials required to collect at least one of each type of coupon (of which there are $n$). Then $E[X] = nH_n = n \ln(n) + O(n)$ and $\sigma^2_X = n^2 \sum_{i=1}^n \frac{1}{i^2} - nH_n$ with $\lim_{n \to \infty} \frac{\sigma^2_X}{n^2} = \frac{\pi^2}{6}$. The exercise asks how Chebyshev's inequality can be used to upper bound the probability that $X > \beta n \ln(n)$ for some $\beta > 1$.

I tried this:
\begin{align*}
Pr[X>\beta n \ln(n)] &\leq Pr[|X-\mu_X| \geq (\beta - 1)n \ln n] \\
&\leq Pr\left[|X-\mu_X| \geq (\beta - 1) \left( \frac{\sqrt 6}{\pi} \sigma_X \right) \ln n\right] (1) \\
&\leq \frac{\pi}{6(\beta -1)^2 \ln^2 n} = O\left(\frac{1}{\ln^2n}\right)
\end{align*}

where (1) follows because $n > \frac{\sigma_X \sqrt 6}{\pi}$. However I believe the first inequality is incorrect because I'm discarding the $-  O(n)$ from $\mu_X$ in deriving an upper bound.

I also tried something else:
\begin{align*}
Pr[X>\beta n \ln(n)] &\leq Pr[|X-\mu_X| \geq \beta n \ln n - nH_n] \\
&\leq Pr[|X-\mu_X| \geq (\beta -1)nH_n] \\
&= Pr\left[|X-\mu_X| \geq \frac{6(\beta - 1)H_n}{\pi^2n} \left(n^2 \sum_{i=1}^\infty \frac{1}{i^2} - n H_n \right)\right]
\end{align*}

but I'm not sure where to go from here. Thanks for any help!


texts: Highest Response Ratio Next (Scheduling Algorithm)

texts:
In CPU scheduling HRRN(Highest Response Ratio Next) algorithm chooses the next process to be scheduled using the formula (W+S)/S  where W-> waiting time &
S->Service Time. Can someone share their intuition behind this formula? How does this calculate Highest Response Ratio?


texts:
In a recent test, I was asked to recognize if the below language is context  free:

$\qquad\displaystyle L = \{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\}$

I think it is context free, and can be accepted by below context free grammar, where $S$ is the start symbol and $Y$ is a non-terminal:

$\qquad S \to S0 \mid Y$

$\qquad Y \to 0Y1 \mid \epsilon$

However, my answer was considered wrong and that the language $L$  is not context free.

I'm confident about my answer, but the response has got me confused. Is my understanding correct? Please let me know if I've missed something.


texts: Convert $8.75×10^{6}$ to IEEE-32 format?

texts: There is a similar question already asked on this site but does not have an answer as to how the 10x was converted into 2y. I know how to convert 8.75 or 875 into IEEE representation. But what about 106? Surely there's a better way than expanding it and then converting it into binary.


texts: Is finite abelian group isomorphism in Log Space?

texts:
Definition :  An abelian group is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written

Input : Two finite abelian groups $|G| =n$ and $|H|=n$ by their table representation

Find : Is $G \cong H$?

There is an $O(n)$ running time algorithm for this problem, due to Kavitha [1].

Question : Is this problem known to be in Log Space?

I tried to google but did not get anything related to log space.

[1] T. Kavitha, Linear time algorithms for Abelian group isomorphism and related problems. Journal of Computer and System Sciences 73(6):986–996. (Science Direct)


texts: Number of possible sequence partitioning

texts:
Given a sequence of 1 and 0 elements, what is the number of possible partitioning of the sequence in sub-sequences (not necessarily consecutive elements, and any number of sub-sequences are allowed) so that any sub-sequence starts and ends with a 1, and can contain an arbitrary number of 0s?

For example: Given the sequence 1 0 1 1 0 1 there are only 3 ways of partitioning the sequence:

1.
1 0 1
      1 0 1

2.
1 0     0 1
    1 1

3.
1 0   1
    1   0 1

I am pretty sure the solution implies dynamic programming, since the solution requires a fast execution time (< 1 second).


texts: Two Generals problem - what if we set boundary conditions, and then layer redundant messages once they've been met?

texts:
apologies if this is in wrong place (very new to CS). I know there must be some flaw in my reasoning here, but I can't quite see it. Here's how I've stated the problem.

There are two generals, A and B. Messages start from A with a request M and B replies with an agreement N. Thereafter, the generals must exchange acknowledgements An and Bn of message reception. That is, after receiving N, A will send A1; upon receiving A1, B will send B1; and so on.

M reads:

  Attack at time X. Once I receive your reply, we will begin exchanging the acknowledgments An and Bn. As soon as we both know that you have received A1, and we both know that I have received B1, we will consider the plan finalized and proceed.

M goes through. N is sent, agreeing to M.
A1 is sent, acknowledging M and N. B1 is sent, acknowledging M, N and A1.
A2 is sent, acknowledging M, N, A1 and B1. B2 is sent, acknowledging M, N, A1, B1, and A2.
So on for An and Bn

By the time Bn is sent, B knows the following:
I've told A that I received A1 n times, and I know he heard me n-1 times. So he knows I received A1.
At this same time, A knows the following:
I've told B that I received B1 n-1 times, and I know he heard me n-2 times. So he knows I received B1.
Recall that the boundary conditions for the attack were:
As soon as we both know that you have received A1, and we both know that I have received B1, we will consider the plan finalized and proceed.

If we set n = 3, these conditions seem to be met. If we set n arbitrarily higher than that, it works.

As I understand it, the point of the Two Generals problem is that is that neither party is willing to proceed while the chance of the other proceeding is less than 100%. I also know that classically, each additional message increases the chance of a general proceeding asymptotically towards 100%. But if we set boundary conditions such as these, and then add some layers of redundant messages, there is some shared knowledge between the two generals, and the possibility that either one will not attack falls to 0? Have we not established that both generals know that the attack criteria have been met with 100% certainty?

I know this problem's unsolvable, so I must've made a mistake somewhere. I just can't see it.


texts: Does Master Theorem apply to $T(n) = 4T(n/2) + n^2 \log n$

texts:
Based on CLRS Theorem 4.1, master theorem doesn't apply to $T(n) = 4T(n/2) + n^2 \log n$. However, I saw the 4th condition of master theorem on slides of Bourke.
If $f(n)=\Theta(n^{\log_ba}\log^kn)$, then $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$. So $T(n)=3T(n/3)+n\log n$ can apply to case #2, see for example this question.
With the same logic, $T(n) = 4T(n/2) + n^2 \log n$ should be $T(n) = \Theta(n^2\log^2n)$. But it's actually $T(n) = \Theta(n^2\log n)$. Is there anything wrong of my thinking?


texts: Definition of unbounded approximation ratio

texts:
Suppose that there is a specific instance of a graph for which the approximation ratio of an algorithm polynomially increases with the number of nodes of the graph, say the approximation ratio is $n^2$.
Further, suppose that the number of nodes of that bad instance can be easily increased. For example, assume that the approximation ratio $n^2$ is obtained when nodes are distributed over the circumference of a circle and the number of nodes can be arbitrary large.

Then, is it correct to say the approximation ratio is unbounded?
When an approximation ratio can be called unbounded?


texts: Complexity of testing if a number is a primorial

texts:
For the $n$-th prime number $p_n$ the primorial $p_n\#$ is defined as the product of the first $n$ primes.

What is the complexity of testing if a given number $n$ is a primorial?
Is it related in some way to the FACTORING problem?


texts:
Is it possible to define logic programming for every logic that has implication and conjunction connectives? Does logic programming adds something new to the usual inference process. By usual inference process I mean the construction of the consequence set from the axioms - deriving all true statements. Does logic programming simply adds directionality/focus the the usual inference process or does logic programming add something more?

I am trying to model the beliefs, intentions and the goals of the BDI agent using substructural logic and for BDI agent implementation one is required to implement logic programming of the underlying logic. So - I am trying to understand what it means to implement logic programming for substructural modal logic with multiple modalities.


texts:
I've been reading Saxe's proof that 1-embeddability of integer weighted graphs is NP-Complete (http://www.math.columbia.edu/~dpt/RigidityREU/Saxe79EmbedNPHard.pdf Theorem 3.2).  I don't understand how this proof works.

First of all, does "1-embeddability" mean mapping each vertex to the real line?  What is meant by a "direction" as mentioned in Theorem 3.1?

I understand that PARTITION takes a set of integers and partitions them so that when all integers of $S_1$ are added, and when all integers in $S_2$ are added, both of these sums are the same.

In the proof of Theorem 3.2, it seems to be saying that we take this set of integers, and make them into weights of a cyclic graph.  So we have one big cycle, and the edge weights are the integers.  After this, I'm lost.

Why is it that the two sets $S_1$ and $S_2$ as defined add to the same thing?

And this proof is using a cyclic graph, how does it extend to general graphs? would we just remove an edge from this so its not cyclic?


texts: Do NFAs with $\varepsilon$-moves never terminate?

texts:
Suppose in an NFA we have an $\varepsilon$-move from a state $q_0$ to $q_1$. According to Sipser,

  Without reading any input, the machine splits into multiple copies one following each of the exiting $\varepsilon$-arrows and one staying at the current state. Then the machine proceeds nondeterministically as before.

Here is an application of this logic to our case: upon reaching the state $q_0$ our machine splits into two copies: one in state $q_1$, one in state $q_0$. For the latter copy, execution continues as before, so again another copy of the machine is created in state $q_0$. Thus, a copy of the machine always in state $q_0$ will exist indefinitely.

Is this true? If no, why not? How should I then interpret the description given above?


texts:
In my model checking class we have defined a bisimulation like this:

Let $K=(S,S_0,Act,R,L)$ and $K'=(S',S'_0,Act,R',L')$ be two kripke structures. A relation $B \subseteq S \times S'$ is called bisimulation if $\,\forall (s, s') \in B$ following points are true:

$L(s) = L(s')$
$\forall \,t \in S, a \in Act: (s,a,t) \in R => \exists \, t' \in S': (s',a,t') \in R' \, \land (t,t') \in B$
$\forall \,t' \in S', a \in Act: (s',a,t') \in R' => \exists \, t \in S: (s,a,t) \in R \, \land (t,t') \in B$

Two states $s \in S, s' \in S'$ are called bisimilar  iff. there is a bisimulation $B$ with $(s,s') \in B$.

$K$ and $K'$ are called bisimilar if:

$\forall \, s \in S_0 \, \exists \, s' \in S': s \sim s'$
$\forall \, s' \in S_0' \, \exists \, s \in S: s \sim s'$

My problem is that this definition is defined recursively. Take for example this two structures:

$\hskip2in$

Of course these structures are bisimilar since they are the same but to show that $(s_0, s'_0) \in B$ I have to show that $(t, t') \in B$ and now I'm in an endless recursion.

Have I misunderstood something about the definition?


texts: Simple way to prove $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular?

texts:
Prove: $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular.

Is it reasonable to get a DFA with at least 30 states for this language? is there an easier way to prove it is regular?


texts: Why clear the child's and not the parent's mark in Fibonacci heaps?

texts:
According to Cormen et al.'s Introduction to Algorithms chapter 21 on Fibonacci heaps (3rd edition), the FIB-HEAP-LINK($H$, $y$, $x$) clears mark of $y$ which will in the end be the child on the resulting merge. I just don't get it, why should we bother clearing this mark? In particular:

What happens if we leave their marks as is?
Why clear the child's mark rather than the parent's?

A reminder of FIB-HEAP-LINK:

FIB-HEAP-LINK($H$, $y$, $x$)

Remove $y$ from the root list of $H$
Make $y$ a child of $x$, incrementing degree[$x$]
Set mark[$y$] to FALSE


texts: Is integer sorting possible in O(n) in the transdichotomous model?

texts:
To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem:

  Given a sequence of length $n$ consisting of finite integers, find the permutation where every element is less than or equal to its successor.

But is there a proof that it doesn't exist, in the transdichotomous model of computation?

Note that I'm not limiting the range of the integers. I'm not limiting solutions to comparison sorts either.


texts:
given a Kripke Structure I want to check if a CTL formula is satisfied or not.
the CTL is: $$ AG(c \vee AX\neg E((a\vee b)Uc)) $$
I have read that it is better to write to CTL in terms of $\wedge $ and E so for instance for an inner part  $AX \neg E((a\vee b)Uc) $ I have re-written as: $$ \neg EX\neg(\neg E(\neg(\neg a\wedge\neg b)Uc) $$
but it seems to be illegal CTL.

generally what is the best approach for these kinds of problems to solve. re-write the formula in terms of other operations or just draw the parse tree.


texts:
I've head the lecture today and we saw this theorem:

$\mathsf{NP}^{\mathsf{NP}}=\Sigma_2$

But without a proof.
Here are the definitions I use:
A language $L$ belongs to $\Sigma_k$ if there is a deterministic Turing machine $M(x,y_1,y_2,\dots,y_k)$ such that:

There exists a constant $c$ such that $|y_i|=|x|^c$ and $M(x,y_1,y_2,\dots,y_k)$ runs in time $\mathit{poly}(|x|)$.
$x\in L$ iff $\exists_{y_1}\forall_{y_2}\exists_{y_3} \dots M(x,y_1,y_2,\dots,y_k)=T$,
where the quantifiers are alternating between existential and universal, and start with existential.

$\mathsf{NP}^{\mathsf{NP}}$ is the class of all languages of languages in $\mathsf{NP}$ with oracle calls to a language in $\mathsf{NP}$.
I thought maybe to use $\mathsf{SAT}$ as it is an $\mathsf{NP}$-complete language.
Can someone please help me understand why this is true?


texts: Is the language $a^{3}b^{+}$ the same as $\{a^{3}b^{n}, n \geq 1\}$ ? and what is the result of pumping this?

texts:
The regular expression $a^{3}b^{+}$ is indeed regular because we can define an automata $M$. But I see that $\mathcal{L} = \{a^{3}b^{n}, n \geq 1\}$ may generate the same strings, but using the pumping lemma with constant $N$ for a substring $\alpha\beta = a^{3}b^{t},|\alpha\beta| \leq N$, let $\alpha = a$ and $\beta = a^{2}b^{t}$, therefore $\gamma = b^{N-t}$, and when $k = 0$, $\sigma = \alpha \beta^{0} \gamma = \alpha \gamma = ab^{N-t}$, which doesn't belong to $\mathcal{L}$ and the language isn't regular.

So, is really the regex equal to $\mathcal{L}$? or am I pumping wrong?


texts: Under which operations is the class of non-recursive languages a closure?

texts:
I am currently studying turing computability and related problems such as the halting problem with a background in formal languages.

I know that the class of recursive (decidable) languages is a closure under union, intersection and complement, and that recursively enumerable languages (semi-decidable) are a closure under union and intersection, but what about non-recursive (undecidable) languages?

To be more specific, I am trying to prove that a specific language of the form $$L = \{ w \in \Sigma^* : w \in A \lor w \in B \}$$ is non-recursive. I managed to prove that neither $A$ nor $B$ are recursive by reducing them to the universal halting problem, but I am not sure what that implies for $L$.

  The exact language is $$L = \left\{ w\#u \in \left\{ 0, 1, \# \right\}^* | \\ M_w \text{ will halt with input } u \text{ or } M_u \text{ will halt with input } w \right\}$$ where $M_b$ is the turing machine whose transition function $\delta$ is represented using Gödel numbering as a binary string $b$.

Is the class of non-recursive languages a closure under union? If it is, how could I prove it myself or where could I find an existing proof?


texts: Proving a language comprised of 2 languages is regular(with suffix and prefix)

texts:
I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular:

$$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\sigma_n\mu_nv\}$$

$u,v \in \Sigma^*$
$0\leq n$, for every i($1\leq i \leq n$): $\sigma_i,\mu_i \in \Sigma$
$\sigma_1...\sigma_n \in L_1$
$\mu_1...\mu_n \in L_2$

I don't understand how to prove if because of the suffix and prefix(u,v accordingly).

If it weren't for u,v what I think I would've done is building an automaton(Deterministic finite automaton): $A=\left(Σ,Q1xQ2x\left\{1,2\right\},\left(q01,q02,2\right),F1xF2x2,δ\right)$, Ending in accepting iff both automatons that accept each language end in an accepting state, and $L_2$ needs to be after $L_1$ from the language's description. However, I don't know how to deal with the u,v in the beginning and in the end. I am not sure how to configure it correctly to prove $L^\frown$ is regular.

Would very much appreciate your assistance with it.


texts:
Consider a variation of the normal heap which we will call the x-heap

The x-heap of height $h$ has the following properties:

It will have $2^h$ nodes
A height of $0$ corresponds to the single root node
The format of the tree is a root with exactly one child, which in turn is the root of a complete binary tree

We define a collection of x-heaps to be sequence $X_0, X_1,\dots,X_k$ with the following properties:

$height(X_{i-1})\leq height(X_i)$, where $0\leq i \leq k$
There exist at least $i + 1$ (X-heaps) of $height \leq i$, where $0\leq i \leq k$
There exist at most $i + 2$ (X-heaps) of $height \leq i$, where $0\leq i \leq k$

We cannot have a collection with all of the same type of x-heap (can't have collection with all single nodes)

Prove that if $X_0,X_1,\dots,X_k$ is a collection, then the total number of nodes is between $2^k$ and $2^{k+1}$

I am not sure where to start here. I feel I must use the last two bullet points, but not sure how.

Moreover, the trees in a collection can have height $1, 3, 4, 8$ as an example. It is not limited to increasing by $1$.


texts: Is Hamiltonian cycle problem on graphs with out-degree at most 3 NP hard?

texts:
I am trying to show a different form of Hamiltonian cycle problem is NP Hard. The problem is as follows.

  We have a directed graph and each node can have at most 3 outgoing edges. Determine if this graph has a Hamiltonian cycle.

Is this problem NP hard?

I just need to find a problem to reduce to my problem but could achieve to find none.

3SAT looks friendly to me as it has 3-termed clauses but no more I progressed.


texts: Can somebody explain please why Ford-Fulkerson Algorithm has pseudo-polynomial complexity? I understand that the complexity in this case strongly depends on the capacities of the edges of the network, since we have $O(|E|*f_{max})$, but why is the algorithm still not polynomial?


texts: Shortest path with nodes containing collectibles of negative cost

texts:
Suppose you have a graph with weighted edges and nodes. Edges always have non-negative costs (representing e.g. fuel costs), and nodes always have non-negative benefits (representing e.g. collectible fuel tanks). A path from A to B is a series of contiguous edges starting at A and finishing at B. The net cost of a path is the sum of the weights of edges (including multiplicity) on the path minus the sum of the benefits of the distinct nodes (ignoring multiplicity) on the path.

In principle paths are permitted to visit a node more than once, but the node's benefit is only ever collected once (i.e. you can't pick up the same fuel can twice).

Is there an efficient algorithm to find a minimum cost path from A to B in this situation? What if you're promised that the input contains no paths from A to B with net negative cost? What if you're happy with heuristics that perform well when nodes containing 'fuel' are scarce?


texts: Does the Hack computer from "The Elements of Computing Systems" use Von Neumann architecture?

texts:
I'm reading "The Elements of Computing Systems" (subtitled "Building a Modern Computer from First Principles - Nand to Tetris Companion) by Noam Nisan and Shimon Schocken.

Chapter 4 is about machine language, and more specifically the machine language used on their computer platform called Hack. Section 4.2.1 says this about Hack:

  The Hack computer is a von Neumann platform. It is a 16-bit machine, consisting of a CPU, two separate memory modules serving as instruction memory and data memory, and two memory-mapped I/O devices: a screen and a keyboard.
  …
  The Hack programmer is aware of two distinct address spaces: an instruction memory and a data memory. … The CPU can only execute programs that reside in the instruction memory. The instruction memory is a read-only device, and programs are loaded into it using some exogenous means.

With that distinction between instruction memory and data memory, is it really a von Neumann architecture? According to my understanding of the difference between von Neumann and Harvard, that description sounds much more like a Harvard architecture.


texts: Does this article imply that Turing-Computability is not the same as "effectively computable"?

texts:
I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve.
In my understanding, this should mean, intuitively, that this problem is "effectively computable", since we have an effective, real method to compute it: build a quantum computer and solve it.
But, since a Turing Machine (turing machines are not quantum computers, I think?) can not solve it, this is not turing-computable.
Hence, does this mean that "effectively computable" and "turing-computable" are not the same concept? So, is the Church-Turing thesis wrong?
My intuition says "no", because in that case, this would be very big news. So, if not, why not?
Also, I am aware that there exist already models of computation that are more powerful than turing machines, but those are only "theoretic", aren't they? Quantum computers, on the other hand, could be physically buildable.


texts:
Is the set of real numbers a language?

My idea is that the set of real numbers can't be a language because it is uncountable. Every language must be  countable.

Is there any other way to solve this problem?


texts: Are there cs methods to uniquely create an ID, that prevent masquerading

texts:
I'm not sure if this is the right place, but I have an idea for a database kind of like a wiki, that would NOT have editors, and would have the following requirements:

Any user can start with using their real name or a pseudonym
Anyone can later switch to using their real name (no reversals to a pseudonym or changing pseudonyms)
Identity is assured using some combination of a private/public key system and hashing (data is hashed with the content and the key of the user that created it).
Any user can add data and/or comments to anything (but cannot delete another users data).
A user can "delete" their own data, which just creates a new version of the same "chunk". This is visible and browsable by anyone.
Any user browsing/reading the database can filter the raw data itself by any desired means. For instance: only show data from real-named users, only show data that hasn't been changed, only show data that has been verified or confirmed by X number of other real-named users, etc.

I see some issues which might be fixable or unsurmountable:

Verification of real name. This could involve some trust system, where multiple (unrelated) parties have to sign off on who you are (not on the content of your data, but just your identity).
For two people that share the same name, there will need to be some additional name field, maybe an incrementing number.
If you lose your private key, how do you post again? Could there again be a way where a quorum of the verification parties ID the real you, as you, and your private key can be returned? (this sets up issues with storing the key)
Preventing masquerading for the pseudonym accounts (maybe data can be filtered by only those who will actually sign their name), so that the hackers/spammers don't overwhelm the system with bad or fake data, that is seemly supported by a huge body (of fake people).

My question is, where do I go to learn about how this might be implemented, or contacts I can ask about the details that need to be fleshed out or refined?


texts: Clustering with probabilities / vector quantization with arbitrary distance measures

texts:
Suppose I'm given $n$ points $x_1,\dots,x_n$ in some space $\mathcal{S}$ (think: $\mathbb{R}^d$), and probabilities $p_1,\dots,p_n$ that form a probability distribution (so $p_1 + \dots + p_n=1$).  Imagine I have a source that outputs a point by choosing among the $n$ points according to the probability distribution $p_1,\dots,p_n$.  Also, I have a distance measure $D(\cdot,\cdot)$ so that $D(x,y)$ is the dissimilarity between two points $x,y$.

I want to design a codebook $y_1,\dots,y_m \in \mathcal{S}$ that provides low-distortion encoding for this source, where $m$ is given and $m<n$.  The point $x_i$ will be mapped to the $y_j$ that is most similar to $x$; then I'll transmit $y_j$ instead of $x_i$.  This incurs distortion $D(x_i,y_j)$.  Let $f(\cdot)$ be the function that maps $i$ to $j$, i.e., $y_{f(i)}$ is the $y$-point that is nearest to $x_i$.  The expected distortion of a codebook is
$$\sum_{i=1}^n p_i \cdot D(x_i,y_{f(i)}).$$
Given the $x_i$'s, $p_i$'s, and $m$, I want to find a codebook $y_1,\dots,y_m$ whose distortion is as small as possible.

Equivalently, this can be phrased as a clustering problem.  I'm given $m$, and I want to cluster the points $x_1,\dots,x_n$ into $m$ clusters, with one centroid for each cluster, such that the expected distance from each point to the centroid of the cluster containing it is as small as possible.  (This expected distance is computed by taking a weighted average over all the points $x_i$, weighted by the probabilities $p_i$.)

Are there any reasonable algorithms for this?  This reminds me of clustering, but I've never seen clustering algorithms that take into account probabilities $p_1,\dots,p_n$.  Alternatively, this reminds me of vector quantization, but the methods I've seen for vector quantization all focus on the $L_2$ distance metric (i.e., $D(x,y)=\|x-y\|_2$), and here I have a different distance measure -- in fact, it's not even a metric.  Those methods don't seem to generalize in any clear way to an alternative distance measure.  I do have $D(s,t) \ge 0$ and $D(s,t)=D(t,s)$ and $D(s,s)$ for all $s,t$.


texts: Simulating a TM with a 2-head, right moving TM

texts:
Is it possible to simulate a regular Turing Machine with a TM with the following specs?

There are two heads, one of which can read, one of which can write
Both heads can only move right
When a head reads (or it writes) it moves right

I know it's possible to simulate a TM that only moves right. But, is it possible to simulate the left moves as well?


texts: Does any parser ever parse non deterministic unambiguous context free grammar?

texts:
I have been informed parser parses unambiguous context free grammars of $DCFL$.

I was wondering if there could be a parser which could make a parsing table for unambiguous grammars of $NCFL$?

Note: This has been discussed here briefly in comments.


texts: Teaching NP-completeness - Turing reductions vs Karp reductions

texts:
I'm interested in the question of how best to teach NP-completeness to computer science majors.  In particular, should we teach it using Karp reductions or using Turing reductions?

I feel that the concepts of NP-completeness and reductions are something that every computer science major ought to learn.  However, when teaching NP-completeness, I've noticed that the use of Karp reductions has some downsides.

First of all, Karp reductions seem to be unnecessarily confusing for some students.  The intuitive notion of a reduction is "if I have an algorithm to solve problem X, then I can use it to solve problem Y, too".  That's very intuitive -- but it maps much better to Turing reductions than to Karp reductions.  As a result, I see students who are trying to prove NP-completeness get led astray by their intuition and form an incorrect proof.  Trying to teach both kinds of reductions and emphasizing this aspect of Karp reductions sometimes feels a little bit like needless formalism and takes up unnecessary class time and student attention on what feels like an inessential technical detail; it's not self-evident why we use this more restricted notion of reduction.

I do understand the difference between Karp reductions and Turing (Cook) reductions, and how they lead to different notions of NP-completeness.  I realize that Karp reductions give us a finer granularity of distinctions between complexity classes.  So, for serious study of complexity theory, Karp reductions are obviously the right tool.  But for computer science students who are just learning this and are never going to go into complexity theory, I'm uncertain whether this finer distinction is critical is critical for them to be exposed to.

Finally, as a student, I remember feeling puzzled when I ran across a problem like "tautology" -- e.g., given a boolean formula, check whether it is a tautology.  What was confusing was that this problem is clearly hard: any polynomial-time algorithm for it would imply that $P=NP$; and solving this problem is obviously as hard as solving the tautology problem.  However, even though intuitively tautology is as hard as satisfiability, tautology is not NP-hard.  Yes, I understand today why this is the case, but at the time I remember being puzzled by this.  (What went through my head once I finally understood was: Why do we draw this distinction between NP-hard and co-NP-hard, anyway?  That seems artificial and not very well-motivated by practice.  Why do we focus on NP rather than co-NP?  They seem equally natural.  From a practical perspective, co-NP-hardness seems to have essentially the same practical consequences as NP-hardness, so why do we get all hung up on this distinction?  Yes, I know the answers, but as a student, I remember this just made the subject feel more arcane and poorly motivated.)

So, my question is this.  When we teach NP-completeness to students, is it better to teach using Karp reductions or Turing reductions?  Has anyone tried teaching the concept of NP-completeness using Turing reductions?  If so, how did it go?  Would there be any non-obvious pitfalls or disadvantages if we taught the concepts using Turing reductions, and skipped the conceptual issues associated with Karp reductions?

Related: see here and here, which mentions that the reason why we use Karp reductions in the literature is because it enables us to distinguish between NP-hardness and co-NP-hardness.  However, it does not seem to give any answer that's focused on a pedagogical perspective of whether this ability is critical for the learning objectives of an algorithms class that should be taken by every CS major.  See also here on cstheory.SE, which has a similar discussion.


texts: Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

texts:
I'm trying to prove that

$L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$.

I'm not sure whether to reduce the halting problem to it or not. I tried to construct a new machine $M'$ for $(\langle M \rangle,w)$, such that $M'$ visits $q_0$ twice, iff $M$ halts on $w$. This is specific $q_0$ given to me, but I didn't come to any smart construction, which would yield the requested. Maybe it's easier to show that it's $RE$ and not $coRE$? It is obvious that it's in $RE$, and I need to show that $L_2^{c}$ is not in $RE$.

What should I do?


texts: Repeated subgraph isomorphism query for single-edge addition for bounded degree graphs

texts: I have a source undirected colored graph $G$ and a base query graph $g$. I know $g$ is subisomorphic to $G$ and now I want to identify which edges I can add to $g$ to preserve subisomorphism. That is, for any pair of vertices $(v_i, v_j)$ in $g$ if $g' = g \cup e_{i,j}$ is $g'$ still subisomorphic to $G$? what I'm trying to find is the set of single-edges I could add to $g$ while retaining subisomorphism. If it helps my graph has bounded degree < 5, and there are always fewer than 100 nodes.


texts: Why is the VC dimension different on intervals and half intervals?

texts:
As I read this lecture for being familiar with VC dimension we find on p. 8:

  VC(half intervals in $\mathbb{R}$ ) = 1    ....  no subset of size 2 can be shattered

  VC(intervals in $\mathbb{R}$ ) = 2         ....  no subset of size 3

It's not clear to me. I read on Wikipedia about the difference of  Half Interval and Interval and why VC dimension are different.

For example can this set be half intervals or intervals?

$$
\{ (-\infty \le x \le a) \, \left|\, a \in \mathbb{R} \right. \}
$$

Any direction or hint on this problem?


texts: Prove the red blue separation problem is NP-complete

texts:
Consider the following problem: given a set of $m$ red points and $n$ blue points in the plane, find a minimum length cycle that separates the red points from the blue points. That is, the red points are inside the cycle and the blue points are outside the cycle, or vice versa. This problem is called the red blue separation problem.

I am trying to reduce the Traveling Salesman Problem (TSP) to this but I am getting nowhere. Can you please help me with this? Any help is appreciated.


texts:
Prove that $L=\{a^{n}b^{m}c^{k}\mid n\leq(m+k)\}$ is not regular.

I used the pumping lemma as follow:

there exists $n\in \mathbb{N}$

$z=uvw$

$|uv|\leq n  , |v|\geq1$

$uv^iw$ is a string in L, so I need to find i such that $uv^iw$ $\notin L$

I rewritten L so that condition will appear as follow: $n-m\leq k$

I set $i$ to be $k+1$ placing it in $uv^iw$ I get $uv^{k+1}w$==> $a^nb^{k+1-n}c^k$ and we can see that the inequality is incorrect: $n+k+1-n\leq k$
simplfying the expression: $1\leq 0$ which is false.

is this way of proving non regular language is correct?


texts: Find all substrings that fit the mask with asterisks

texts:
There is a problem.

Given string $text$ containing only letters and string $mask$ containing letters and asterisks (*), where asterisk means substitution of zero or more letters, find all substrings of $text$ that fit $mask$.

There is an example: let's $text=cabccbacbacab$, $mask=\textbf{ab}*\textbf{ba}*\textbf{c}$. The algorithm should give substrings $abccbac$, $abccbacbac$, because $abccbac = \textbf{ab} + cc + \textbf{ba} + \textbf{c}$, $abccbacbac = \textbf{ab} + ccbac + \textbf{ba} + \textbf{c}$.

I have tried to split mask into tokens (for above example $\textbf{ab},\textbf{ba},\textbf{c}$) then find all occurrences of every token in $text$ then make cartesian product of all relevant occurrences and check every token for condition.

Is there more efficient solution for this problem?


texts: Complexity of list coloring $K_n$ with $n$ colors

texts:
The list coloring problem is, given a set $L(v)$ colors for each vertex $v \in G$, is there a proper vertex coloring, $c$, of $G$, such that $c(v) \in L(v), \forall v$.

I was wondering, for complete graphs $K_n$, is list coloring NP-complete? Does this change if $\bigcup_{v \in K_n} L(v) = \{1,2\dots n\}$?


texts: What is the difference between an algorithm, a language and a problem?

texts: It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and considering problems? And how do these relate to the concept of a language in formal language theory?


texts: How Data Compression relates to Estimating Distribution?

texts:
I recently read this paper Mahoney, 1999.
And encountered this line,

optimal compression of a probabilistic language L with unknown distribution (such as English) using an estimated distribution M (an encoding of length −log2 M(x) bits for each string x) is M = L, by the discrete channel capacity theorem.

Can you please explain what this means and what is the relation between data compression and estimation of distribution?


texts: Why are CFLs not closed under intersection?

texts: I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection.  I was wondering if there was a simple proof or example demonstrating that CFLs are not closed under intersection.


texts: Looking for the English name of algorithm using a precomputed array for interval sum computation

texts:
I am looking for the English name of the following algorithm:

We are given an array a with numbers and we need to be able to efficiently retrieve the sum of a continuous interval [f,t] of numbers in that array. In order to do that we precompute an array sums(of size size(a) + 1) that stores the sums of the prefixes of the initial array. More formally sums[i] = a[0] + a[1] + ... a[i-1]. This array can be constructed with linear complexity and now in order to compute the sum of the numbers in the interval [f,t], we simply compute sums[t]-sums[f-1].

Direct translation of the name of the algorithm(or more precisely the datastructure) that I've seen used in Bulgaria is prefix array, but in my experience direct translation often turns out to be wrong when it comes to algorithms and data structures.

How is this algorithm(or datastructure) called in English?


texts: Is the halting problem always decidable for non-universal programs?

texts:
For every non-universal computable program $P$ that takes input of type $D$ does there exist some total computable function $g$ that takes an input $I$ of type $D$ and decides successfully whether $P$ halts on $I$?

Some concrete definitions:
A program $P$ that takes some data type $D$ as input is computable iff there exists some total computable function $h$ that takes a input string and returns a $D$, and some Turing machine $T$, which takes a binary string, such that $P(h(I)) \cong T(I)$ for all strings $I$. "$\cong$" includes both not halting as well as both producing the same output.

A program $P$ that takes some data type $D$ as input is universal iff there exists some total computable function $f$ that takes both a description of a Turing Machine and an input string and produces something of type $D$ such that for every Turing machine $T$ and every string $I$, $P(f(T, I)) \cong T(I)$.


texts: Confused about NP-Complete Proof Using Reduction

texts:
Consider a job schedule decision problem with only one machine takes input $\{(r_1,p_1,d_1),(r_2,p_2,d_2),...,(r_n,p_n,d_n),K\}$; where $r_i$ is the start time for the ith triple, and $p_i$ is the process time of the triple; and $d_i$ is the deadline.Require for each $i$, schedule a job at time $t_i$ such that $r_i≤t_i≤d_i−p_i$. Goals to decide whether we can schedule $K$ number of compatible jobs.

I try to show that this problem is at least as hard as SubsetSum problem.

Consider a instance of input to SubsetSum. $\{a_1,a_2,..a_n;T\}$

Assume that $∃ I⊆\{1,2,..n\}$
such that $∑_{i∈I}a_i=T$; then we can design a transformation such that assigns a subset $\{r_i,p_i,d_i\}$ some value, and show that taking this set as input to schedule problem will also return True. For example, assign start value to each of job to be 0, process time for each job to be $a_i$, deadline for each job to be $\sum_{i\in I} a_i$. I have prove the $\implies$ direction

However, my problem here is about doing converse proof. We have to show that schedule decision problem taking an instance return true implies that SubsetSum taking kind of "inverse transformation" of that instance also returns true.

My understanding of prove converse direction is that we need some sort of inverse transformation. For example, given any arbitrary set of triple $\{(r_i,p_i,d_i)\}$, if this set accepted by schedule problem, then we need to find some "inverse transformation" transform the triples into some array, and a target value that can be accepted by SubsetSum. And this "inverse transformation" compose with our original transformation (designed for ($\implies$) direction proof) should be some identify transformation.

OR

Can we only give the input that has start value to each of job is 0, process time for each job is $p_i$, deadline for each job to be $\sum_{i\in I} p_i$. Basically, use the transformed input from the direction of ($\implies$)

And assume that this set of input accepted by schedule decision problem, we want to show that using the sum over process time and the deadline time as input to SubsetSum can also return true.

I don't which approach is correct here


texts: Is $\{\varepsilon\}$ a conventional way to mark the empty language?

texts: I am grading an exercise in Automata and Formal Languages and see many of the students use $\{\varepsilon\}$ as the empty language. At first I thought this was an error, and I have asked the lecturer who confirmed. But I keep seeing this and I'm losing my confidence. Is this kind of thing used by anyone? Meaning, does anyone use $\{\varepsilon\}$ as the empty language (even though it would "override" the obvious meaning of the singleton of $\varepsilon$)?


texts:
This question was asked and answered but I cannot understand the solution.

Why is it sufficient to test all strings of |Q| + 1 length?
Why should special state q be found?

the original question:
Show that the set of all TMs that move only to the right and loop for some input is decidable

L2={ M | M is a TM and there exists an input w such that in the computation of M(w) the head only moves right and M never stops}


texts:
I have to craft up a number made of 19 digits so that, after some mathematical operations made 11 times, the resulting sum of the remainders of the first ten operations is equal to the the remainder of the eleventh operation. The eleven calculations are as follows. I need to reverse them in order to be able to craft up the x.

op_10 : (x / 256) mod 256 => This is the remainder that must be equal to the sum of the ten remainders below.

op_0 : (x / 72057594037927936) mod 256 => 1st remainder

op_1 : (x / 281474976710656) mod 256 => 2nd remainder

op_2 : (x / 65536) mod 16 => 3rd remainder

op_3 : (x / 1048576) mod 16 => 4th remainder

op_4 : (x / 16777216) mod 16 => 5th remainder

op_5 : (x / 268435456) mod 16 => 6th remainder

op_6 : (x / 4294967296) mod 16 => 7th remainder

op_7 : (x / 68719476736) mod 16 => 8th remainder

op_8 : (x / 1099511627776) mod 16 => 9th remainder

op_9 : (x / 17592186044416) mod 16 => 10th remainder

Is there such an algorithm?
x is the number i need to craft up.