texts: Assignment Problem - multiple tasks, but only one chosen based on their preference (cost)

texts:
I've looked at Hungarian algorithm and Knapsack problems and neither quite hit the nail on the head. I've been trying to best rephrase my question while searching for answers and haven't got anywhere.

I have agents j and tasks i. Each agent can have between 1 and 4 task preferences (each with the cost 0-3), but must have only one task assigned by the end.

Each task also has a maximum number of agents that can be assigned to it (depending on the task).

Is there an algorithm out there that will minimise the overall cost, while maximising the amount of agents assigned to each task?

I hope that's clear, never really done this sort of thing before!


texts: Depth-2 circuits with OR and MOD gates are not universal?

texts:
It is well-known that every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be realized using a boolean circuit of depth 2 (over the variables, their negation and constant values) containing AND gates in the first level and one single OR gate in the upper level; this is simply the DNF representation of $f$.

Another type of gate which is of great interest in circuit complexity is the $MOD_m$ gate. The usual definition is the following:

$$\mathrm{MOD}_m(x_1,\dots,x_k)=\cases{
  1 & if \(\sum x_i \equiv 0 \mod m\) \\
  0 & if \(\sum x_i \not\equiv 0 \mod m\) \\
}$$

These gates sometimes have surprising power; for example, any boolean function can be represented by a depth-2 circuit having only $\mathrm{MOD}_6$ gates (this is folklore but I can elaborate is someone is interested).

However, another folklore is that circuits with a single OR gate at the top and $\mathrm{MOD}_m$ gates in the bottom layer (with $m$ being fixed once and for all, and in particular being the same for all the gates) is not universal, i.e. for any value of $m$, there are boolean functions that cannot be computed by $\mathrm{OR} \circ \mathrm{MOD}_m$ circuit.

I'm looking for a proof for this claim, or at least some direction.


texts: Bubble sort that ignores rightmost sorted parts

texts:
Initial Bubble sort pseudocode(Typical):

1)foreach Element in array

2)  initialise a flag that flips whenever a swap is done

3)  Starting from the element, attempt to swap and update flag

4)  If no swap is done, i.e flag remains true, break

We can improve the sorting algorithm further as values that are already sorted at the end of the array should not be checked in the subsequent passes. For example, when sorting [4,2,3,1,5,6], we get [2,3,1,4,5,6] after the first pass. We can see by observation that last 3 values (4,5,6) are already sorted and hence need not be looked at in the next pass.

I would think given the old source code[and my explained pseudocode], the checks will still be done in the inner loop even when previous outer iterations, no swap was done to a particular interval. I tried implementing a 2nd flag and an index variable to note the location which marks the start of a sorted interval. Here's my implementation in Java,I think it works, but I’m not sure whether I covered all cases.

  Can someone verify if my algorithm is correct and if there is some flaw with it, please suggest an alternative.

The new pseudocode of my algorithm will be

1)foreach Element in array

2)  initialise a flag that flips whenever a swap is done

3)  if the localSorted flag is still true at the previous positions, break

4)  Starting from the element, attempt to swap till end of array and update flag

5)      Whenever a swap is done, the old localSorted status is questionable, hence set to false

6)      If the localSorted status isnt changed even in the inner loop, break out

7)      Otherwise set the localSorted at the first location

8)  If no swap is done, i.e flag remains true, break

PS: Pardon me if my pseudocode is not really clear.


texts:
I am trying to prove or disprove the following statement:

  If $A = (\Sigma, Q, \delta, q_0, F)$ is a complete DFA where $F \neq \emptyset$ then $L(A) \neq \emptyset$

So my initial thinking is to find a counter example. If say we were to construct a DFA with one accepting state, and that state is never reached then the proposition is false.

For instance :

Assume we have the following automaton

So my question is , are we allowed to have such a state in a DFA ?


texts: Construct Optimal Directory Trees Efficiently

texts:
Question:

I want to construct a optimal directory tree structure to access $n$ ($n < 256$) elements using only the keyboard with as few key presses as possible. For this one could consider the directory as double linked list with connections between the first and the last element. To access element E, one then would traverse the list until the appropriate subdirectory S, enter S and restart from there until E is selected.

There are some natural requirements:

the elements in the tree structure are lexicographically ordered
the arity of the tree might be >2.
I would like to apply custom weights to some elements
the cost to be minimised is the weighted average of the total click count to access all elements (i.e. $c = \sum_{e \in E} w(e)*c(e)$, where $E$ is the set of elements, $w(\cdot)$ the weight for each element and $c(\cdot)$ the cost to access each element. $c(\cdot)$ depends on the chosen directory structure, of course.)

I'm struggling to find a good solution here. I do not know any standard tree that would fit in here as there might be no elements in intermediate nodes.

So, I'm looking for hints to literature. Maybe someone even knows an efficient algorithm? Bruteforce in Python takes too long to run, Bruteforce in C++ take too long to code :).

Motivation

I feed my stereo from a single board computer using the DLNA protocol. I want to access my music (artist-folders are the elements) as fast as possible. The stereo only supports "up", "down", "enter" and "escape" to navigate.

Clarifications

$c(e)$ is the number of clicks needed to access element $e$ from the top of the directory. $c(\cdot)$ depends on the directory structure. To access the lexicographically third element in a long list, one needs exactly 3 clicks (2x down, 1x enter). For the directory structure $((a, b), (c, d))$ one would only need 2 clicks to enter $c$ (2x enter).

Naming the subdirectories will not be a problem. Since the elements keep their order, I can use the names of the first and the last elements, as in a dictionary.


texts:
I've been looking over sorting algorithms for linked list and here's what I came up with.

As we know, for element access arrays will work better than linked list. Also, there is the benefit of elements being stored in consecutive memory locations: due to spatial locality of cache, arrays give better performance.

Thus for sorting linked list:

Extract all elements from linked list to a array: $O(n)$
Sort the array using quicksort: $\Theta(n \log n)$
Store the elements in linked list: $O(n)$

Is this approach better than other approaches for sorting linked lists such as using merge sort directly, as described on geeksforgeeks.


texts: How to create algebraic structures in code

texts: I've been searching around google and this site and I haven't been able to find the answer to this. How are algebraic structures (like a set and its elements, groups, rings, etc.) defined in code (in any language)? Like, if I wanted to "do things" with an arbitrary ring, how would I go about constructing that ring?


texts:
HAMCYCLE = {<"G"> : G is a simple undirected
graph that has a Hamiltonian cycle}

CUBIC CYCLE = {<"G"> :G is a simple undirected graph that contains
a simple cycle of length at least |V (G)|^1/3}
The reduction i figured out is :
G has a ham-cycle <==> G has a cubic cycle of a given length(V^1/3).
Prooving ==> part is simple as we have to show that if a cycle of V exists, then in G a cycle of V^1/3 exists.
But i got stuck in proving the other direction.
Any insights would be helpful.


texts: If my computer is a 32 bit system,it has a 32 bit address right?But when i print any memory address in C why do i get a short value?

texts:
For example

printf("%u",&a);

gives me output
65524


texts:
I want to detect cycles in an undirected graph such that I get a list of all edges/vertices which form each cycle. For a graph G({a,b,c,d}, {a-b, b-c, c-d, d-a, b-d}) this would be {a, b, c, d}, {a, b, d}, {b, c, d}.

I have read this and I think that when the iterative pseudocode from Wikipedia finds a back-edge then I can say the graph has a cycle. But I don't know how to find out which vertices/edges the cycle consists of.

Can you please help with an algorithm which would take a graph as input (or the information from DFS) and output list of lists describing the cycles?


texts: Why is it impossible to reverse a hash code? There could be some way to crack this coding?


texts: Does the vehicle routing problem and variations have approximation ratios or a PTAS?

texts:
This is a somewhat big question since there are many variations on the VRP. The most studied seems to be the capacitated version, the CVRP, but variations considering time windows, backhaul/linehaul, etc. are also studied, and of course characteristics of the graph and number of vehicles matter too. The most general VRP with no capacity constraint and one vehicle is the TSP, which of course can't be approximated within any constant, so neither can the VRP.

Is there research on the approximation complexity classes for variations? Such as where the graph is Euclidean, has triangle inequality, is symmetric v asymmetric, CVRP, VRPTW, DVRP, etc.

I was specifically looking at the Clarke-Wright savings algorithm for these questions. I haven't found anything on its approximation ratio, and I realized it might be because the entire problem doesn't have approximation ratios.


texts: Designing a parallel algorithm to find the second largest item in an array

texts:
Using pseudocode, I need to design a parallel algorithm that, when given k keys, a[0], a[1], a[2],... a[k-1] stored in an unsorted array a, would find the second largest key in it.

I'm new to parallel computing, so I know that in terms of sequential programming, we can use bubble sort with two passes. First pass gets your the largest element, while the second pass will get you the second largest element, the goal. Should we split the bubble sorta via parallel processing, we only need to do one pass each iterations largest element to find the second largest. My problem is I don't know how to exactly 'parallelize' the algorithm.


texts: Prerequisites for Approximation Algorithms

texts:
I'm new here, so I apologize if this is not the appropriate place to ask this question.

I just started a graduate level course on approximate algorithms, and I am falling behind fast. The class is very theoretical and we are asked to prove approximation problems. We've covered traveling salesman problems, greedy algorithms, set cover, knapsack and makespan in the course of a couple weeks.

I understand the general sense of what the algorithms do, but I need help on intuition of what to do in proofs when trying to solve n-approximation problems.

What readings, topics, or skills will help my ability to solve approximation problems? After I see the solution, it makes sense, but I don't know how one would even start to think of that solution in the first place.

Thank you for any help you can offer.


texts:
Hello dear stackexchangers,

I have a simple question, and I would like to say that I am not a scientist. When I read the problem statement on this link: http://www.claymath.org/millennium-problems/p-vs-np-problem

  Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

I understand the problem, but in order for the finder to prove he solve the problem, if we take 100 students from 400, how many "incompatible" pairs and how many combinations of 100 students without these pairs should be proposed and generated in order to make something really "probing"? In a polynomial way of course.

Because the statement is not really clear about it, in my humble opinion.

Sincerely yours


texts:
I've got a theoretical exercise at my university which belongs somewhere between alpha blending and ray casting – to be honest, I’m not sure. It says, that we are looking at a voxel (1-centimeter distance) which consists of different colors (sand: yellow, stone: red, oil: green and water: blue) where sand and water are transparent, stone is half transparent and oil is completely opaque. This information led to the following color value:
80 | 120 | 245
The value ranges from 0 – 255. The function values of the given elements are: sand (50-100), oil (100-150), water (180-200), stone (210-250). Now we are supposed to calculate the actual value of the pixel given the formula:

Color x = a_s * c_s (1 – a) + c ;

opacity c = a_s (1-a) + a

Where a_s stands for alpha sample and c_s for color sample.
I’m already thinking about this problem since days. I can’t differentiate between a_s and a. I’m quite sure I have to solve this problem recursively but how do I initiate the first step?... Suppose that a is 0 at the beginning and just use the information in the text? Also is there any meaning regarding the order of the calculation?
Maybe someone understands my problem.

EDIT INFORMATION:
Thank you both for your help!

I fully understand that it is really unclear what we are supposed to do because the wording of the exercise is pretty messy. I try to be more precise:

The whole exercise, consisting of 5 subtasks, gave us the following information (translated from my native language): “You are given a volume data set regarding the earth structure of an earth field. The following relationship between these density values exists:

Sand: density 50-100, Oil: density: 100-150), Water: density 180-200; Stine: density 210-250. Values range from 0-255.

From a)-d) we were supposed to draw the transfer functions of these opacities. D) says: “Draw the transfer function for the opacity given that sand and water are transparent, oil is semi-transparent and stone fully opaque.

Now coming back to the initial question: “An observer looks from the left side at the voxels with the same density from a distance of 1 centimeter. The voxel influence the calculated color value with their initial colors (sand yellow, stone red, oil green, water blue) and the opacity given in subtask d), which is:

80 | 120 | 245.

Calculate the actual color value for the visible pixels (using the formulas above).
I (!) can just assume that the three digits represent a RGB code because the given colors of the elements could translate into: R=80=Stone; G=120=Oil; B=245=Water.
I also just assumed ray casting because there is a volume data set given, even though I recognize some formula elements of Alpha Blending in the formula given in the text. So that is why I’m so confused.


texts: Building an enumerating machine with a Turing machine

texts:
I have a Turing machine say M with a state diagram which decides a particular language...
I wanted to build an enumerating machine for the same..
Since its decidable..
I can use the following logic
Let s1,s2,...be list of strings in $\Sigma^*$
So an intuitive definition fo the enumerator is -

Repeat the following for i =1,2,3,...
Run M on si
If it accepts , print out si

But what i want to build is a state diagram for the enumerator... as enumertor also by definition has a transition function like $\delta$(q,a) = (r,b,L,c)
where q is the current state of the enumerator and a is the alphabet on the head of the working tape
so it moves to state r writes a b on working tape moves left and writes a c on the print tape...
c could be $\epsilon$ also in which case nothin get written on the print tape..
Also as per what i read.. The working tape of the enumerator is blank initially..
Does that mean i need to write on the tape s1,s2... one by one and then Run M on it.. ??
This is somewhat confusing to me.. If that is the case do i need to have one more state that writes the next string on the working tape after the M accepts it or rejects it and so now M can being execution with the new string...
So for writing on the working tape do i have to use transition function..
or is it like .. by default the enumerator runs over all strings in alphabet $\Sigma$ written over working tape
one by one with the transition function defined ?
Basically i am trying to write a state diagram for the enumerating machine which enumerates the language with alphabet only 0 and it enumerates only those string whose length is a power of 2.
I already have a Turing machine state diagram built for this so i wonder what will be the exact state diagram for the enumerating machine...?
**Just to highlight the confusion point and a question -

Do we assume that we will fill the enumerating machine working tape with words over the alphabet..one by one and then run the enumerating machine on it...which will print some words.
or
Does this process of writing on tape is also done by the transition function of the enumerating machine ?
Given a Turing machine state diagram ( the language is decidable by this machine) what will be the state diagram for enumerating machine and what new states will show up**

Thanks


texts:
Is it correct that in a matroid, the union of all the circuits and
    the intersection of all the bases do not overlap?

I susepect that is true from the equivalence in the definition for a
coloop from wikipedia:

  An element that belongs to no circuit is called a coloop.  Equivalently, an element is a coloop if it belongs to every basis.

Is there some relation between the intersection of all the circuits
and the union of all the bases?

Thanks.


texts: How would I make sure my compressed string has the smallest length possible?

texts:
I'm trying to make a function that takes a string and compresses the repeating blocks. The code I'm using is implemented in such a way that a single character like 'a' would be converted to '1(a)' resulting in a bigger length.

The code is something like this:

import re

def _format_so(bchars, brep):
    return '%i(%s)' % (brep, bchars) if bchars else ''

def char_rep(txt, _format=_format_so):
    output, lastend = [], 0

    for match in re.finditer(r"""(?ms)(?P<repeat>(?P<chars>.+?)(?:(?P=chars))+)""", txt):
        beginpos, endpos = match.span()
        repeat, chars = match.group('repeat'), match.group('chars')

        if lastend < beginpos:
            output.append(_format(txt[lastend:beginpos], 1))
        output.append(_format(chars, repeat.count(chars)))
        lastend = endpos
    output = ''.join(output) + _format(txt[lastend:], 1)
    return output

givenList = ['dwdawdawd', 'aaaaaaaaa', 'abcabcabca']
newList = []

for txt in givenList:
    output_so = char_rep(txt, _format=_format_so)

    newList.append(output_so)

print(newList)

Output = ['1(d)2(wda)1(wd)', '9(a)', '3(abc)1(a)']

I want to make sure that the output will have the shortest length possible. The previous example should output ['d2(wda)1wd', '9(a)', '3(abc)a']

What do you suggest as the best approach for solving this problem?


texts: Average prefix code length of every 4-sized frequency vector is bounded at 2

texts:
I'm trying to show that for every frequency vector $(p_1, p_2, p_3, p_4)$ such that $\sum_{i=1}^4 p_i=1$, the average word length outputted by Huffman algorithm is bounded at 2: If $(w_1,w_2,w_3,w_4)$ is the outputted code, then $\sum_{i=1}^4 p_i |w_i| \le 2$.

I've tried looking at the tree that is generated by Huffman algorithm, but the thing is that several different tree structures match different 4-sized frequency vectors and I can't tell something general about all of them.

Also, is there a more general theorem for $k, n$ (here $k=4, n=2$)?


texts: Passing a non-mutable argument by value or by reference?

texts:
A function can generally be defined to receive parameters by value or by reference. If we want to mutate an object inside the function and have those changes reflected outside the function, then it must be passed by reference.

If we don't want to mutate the object then we can choose between passing by value or by reference. The choice, in my experience, is based on whether or not it's expensive to copy the object. If it's cheaper to copy than to deal with the reference's indirection - pass by value, else - pass by reference.

1) Are there any other considerations that should be taken into account?

2) Wouldn't a compiler be better suited to make this choice instead of the programmer? Why, or why not?

To illustrate question 2, the programmer could simply indicate whether they intend to mutate an argument or not. If an argument will be mutated then it must be passed by reference. If it won't be mutated, then the compiler can choose between passing by value or by reference - whichever is faster.

3) Do you see any pitfalls in this approach to language/compiler design?


texts: runtime to a BFS flood-fill with multiple centres?

texts: If we have a flood fill algorithm which, given a number of centres reprenting pixels on an image, runs a BFS flood-fill on them, checking the pixels 4 neighbours, changing their colours and adding them onto the queue to have their own neighbours processed if they have not been. What is the runtime, It seems it would be O(n) where n is the number of pixels but some sources have said it should be O(4^n). And how would this runtime change if the number of centres were changed, such that it was a multiple or fraction of n.


texts: Language of the values of an affine function

texts:
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions of the multiples of $a$ plus a constant:

$$M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \}$$

Is $M$ regular? context-free?

(Contrast with Language of the graph of an affine function)

 I think this would make a good homework question, so answers that start with a hint or two and explain not just how to solve the question but also how to decide what techniques to use would be appreciated.


texts:
This question is based on the solution to topcoder SRM-620 question:

bool solve(int a, int b, int c, int d)
{
    if(a == c && b == d)
        return true;
    if(a > c || b > d)
        return false;
    return solve(a+b,b,c,d)||solve(a,b+a,c,d);
}

The time complexity is given by the recurrence formula

$$
T(a,b,c,d) =
\begin{cases}
c_1,         & \text{$a=c$ and $b=d$}, \\
c_2,         & \text{$a>c$ or $b>d$}, \\
T(a+b,b,c,d) + T(a,b+a,c,d) +c_3,      & \text{otherwise.}
\end{cases}
$$

How do I transform this to closed form if possible?


texts: Search algorithm for multidimensional space with custom topology

texts:
First, let's start with the description of the problem in dimension 1:
Let $T_0$ be a space with $n$ nodes organized in a tree structure, with $m$ of those nodes defined as target nodes. In this space, we define a function $f(node)$ that associates each node to the first target node in the path to the root.
So, as an example, given the space defined by the image below

we have the following: $f(F) = C$, $f(E) = E$ and $f(D) = A$ .
In this space, an "efficient" algorithm

We can now define a multidimensional space defined as the cartesian product of spaces similar to $T_0$, each with a different set of nodes and a different tree structure, and with two key differences:

The target nodes are defined on the product space
The order in the cartesian product space defines the priority when defining the distance between two solutions. So, any distance between any two nodes in a tree is shorter than the distance between any other two nodes in a space on its left on the cartesian product.

So, for example, a 2 dimensional space $T0 * T1$ defined as in the image below:

Given the set of target nodes ${(A, u), (B, x), (F, w), (C, x)}$, then

$f((B, x)) = (B, x)$
$f((B, z)) = (B, x)$
$f((F, x)) = (F, w)$ chosen over $(C, x)$ because distances in $T1$ is shorter than any other distance in $T0$ by definition

So, the question is, is there any algorithm that can be applied to this space in order to efficiently compute $f$?
So far I have considered two options:

Put all the elements of the space in a map with value the target node. While this approach has a great time complexity, the space complexity is way too high when the cartesian product is made of several $T_i$
Order the target nodes based on the distance defined above (single space topology + order in the cartesian product), but this approach has linear time complexity in the number of target node, which is less than ideal.

Neither of them is fully satisfactory, which is why I am reaching out for ideas.


texts:
Does every pure function have a branchless equivalent?

By pure function I understand a function that uses only its input values and no global state to produce the output.

By branchless function I understand a function that does not use if/else during its execution. A loop contains a branch with and unconditional jump. Constant loops can be unrolled.

As an example, here is the signum function:

function signum(x):
  if (x > 0) return 1;
  if (x < 0) return -1;
  return 0;

And here is a branchless version of the same function:

function signum(x):
  return (x > 0) - (x < 0);


texts: In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations?

texts:
I am a beginner learning theoretical computer science. While learning about CFG, I found that doing both leftmost and rightmost derivations gave me the same parse tree.

So, my question is: Why is it necessary to do both of them? What are we trying to really prove by doing them?


texts: 2-SAT Problem with additional constraints on variable?

texts:
Given a 2-SAT problem that is satisfiable. The solution to the problem can be found in polynomial time.

Adding an additional constraint:

The maximum number of positive literals that can have the boolean Value 1 is N. (i.e. a=positive literal, ~a=negative literal)

Is the problem still solvable in Polynomial time?

My assumption is it should be but I am unclear now to modify the original solution? Or are we looking at something similar to the Vertex Cover Problem?


texts: How solve this recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7

texts:
I am trying to solve the recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 but without success.

And from here I don't know how to continue?


texts: Is there a way to theoretically compare hash functions?

texts:
Say I am given two hash functions f1 and f2 is there anyway that I can prove one hash function will produce fewer collisions than another one? That is say for some domain assuming all values in the domain are equally likely to be chosen can I show that f1 will on average perform better than f2?

Looking up how to determine if one hash is better than the other lead me to some interesting articles of how to compare cannabis but I couldn't find much else.


texts: Can the running time be reduced to something lower than $O(d^4)$?

texts:
Imagine I have a weighted complete directed graph $G$ with $d$ vertices(so $d(d-1)$ edges) and I want to do the following:

Set $D$ to be a DAG with the same set of vertices but without any edges
sort the edge weights $c_{ji}$ of the original graph by size
From the biggest to the lowest edge weight: Add an edge $(j,i)$ to the DAG $D$ if we do not cause a cycle with it

Now I see two approaches to implement this.the first one is:

Set $D$ to be a DAG with the same set of vertices but without any edges
sort the edge weights $c_{ji}$ of the original graph by size
From the biggest to the lowest edge weight: Add an edge $(j,i)$ to the DAG $D$ if there is no path from $i$ to $j$

Now sorting can be neglected in complexity ( $O(d^2\log(d))$)

And number three is performed at most $d(d-1)$ times and to check if a path exists we can use BFS or DFS and the number of edges, unfortunately, can be as big as $d^2$ so we have $d^4$ in total

My second idea: Work with a reachability matrix and update the reachability matrix in every iteration of the loop...
But then updating the reachability matrix is again of complexity $d^2$ because if we set an edge from $j$ to $i$ then denoting the ancestors of $j$ by $k_1$ and the descendants of $i$ by $k_2$ we need to set $R(u,w)=1$, $R(u,i)=1$, $R(j,w)=1$ for any $u$ in $k_1$ and $w$ in $k_2$ ....
Assuming that in the worst case that each of $k_1$ and $k_2$ have $d/2-1$ vertices we get a complexity of $d^2$
That we need to update the reachability matrix more than $O(d)$ times can e.g. be seen by looking at bipartite graphs...
So I'm again stuck with the same complexity... Is there actually a more efficient solution?


texts: Rice Theorem - Problem to understand and apply it

texts:
I have struggle to understand the Rice Theorem.

My understanding of Rice Theorem:

The purpose of this Theorem is to proof that some given language L is undecidable iff the language has a non-trivial propertie.

So, if I want to apply this Theorem I have to show that the following conditions are satisfied:

1) There are two TM's which have the same language and they are either both in the language $L(M_1)=L(M_2)$ or neither is in L ($M_1 \wedge M_2$ are no specific (picked) machines).

2) I have to show that there exists two specific TM's: $M_1'$ which has the property and $M_2'$ which doesn't have the property.

Is this correct?

Perhaps someone can give an example, so that I know how to apply the rice theorem.

What's about the language: $L=${$<M>$|$\emptyset$ $\subseteq$ $L(M)$}

For the first condition:

There are two turing-machine's which have the same language and doesn't accept the language L.

For the second condition:

$M_1$ is the turing-machine that accepts all, and...
$M_2$ is the turing-machine that rejects all.

So both conditions are true which implies I can apply the Rice Theorem?

Thank's for your help.


texts: Is there any algorithm that finds the common edges and vertices between two graphs? Its not a common subgraph problem though, the edges which are common between the two graphs may not be connected to each other, may be far apart. How to find all the common edges in the graph? Like finding the common subgraphs between two graphs such that none of the subgraphs are connected to each other. Like these two graphs, the black and the blue part are the uncommon part...


texts: How many comparisons do we need to find min and max of n numbers?

texts:
Suppose we have given a list of 100 numbers. Then How can we calculate the minimum number of comparisons required to find the minimum and the maximum of 100 numbers.

Recurrence for the above problem is

$$T(n)=T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + 2$$
$$\approx 1.5 \times n - 2$$

hence

$$T(100)=1.5 \times 100 - 2 = 148$$

But by solving like as I've mentioned below, I'm coming up with the ans 162

We can divide list of 100 numbers in two list (50,50). Now upon combining the result of these two list 2 more comparisons will be required. Now recursively we break the lists like below, which will make a binary tree

$$100 \implies (50,50)$$
$$50 \implies (25,25)$$
$$25 \implies (12,13)$$
$$12 \implies (6,6), 13 \implies (6,7)$$
$$6 \implies (3,3), 7 \implies(3,4)$$
$$3 \implies (2,1), 4 \implies (2,2)$$

By combining the results upwards in the tree with 2 comparisons on merging each two lists I'm coming up with ans 162. What am I over counting.


texts:
I have some questions regarding this old contest problem:
Problem,
Solution

I don't quite understand the second paragraph of the second solution which begins with "Unfortunately, the permutation...".
Could anyone explain this part?


texts: Simple proof that finding a combinatorial map of a planar graph given as an incidence matrix can be done in polynomial time?

texts:
Suppose that I have a graph $G = (V,E)$, given as an incidence matrix of edges and vertices. Suppose that $G$ is planar, that is, it can be embedded in the plane without edge crossings.

I would like to construct in the combinatorial map corresponding to some (any) planar embedding.

That is, corresponding to each planar embedding $i : G \to \mathbb{R}^2$, there is a system of darts (half edges), with a fixed point free involution (corresponding to reversing the direction of a dart) and a permutation (corresponding to cyclically rotating through the darts which share the same head). This is the combinatorial map representation of the embedding $i$.

This is the representation of $G$ that I want to construct from the incidence matrix representation of $G$ in polynomial time.

I know (unless I'm misunderstanding the references) that there are a lot of algorithms that solve this problem in linear time. However, they are all very complicated.

Is there a simple algorithm (perhaps very inefficient) that shows that this construction takes polynomial time?


texts: Difficulty in understanding the proof of "Every context-sensitive language L is recursive" as given in the Peter Linz text

texts:
I was going through the automata text by Peter Linz. There I came across the proof the theorem below. I could not quite get the portion of the proof in bolds.

Every context-sensitive language L is recursive.
Proof: Consider the context-sensitive language $L$ with an associated context- sensitive grammar $G$, and look at a derivation of $w$
$$S \Rightarrow x_1 \Rightarrow x_2 ... \Rightarrow x_n \Rightarrow w$$.
We can assume without any loss of generality that all sentential forms in a single derivation are different; that is, $x_i \neq x_j$ for all $i\neq j$ . The crux of our argument is that the number of steps in any derivation is a bounded function of $|w|$. We know that
$$|x_j| \leq|x_{j + 1}|,$$
because $G$ is noncontracting. The only thing we need to add is that there exist some $m$, depending only on $G$ and $w$, such that
$$|x_j| \lt|x_{j + m}|,$$
for all $j$, with $m = m(|w|)$ a bounded function of $|V\cup T|$ and $|w|$. This follows because the finiteness of $|V \cup T|$ implies that there are only a finite number of strings of a given length. Therefore, the length of a derivation of $w \in L$ is at most $|w| m (|w|)$.
This observation gives us immediately a membership algorithm for L. We check all derivations of length up to $|w|m(|w|)$. Since the set of productions of $G$ is finite, there are only a finite number of these. If any of them give $w$, then $w \in L$, otherwise it is not. ■

What I could reason on my own is that, since context sensitive grammars are non contracting, we can apply the productions in steps, and if we get more $|w|$ symbols in the right sentential form, it then when we stop. So we shall be ultimately above to check where $w$ is generated by a context sensitive grammar or not.


texts: Are turing machines and formal languages the same mathematical object?

texts:
Turing's objective while building his concept was to formalise how humans do abstract reasoning.

Now correct me if I am wrong but that reasoning seems just an exercise where you manipulate a set of formal statements i.e. strings with no semantics attached to it.

So if Turing machines is the same as reasoning, is there an isomorphism (or something like that) between formal languages and Turing machines?


texts:
Given a biased $N$-sided die, how can a random number in the range $[1,N]$ be generated uniformly? The probability distribution of the die faces is not known, all that is known is that each face has a nonzero probability and that the probability distribution is the same on all throws (in particular, the throws are independent). This is the obvious generalization of Fair results with unfair die.

Putting this in computer science terms, we have an oracle representing the die rolls: $D : \mathbb{N} \to [1,N]$ such that $p_i = P(D(k)=i)$ is nonzero and independent of $k$. We're looking for a deterministic algorithm $A$ which is parametrized by $D$ (i.e. $A$ may make calls to $D$) such that $P(A()=i) = 1/N$. The algorithm must terminate with probability 1, i.e. the probability that $A$ makes more than $n$ calls to $D$ must converge to $0$ as $n\to\infty$.

For $N=2$ (simulate a fair coin from coin flips with a biased coin), there is a well-known algorithm:

Repeat “flip twice” until the two throws come up with distinct outcomes ((heads, tails) or (tails, heads)). In other words, loop for $k = 0..\infty$ until $D(2k+1) \ne D(2k)$
Return 0 if the last pair of flips was (heads, tails) and 1 if it was (tails, heads). In other words, return $D(2k)$ where $k$ is the index at which the loop was terminated.

A simplistic way to make an unbiased die from a biased one is to use the coin flip unbiasing method to build a fair coin, and build a fair die with rejection sampling, as in Unbiasing of sequences. But is this optimal (for generic values of the probability distribution)?

Specifically, my question is: what is an algorithm that requires the smallest expected number of calls to the oracle? If the set of reachable expected values is open, what is the lower bound and what is a class of algorithms that converges towards this lower bound?

In case different families of algorithms are optimal for different probability distributions, let's focus on almost-fair dice: I'm looking for an algorithm or a family of algorithms that's optimal for distributions such that $\forall i, \bigl|p_i - 1/N\bigr| \lt \epsilon$ for some $\epsilon \gt 0$.


texts: Count the number of Euler PATHs in directed graph?

texts:
I would like to find all Euler PATHs in a directed graph.
Counting (instead of finding) all the Euler PATHs is sufficient.
Circuits are not good for me, only Paths.

I am doing a problem, that I have derived to a point, where knowing the number of paths fast would help.
Currently, I have written (in c++) a recursive function that finds all of them, but it complexity grows quickly, so my algorithm gets slow fast. My algorithm is ~O(2^n). I would like a faster one for counting, if possible.

I have researched the topic, but I can only find proofs (for being NP complete, or polynomial) and algorithms for Euler Circuits in directed and undirected graphs. But again, I am looking for Euler Paths in directed graphs.

My graphs have only two nodes, but a lot of edges, that should be touched only once, like in an Euler Path.

So in summary:

Euler Path.
Directed Graph.
Only two nodes.
High edge count.
Edge costs are the same.

Here is an image to illustrate a possible set up.


texts: Are there a lambda-mu expression equivalent to the yin yang puzzle?

texts:
The yin yang puzzle was written in Scheme. Since it uses call/cc, it is not possible to express it in a pure lambda expression, unless we do a CPS transform.

However, given the fact that $\lambda \mu$-calculus have the power to model call/cc, is it possible to write an equivalent $\lambda \mu$-expression? I am still learning $\lambda \mu$-deductions, so this would be a good example to show how the deduction works.

There is no need to model the "display" command in a pure expression. Ideally only showing how the calculus keep looping and evaluates diffident terms again and again.

UPDATE My translation in $\lambda$-expression with CPS:

(λcallcc.callcc (λyin.callcc (λyang.yin yang))(λcc.cc cc)

In CPS, (λcc.cc cc) is what "call with current continuation" means. So the expression takes it as a parameter. This will result in assign the sub-expression starts λyin assign its continuation into parameter yin. And then in the body, the second callcc assigns the yang of sub-expression starts λyang into itself. Finally, apply yin yang.

Note the above translate is not full CPS, only the concept of call/cc has been translated. But it provides the same behavior and it is not hard to do a full CPS translate.


texts: The Ethernet MAC address FF:FF:FF:FF:FF:FF is reserved for broadcasts. If all frames are naturally broadcast in a LAN, what is the need for a broadcast address?


texts: How can I academically say that 'one computer is slower than the other'?

texts:
I'm writing a research paper and I have to basically say that one microcontroller is slower than an other microprocessor.  However, I'm worried that simply saying that it's 'slower' wouldn't be appropriate in a research paper.

Am I right?  Is it OK to just say that one processor is 'slower', or do I need to say something else?  What else could I say?  The best I have come up with is that one has 'less computational power' than the other or that the microcontroller has 'low computational power'. Unfortunately, these expressions don't seem to be too popular when searching online.

So, what would be a better and academically correct way of saying this?


texts: adding an edge, Is T still a MST to the new graph?

texts: Suppose I have a minimum spanning tree $T$ in a graph $G=(V,E)$ with positive edge weights $w$. Provide an algorithm that after adding a new edge $e$ with a unique weight $w(e)$ to $G$, returns true if $T$ will still be an MST.


texts: Does this state certify to be called as a deadlock?

texts:
I came across following problem:

  Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P (wait) and V (signal) functions. Consider the following C implementation of a barrier with line numbers shown on left.

void barrier (void)
{
    P(S);
    process_arrived++;
    V(S);
    while (process_arrived !=3);
    P(S);
    process_left++;
    if (process_left==3)
    {
        process_arrived = 0;
        process_left = 0;
    }
    V(S);
}

  The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.
  The above implementation of barrier is incorrect, because ... ?

I know that after execution of below steps, this may lead to halting of all processes:

| #process | process_arrived | process_left |
|----------|-----------------|--------------|
| 1        | 1 blocked       |              |
| 2        | 2 blocked       |              |
| 3        | 3 blocked       |              |
| 1        |                 | 1            |
| 2        |                 | 2            |
| 3        |                 | 3            |
| 1        | 4               |              | <-- (1)
| 3        | 0               | 0            |
| 2        | 1 blocked       |              |
| 3        | 2 blocked       |              |

Above each line shows which process executes and what changes it does to two variables.

After last step all processes have started their 2nd attempt to synchronize and all have incremented process_arrived twice. However, 2nd increment of process_arrived by p1 is done (<-- (1)) before process_arrived is reset to 0. Thus even after all processes incremented process_arrived twice, its value is 2 and all processes keep busy waiting for it to become 3.

  My doubt is does this state certify to called as deadlock as I dont see necessary requirements of deadlock hold here, namely circular wait and hold and wait. I guess process_arrived is a single resource here. How can a circular wait, hold and wait and hence deadlock occur with single resource? Or is there some other, more generalized definition  of deadlock which I am missing? Quick google defines deadlock as "a situation, typically one involving opposing parties, in which no progress can be made". Does that mean we can ignore necessary conditions of deadlock, in the context of computer science?

This is rather simple or subtle doubt, but I want precise understanding about whats called deadlock.

PS: I believe mutual exclusion requirement of deadlock is satisfied here as all updates to variables are protected by semaphore S


texts:
i have problem with resolution in first order logic

i have :

C1  :
¬ Loves(x,F(x) ) or Loves ( G(x) , x )

and

C2 :

¬ Animal ( X) or Loves ( jack , x )

can some one help me why the answer ( after Resolve C1,C2 ) is :

¬ Animal(F(jack) ) or Loves ( G(jack) , jack )

because my answer is :

x/ jack

then i will have :

C1 :
¬ Loves ( jack , F(jack ) ) or Loves ( G(jack),jack )

C2 :

¬ Animal ( jack ) or Loves ( jack,jack )

and i cant use resolution with Loves (jack,jack) and ¬ Loves (jack,F(jack))

thank you all !!


texts: Decidability of equivalence of two context free grammars

texts:
I got a question regarding the decidability of equivalence of two context free grammars:

  Construct a Turing machine that decides whether $L(G) = L(H)$, where $G$ and $H$ are two context free grammars.

This question is taken from Sipser's book on theory of computation.

My current idea is given that $G$ and $H$ are CFG's, we know that there exists push down automata that accept the languages described by $G$ and $H$. We can simulate a PDA on a Turing machine and hence, we can convert the problem to the equality of Turing machines, such that $M_1$ and $M_2$ are TMs and $L(M_1) = L(M_2)$ which is known to be undecidable.

My question is, are these steps fine to do (with a bit more formalism)?


texts: Does the space complexity of a recursive algorithm depend on the total no of recursive calls?

texts:
I am confused whether space complexity of a recursive algorithm depends on the total number of recursive calls or not.

Say I have an algorithm which has exponential function calls, but stack size is linear, so in that case we can say that space complexity is not proportional to number of recursive calls but if we say that does it depend on the total number of recursive calls or not, then does it make sense to make such a statement because after all stack is made because of the recursive calls only?

So is it better to say that "stack size depends on the recursive calls but not on the total number of recursive calls"? Is this statement valid?


texts: Is there a more up-to-date / wider-scope version of the 'Compendium of NP Optimization Problems'

texts:
When I was studying Comp Sci, we had Garey & Johnson as a course textbook, with a large collection of NP-Complete problems. But by that time you could also have a look at the Compendium of NP Optimization Problems, online.

However, it seems the 'Compendium' site has not seen any updates in several years. Is that indeed the case? Is there a more up-to-date compendium (perhaps in print) which accounts for further research and contains more problems in more domains?


texts: Does an Operating System inject its own machine code when you open a program?

texts:
I'm studying CPU's and I know how it reads a program from the memory and execute its instructions. I also understand that an OS separates programs in processes, and then alternate between each one so fast that you think that they're running at the same time, but in fact each program runs alone in the CPU. But, if the OS is also a bunch of code running in the CPU, how can it manage the processes?

I've been thinking and the only explanation I could think is: when the OS loads a program from the external memory to RAM, it adds its own instructions in the middle of the original program instructions, so then the program is executed, the program can call the OS and do some things. I believe there's an instruction that the OS will add to the program, that will allow the CPU to return to the OS code some time. And also, I believe that when the OS loads a program, it checks if there's some prohibted instructions (that would jump to forbidden adresses in the memory) and eliminates then.

Am I thinking rigth? I'm not a CS student, but in fact, a math student. If possible, I would want a good book about this, because I did not find anyone that explains how the OS can manage a process if the OS is also a bunch of code running in the CPU, and it can't run at the same time of the program. The books only tell that the OS can manage things, but now how.


texts: At what point do electrical signals become actually logic and programmable language?

texts: I get that one transistor can store a value of 1 or 0. That's not the problem. What I don't get is how the fact that a transistor represents a 0 can translate into logic? How do these transistors turn each other one or of? Is there a uniform pattern to the circuit? how do these electrical signals magically transform into mathematical equations? Is there a specific set of transistors that deal with addition? Another set for subtraction? How does the kernel transform this into programmable language? How the hell do these transistors know which pixels to colour and what to colour them with? WHAT VOODOO MAGIC IS THIS? I am pretty curious as to how this magical transformation happens, but I'm also pretty stupid, so please dumb it down a lot...


texts: Given arbitrary integers of $K$ and $M$, can deciding $2^K$ + $M$ is a prime be in $P$?

texts:
Given arbitrary integers of $K$ and $M$, is $2^K$ + $M$ a prime?
K = int(input('enter exponent K: '))
M = int(input('enter integer for M: '))

if AKS.Primality(2**K + M) == True:
    OUTPUT 'yes'
else:
    OUTPUT 'no'

I am not knowledgeable enough in number theory or any other field of mathematics to know the answer to this question.
Question
Is there a polynomial-time algorithm for this decision problem?


texts: Proving the language $L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$ is not regular using the pumping lemma

texts:
I am trying to learn about applying the pumping lemma and I'm not really sure how to go about proving this language isn't regular with the pumping lemma:

$L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$

Now I realize that the condition $m \equiv 0 \space mod \space n$, is essentially saying that $m$ is some multiple of $n$. Is it possible that could you go about proving that $L$ is not regular in the way that you can prove that $L = \{0^n 1^n\}$ is not regular since $m$ is a multiple of $n$, since $m = kn$ (where $k$ is some integer)?

Updated:

-- My attempt at the proof:

If the language $L$ is regular, then by the pumping lemma $\exists \space p \space | \space \forall s \in L \cap \Sigma ^{\geq p}  $.

Next by the pumping lemma $\exists x, y, z : s = xyz$, where $s$ is a string such that:

(1) $|y|\geq1$

(2) $|xy|\leq p$

(3) $\forall i\geq0, xy^iz \in L$

Now suppose we let $m = kp$, where $k$ is some integer, let the string $s = 0^p 1^{kp}, s\in L$ and $|s|\geq p$. By the pumping lemma the decomposition of $s$ is defined by $s = xyz$. Now we show that $\forall x, y, z$ that (1)-(3) do not hold.

If (1) and (2) hold, then $s=0^p1^{kp} = xyz$, with $|xy|\leq p$ and $|y|\geq 1$.

So $x = 0^u, y=0^v, z=0^w1^{kp}$

$u+v \leq p$, $v \geq 1 $, $w \geq 0$

$u+v+w = kp$

But (3) fails for $i=2$ since $xy^2z = 0^u0^v0^v0^w1^{kp} = 0^{u+2v+w}1^{kp} \not\in L$ since $u+2v+w \neq kp $

Hence $L$ is not a regular language.

Is this the correct way to go about this proof?


texts: Is there a name for an "array with no holes"?

texts:
How would you call an array [1, 2, 3, 4, 5, ...] that has (and ensures) the property of not having any undefined values through all its length.
"Dense" could work but it's not exactly what I mean, as it has more to do with zero/non-zero values.


texts: What is the difference between Coding and Programming?

texts:
In our daily life we use both coding and programming for the same meaning. I want to know the difference between these terms (If any).

If they are used for different meanings than please anyone can aware us about it, So we can correct ourselves.


texts: Finding which value I will be on after a certain number of steps

texts:
I have a fixed array: [a,b,c], I wanna loop through this 3-items-sized array for 7 times in order to find what I would get at that exact step.
The "value stack" for 7 would look like a b c a b c a.
Question is, how can I find what value would be at step 10, for example?

Input: getValueForStep( [a,b,c], 7 )
Output: a


texts:
So given an IP address it is converted into binary via calculating the binary of all different segments and then joining them.
For example, 12.32.18.01 converted into a binary it would amount to this number in decimal form 12*2^24 + 32*2^16 + 18*8 + 01
My question is why to go through all this trouble and calculation. Why not just get rid of the dots in the original Ip and then convert that integer into binary. So, for this example, the binary of the above example would amount to this integer in decimal 112 032 018 001. I mean what's the problem with second approach?


texts: Can we use domains other than the naturals in computability theory?

texts:
I wonder why people assume the domain of a computable function is $\mathbb N$? For example, in Wikipedia.

Can its domain be any countable set rather than $\mathbb N$?

Can its domain be an uncountably infinite set?


texts: Implementing Nesetril and Poljak's clique detection algorithm

texts:
I want to implement the clique detection algorithm by Nesetril and Poljak described in [1].

However, I can't seem to understand how the auxiliary graph $H$ is to be created and how it can be used to detect a clique. For instance, the paper suggests that to detect a clique of size $3\ell$ in a graph of size $n$, we construct an auxiliary graph $H$ of size $n^\ell$. For the detection of a clique of size $6$ in a graph $G$ of size $8$ for example, then the size of $H$ would be $64$ (i.e. $8^2$) and then checking for the presence of a triangle in $H$ which would indicate the presence of a clique of size $6$ in $G$.

Further down, while describing how to construct $H$, they stated that the vertex set of $H$ should be a subset of the vertices of $G$, and that the size of this subset is $\ell$. This is the first conflict. The second conflict is in the construction of the edge set. What is meant by $Y'$ in this sentence: $E(H)=\{ \{Y,Y'\} ; Y \neq Y' \text{ and } Y \cup Y' \text{ forms a complete subgraph in } G \}.$

The paper did not at any point after this sentence define what $Y'$ was.

Any explanation will be appreciated.

[1] J. Nešetril, S. Poljak, On the complexity of the subgraph
problem, Comment.Math. Univ. Carolinae 14 (1985) 415–419.


texts: A double recursive function (ping-pong) between function to itself complexity analysis

texts:
def RecFunc(n):
   if n <= 3:
      return 1

   return RecFunc( RecFunc(n/3) + RecFunc(n/2) + RecFunc(n/2) )

How should I start if it is nested inside? I know how to solve it without the outer RecFunc (with a recursive tree I assume) - But here there is an outer RecFunc and I don't know what to do!

Thanks to Steven for noticing a mistake I made (Misread the question and made it so RecFunc(4) will not halt)


texts: Many-one reducibility: why $A = \{1\}$ is not a counterexample to $\forall A : A \leq_m A \cup \{0\}$?

texts:
I'm looking at a textbook exercise that asks to prove or give a counterexample that $\forall A : A \leq_m A \cup \{0\}$.

$A \leq_m B$ is defined as:

$\exists f$ total, computable s.t. $\forall x \in A : x \in A \Leftrightarrow f(x) \in B$,

It then says in the answer sheet something to the effect of:

  The only counterexample is $A = \mathbb{N} \setminus \{ 0 \}$.

  Otherwise there is always an appropriate $f$:

  If $0 \in A$, $id$ is good enough
  If $0 \not\in A$, one such $f$ is

  $f'(x) = \begin{cases} x_0 & x = 0\\ x & otherwise\end{cases} $
  for some $x_0 \not\in A \cup \{0\}$.

However, before checking the answer sheet I was persuaded there were multiple such counterexamples.

In fact, I still don't understand what's wrong in my "proof" that $A = \{ 1\}$ is a counterexample.

It goes like this:

  Let $A = \{1\}$.
  Then $A \cup \{0\} = \{0,1\}$.
  Suppose such an $f$ as required by the definition exists.

  There are three cases, mutually exclusive by definition of
  function:

  $(1,0) \in f$, therefore $f(A) = \{0\} \neq A \cup \{0\} = \{0,1\}$
  $(1,1) \in f$, therefore $f(A) = \{1\} \neq A \cup \{0\} = \{0,1\}$
  $(1,c) \in f$ for some other $c$, therefore $f(A) = \{c\} \neq A \cup \{0\} = \{0,1\}$

  Therefore $f$ such that $f(A) = A \cup \{0\}$ cannot exist for $A = \{ 1 \}$. QED.

In particular, I don't see how, for the given

$f'(x) = \begin{cases} x_0 & x = 0\\ x & otherwise\end{cases} $

it holds that $f'(\{1\}) = \{1,0\}$

It seems to me that $f'(\{1\}) = \{1\} \neq \{0,1\}$.

What am I misunderstanding about either basic set theory or the definition of $\leq_m$?


texts:
I am trying to understand Multiway Cut, and basically how the Multiway Cut works. I am searching google many hours to find a good example to understand. A good example that I am trying to understand is this:

http://crab.rutgers.edu/~rajivg/studentTalks/multiwayCut.pdf

What I cannot understand, and here is the point I need your help, is how did he go from slide 12 to slide 13? How the graph on slide 13 was produced? How do I choose A1*,A2*,A3* ??


texts:
So, I'm trying to conceptualize something:

Say we have a weighed graph of size N. A and B are nodes on the graph. You want to find the shortest path from A to B, given a few caveats:

movements on the graph are regulated by a circular cycle of length 48, in such a manner that:

  cycle{

     0 <= L <= 24  movement IS possible

    25 <= L <= 48 movement IS NOT possible

  }

For simplicity's sake, we will call this cycle 'time'.
The distance between nodes A and B is equal to:

  shortest_distance(A to B) - 1 OR shortest_distance(A to B) + 1

Depending on their orientation
the weight of the edges represents the 'time' it takes to travel between nodes.

I'd like to create an algorithm that will give me the shortest path with these constraints in mind, assuming one is leaving from node A at time(cycle) = 12, traveling towards node B. The shortest path would be defined as the path which takes the least 'time'.

Step one would obviously be to take into account the orientation affecting the shortest distance (i.e. which way are they oriented by above), which would be a simple addition or substraction to the result of djikstra's algorithm

What I'm having trouble figuring out is how to account for the cycle in the algorithm... could it be as simple as just an if statement checking to see if the current cycle time is within the constraints that allow movement?

Would my idea be viable? If not, does anyone h ave any suggestions at different ways I should look at this problem?

I know this question seems really basic, but I just can't wrap my head around it.


texts: Sugiyama's algorithm: ambiguity in Barycentric Method for arc (edge) crossing reduction?

texts:
Context:

This question rises from the paper "Methods for Visual Understanding of Hierarchical System Structures" by Kozo Sugiyama, Shojiro Tagawa and Mitsuhiko Toda, which lays out a framework (the Sugiyama framework), for hierarchical graph drawing.

In the paper, Sugiyama et al. introduce the Barycenter Method for reducing crossings, which requires computing the upper and lower barycenters, defined in equation 9 on page 113.

$$B^U_{ik}=\sum\limits_{j=1}^px(v^{i-1}_j)m^{(i-1)}_{jk} / C^U_{ik},\quad k=1,\dots,\lvert V_i\rvert$$
$$B^L_{ik}=\sum\limits_{l=1}^qx(v^{i+1}_l)m^{(i)}_{kl} / C^L_{ik},\quad k=1,\dots,\lvert V_i\rvert$$

where:
$$
\begin{align}
B^L_{ik} &= \text{upper barycenter of a vertex } v^i_k\\
B^U_{ik} &= \text{lower barycenter of a vertex } v^i_k\\
C^L_{ik} &= \text{lower connectivity of a vertex } v^i_k\\
C^U_{ik} &= \text{upper connectivity of a vertex } v^i_k\\
E_i &= E_i \subset E,\quad e_i =(v, w) \in E_i \text{ if } v\in \sigma_i \lor w\in \sigma_i  \\
i &= \text{is the index of the layer}\\
M^{(i)} &= \text{is the matrix realization of layer $i$}\\
m^{(i)}_{kl} &= \begin{cases}1&\text{if } (v_k,w_l) \in E_i\\0&\text{otherwise}\end{cases}\\
p &=\lvert V_{i-1}\rvert\\
q &=\lvert V_{i+1}\rvert\\
\sigma_i &= \text{an }\textit{order }\text{of $V_i$}\\
v^i_k &= \text{is the } k^{\text{th}} \text{ vertex in the } i^{\text{th}}\text{ level}\\
x(v) &= \text{is the "horizontal position of a vertex $v$}
\end{align}
$$

The definition of matrix realization is found in equation q on page 112.

Question

What is $x(v)$? Yes it is the "horizontal position of a vertex $v$", but what is that? My confusion stems from the statement of the upper-/lower- barycenter for vertex $v^i_k$, which can be calculated for $k = 1,\dots,\lvert V_i \rvert$.

$V_i$ is a set, hence lacking order, which makes me presume - perhaps falsely - that it is in reference to the ordering of $V_i$, which is $\sigma_i$. If the horizontal position of a vertex $v$ was simply its position in its respective layer's ordering, then $x(v^i_k) = k$. Since the BC method hinges upon these calculations, what is $x(v)$?


texts: Find optimal quantum at Round Robin Scheduling algorithm

texts:
In this process list situation

How can I find the quantum time ( time slice ) at 80% of CPU time ?
I found only for 100% of CPU time, so I don't know if it's the same for 80% case

B.T.Q= [mean + median ] / 2
mean=(P1+P2+P3+.....Pn) / n


texts:
This is from a textbook on operating systems. This is not homework, just part of the chapter on deadlocks.

transaction(Account from, Account to, Number amount):
    mutex lock1 = getlock(from)
    mutex lock2 = getlock(to)

    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)

Deadlock is possible if two threads simultaneously invoke thetransaction() function, transposing different accounts. That is, one thread might invoke

transaction(checkingaccount, savingsaccount, 25)

and another might invoke

transaction(savingsaccount, checkingaccount, 50)

What is a good solution to this problem? One I can think of is to use a witness program that will alert the user that a deadlock has occurred, but there must be a better solution implementable by modifying the code. Any ideas?


texts: Soft Question : Is there any website for weak negative results?

texts:
I have noticed that while doing research in computer science you come across many weak but negative results. Now, not every negative result deserves a paper of its own. So I was wondering, is there a website where people can dump their weak results?

If so, how do I look about on this website?

For example, recently we showed that a variation of the Dial-A-Ride problem is NP hard but that is about all that we have. Now, there is no way for us to determine if work has already been done on this variant of the problem since we don't even know what this variant is referred to as in literature.

A resource that collects all weak results could have saved us a lot of time and saved us from re-inventing the wheel.


texts: Filling a 3x3 board with connected tiles

texts:
long story short: I want to list all possible combinations of n tiles on a 3x3 board with the restriction that at least 6 tiles are part of a connected chain. Tiles are connected if the pattern continues from one to the other and a tile can be repeated any number of times (see image below for clarification, I would like to increase the number of available tiles at one point).

You can see some of my thoughts below, I would like to know if there's a more elegant solution to this problem or (if I'm on the right track) some ideas on optimizations and data structures that I would need to actually implement this.

It seems to me there are three separate problems:

I need to map out all connected graphs with 6 vertices
Try all the combinations of tiles that fit on those vertices
List item

Since I actually need to print all the solutions I was thinking that there's no way of avoiding backtracking, so all my ideas so far are basically optimizations of the process. The biggest time save so far is the fact that once you have a valid configuration you can also print out its rotations (see picture below), thus cutting the search time to a quarter, but the catch is i don't know how to deal with duplicate solutions :/

There's also the observation that since I need to have a minimum of six connected tiles, one of them will surely be in a corner (upper left corners seems like the logical place to start) so all the connected graphs would have to start out in that corner.

That's about everything I have right now, thank you for reading and any help is highly appreciated.


texts: bounding the height of stack when checking acceptance pushdown automaton

texts:
Let $A$ be a nondeterministic PDA (with empty stack acceptance). I am looking for a reference for a statement of the following form.

There exists a constant $c$, computable from $A$, such that:
if $w$ is accepted by $A$ then there is an accepting computation of $w$ on $A$ with stack height at most $c|w|$.

From this it would follow that we can decide whether $A$ accepts $w$ without going via equivalent context-free grammars.


texts: Definition of the state of an object in OOP

texts:
I need a concise definition of the "state of an object" in object-oriented programming (for a paper).

For about half of a day I searched for a paper that I can cite on this topic, but I couldn't find one. All the papers I found were mostly general papers on object-oriented programming and they didn't define the state of an object.

I am unsure, but my best guess is something like:
The state of an object is defined by the state of the instance variables of the object.

I am searching for a definition of the state of an object and/or a reference on the topic.

(btw, could I refer to the concept as "object state" or is this uncommon?)


texts:
The author here writes:

  Little known fact, the system of measuring length in the US is Turing complete

My question is: Is the system of measuring length in the US Turing complete?


texts: Which one is the correct way to change functional notation while solving recurrence relation?

texts:
In CLRS 3rd edition P. No 86, the relation

  $T(2^{n}) = 2T(2^{n/2}) + n$

is changed to

  $S(n) = 2S(n/2) + n$

My first question is, why we can change any recurrence relation like this? And,  how will the following relation

  $T(2^{n}) = T(2^{n-1}) + 1$

be changed? Which change is correct?

  $S(n) = S(n/2) + 1$

or

  $S(n) = S(n-1) + 1$


texts:
Let $f:\mathbb{N} \to \mathbb{R}$ be a lower semicomputable function, i.e. there exists a recursive function $g:\mathbb{N}\times \mathbb{N} \to \mathbb{Q}$ s.t.

$$\forall x \in \mathbb{N} \quad \lim_{k \to \infty} g(k,x) = f(x) \qquad\qquad (1)$$
$$\forall x \in \mathbb{N} \quad g(k,x) \le g(k+1,x)\qquad\qquad (2)$$

Question: can we assume that if $f(x)$ is rational then eventually $g(k,x)$ stabilizes on the true value? Formally, can we prove that there exists a recursive function $g':\mathbb{N}\times\mathbb{N}\to\mathbb{Q}$, possibly different from $g$, s.t. $(1)$ and $(2)$ holds for $g'$ and additionally

$$ \forall x \in \mathbb{N} \quad \left( f(x) \in \mathbb{Q} \Rightarrow \exists k_0 \in \mathbb{N}\, \forall k>k_0 ~~g'(k,x) = f(x) \right)$$

I tried many different strategies but they all seem to a dead end.

Notice that $g'$ need not to be build from $g$ (there may be no relations among the two) and we need not to be able to know when $g'$ stabilizes. Think for example to the function $f$ that prints 1 if the $n$-th TM halts otherwise 0 (i.e. the characteristic function of the halting set). If you pick $g'$ as $g'(k,n)=$"$1$ if the TM $n$ halts in $k$ steps and $0$ otherwise" you clearly get that $g'$ eventually stabilizes on all $n \in \mathbb{N}$ even though we will never be able to say when.

Currently I don't even know whether this should be true or false. Maybe I'd bet on true, but it's just a feeling and that can be totally wrong of course.


texts: Is there an undecidable decision problem that computable algorithm for it leads to an algorithm for halting problem?

texts: Suppose, to the contrary, that there exists a computable algorithm for some undecidable decision problem. Would this mean that halting problem would be solved by a computable algorithm? I know that the converse is true for a decision problem in RE complexity class, but not for the other way around.


texts: Is there a mistake in the expression for clean behavior in Pnueli's article from 81'?

texts:
I am reading an article called The temporal semantics of concurrent programs
.

On page $9$, there is a small section (numbered as $2$) called "clean behavior".

I think that there is a problem with this part, what does Pnueli meant by "Let $\lambda_i$ be the leagality condition for the statement departing from $m^i$" ?

I have marked the word "the" in bold since, as I see it, there can be more than one edge departing from $m^i$, an example can be seen on page $11$, at the beginning of part $5$.

Did I missunderstood something , or is there actually a mistake in the article by not addressing the fact that there can be more than one statement that can be exectuded after $m^i$, and that this expression for clean behavior need to be corrected accordingly ?


texts: How do I calculate the average number of comparisons for linear search?

texts:
In a list of 15 entries (city names) if searching for a particular name what is the average number of comparisons using linear search? Worst case it would 15 comparisons and best case it would be 1 comparison. Is the following calculation the average number of comparisons? If not, how do I calculate the average? Thank you.
(15 + 14 +13+ 12 + 11 + 10 + 9 + 8 +7 +6 +5 +4 + 3+ 2+ 1) / 15 = 8


texts: Proving that Turing Machine M runs in time $O(2^{dn})$

texts:
I'm trying to solve this question in order to review for my exam, and this one has got me a bit stumped. From the looks of it, it seems like a fairly straight-forward question, but I can't figure out what steps to begin with.

Let $M$ be a linear-space Turing machine consisting of a single tape. We say $M$ is a linear-space Turing machine if M halts on every input, and if there are constants $c$ and $n_{0}$ such that for all inputs $x\in \Sigma^{\ast}$ of length $n\geq n_{0}$, $M$ running on $x$ visits at most $c\cdot n$ tape squares.
Prove that for some constant $d$, $M$ runs in time $O(2^{dn})$.

I have a couple of ideas to begin with. First, my intuition tells me that I just have to build an algorithm that runs according to those rules and accepts/rejects in time $O(2^{dn})$. Secondly, theres a hint that tells me to "consider the number of configurations", however, I'm not sure on how to incorporate that.
Thank you in advance for any help.


texts: Proving that the conversion from CNF to DNF is NP-Hard

texts:
How can I prove that the conversion from CNF to DNF is NP-Hard?

I'm not asking for an answer, just some suggestions about how to go about proving it.


texts: Sum rule for Big-O with equal complexity-functions?

texts:
One property of the Big-O-notation is the sum rule, which states that when I have two functions $f_1$ and $f_2$ and their corresponding complexity functions are $g_1$ and $g_2$, then the combined complexity is $f_1 + f_2 = O(\max(g_1, g_2))$.
But what do we pick if both complexity-functions are equal? E.g., if $f_1(n)$ is the sorting of an array and $_f2(m)$ as well, then the complexities are $O(n\log(n))$ and $O(m\log(m))$. Applying the rule would be $O(\max(n\log(n), m\log(m)))$. I think that picking any of those would yield a valid but very unintuitive estimation as you would drop one variable. Besides that, it's not clear which one to pick.
Is it the case that you are not supposed to use the rule when there are multiple variables involved?


texts: On "The Average Height of Planted Plane Trees" by Knuth, de Bruijn and Rice (1972)

texts:
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" want to prove that the average height $h_n$ of a tree with $n$ nodes (that is, the maximum number of nodes from the root to a leaf) satisfies $h_n \sim \sqrt{\pi n}$.

The outline is as follows. Let $A_{nh}$ be the number of trees with height less than or equal to $h$ (with the convention $A_{nh} = A_{nn}$ for all $h \geqslant n$) and $B_{nh}$ the number of trees of $n$ nodes with height greater than or equal to $h+1$ (that is, $B_{nh} = A_{nn} - A_{nh}$). Then $h_n = S_n/A_{nn}$, where $S_n$ is the finite sum
$$
S_n = \sum_{h \geqslant 1} h(A_{nh} - A_{n,h-1}) = \sum_{h \geqslant 1} h(B_{n,h-1} - B_{nh}) = \sum_{h \geqslant 0} B_{nh}.
$$
It is well known that $A_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$, for the set of general trees with $n$ nodes is in bijection with the set of binary trees with $n-1$ nodes, counted by the Catalan numbers.

Therefore, the first step is to find $B_{nh}$ and then the main term in the asymptotic expansion of $S_n$.

At this point the authors use analytical combinatorics (three pages) to derive
$$
B_{n+1,h-1} = \sum_{k \geqslant 1} \left[\binom{2n}{n+1-kh} - 2\binom{2n}{n-kh} + \binom{2n}{n-1-kh}\right].
$$

  My own attempt is as follows. I consider the bijection between trees with $n$ nodes
  and monotonic paths on a square grid $(n-1) \times (n-1)$ from $(0,0)$ to $(n-1,n-1)$ which do not cross the diagonal (and are made of two kinds of steps: $\uparrow$ and $\rightarrow$). These paths are sometimes called Dyck paths or excursions. I can express now $B_{nh}$ in terms of lattice paths: it is the number of Dyck paths of length 2(n-1) and height greater than or equal to $h$. (Note: a tree of height $h$ is in bijection with a Dyck path of height $h-1$.)

  Without loss of generality, I assume that they start with $\uparrow$ (hence stay above the diagonal). For each path, I consider the first step crossing the line $y = x + h - 1$, if any. From the point above, all the way back to the origin, I change $\uparrow$ into $\rightarrow$ and vice versa (this is a reflection wrt the line $y=x+h$). It becomes apparent that the paths I want to count ($B_{nh}$) are in bijection with the monotonic paths from $(-h,h)$ to $(n-1,n-1)$ which avoid the boundaries $y=x+2h+1$ and $y=x-1$. (See figure.)

In the classic book Lattice Path Counting and Applications by Mohanty (1979, page 6) the formula
$$
\sum_{k \in \mathbb{Z}} \left[\binom{m+n}{m-k(t+s)} - \binom{m+n}{n+k(t+s)+t}\right],
$$
counts the number of monotonic paths in a lattice from $(0,0)$ to $(m,n)$, which avoid the boundaries $y = x - t$ and $y = x + s$, with $t > 0$ and $s > 0$. (This result was first established by Russian statisticians in the 50s.) Therefore, by considering a new origin at $(-h,h)$, we satisfy the conditions of the formula: $s=1$, $t=2h+1$ and the destination point (the upper right corner) is now $(n+h-1,n-h-1)$. Then
$$
B_{nh} = \sum_{k \in \mathbb{Z}} \left[\binom{2n-2}{n+h-1-k(2h+2)} - \binom{2n-2}{n-h-1+k(2h+2) + 2h+1}\right].
$$
This can be simplified in
$$
B_{n+1,h-1} = \sum_{k \in \mathbb{Z}} \left[\binom{2n}{n+1-(2k+1)h} - \binom{2n}{n-(2k+1)h}\right],
$$
which, in turn, is equivalent to
$$
B_{n+1,h-1} = \sum_{k \geqslant 0} \left[\binom{2n}{n+1-(2k+1)h} - 2\binom{2n}{n-(2k+1)h} + \binom{2n}{n-1-(2k+1)h}\right].
$$
The difference with the expected formula is that I sum over the odd numbers ($2k+1$), instead of all positive integers ($k$).

Any idea where the problem is?


texts:
I molded my problem as the following game (it is a congestion game with varying price):

$N$ players share resources $E$,

$S_i$ is the strategy space of player $i$ which is in $2^E$ (where $2^E$ is the power set of resources).

$P_e^i$ is the price of resource $e \in E$ considering player $i$. The price of resource $e$ is different for different users.

The goal of each player is to select a strategy $S_i$ which minimize its price $\sum_{e\in S_i}P_e^i$ .

My questions are:

Does this game have any Nash Equilibrium (NE)? If so under which conditions?
If it has any NE, what is a sample algorithm for achieving it?

I searched literature but could not find any appropriate information! Any solution is appreciated!


texts: How to understand the recurrence relation and time-complexity of StoogeSort?

texts:
I have the following problem of recurrences and divide-and-conquer. Consider the algorithm, called StoogeSort in honor of the immortals Moe, Curly and Larry. The swap operation $(x,y)$ exchanges the values of $x$ and $y$.

Algorithm StoogeSort:
procedure StoogeSort(A[0...n −1])
    if n = 2 ∧ A[0] > A[1] then
        swap(A[0], A[1])
    else if n > 2 then
        m = ceil(2n/3)
        StoogeSort(A[0...m−1])
        StoogeSort(A[n−m ...n−1])
        StoogeSort(A[0...m−1])
    end
end

The problem demands the following:

Show that the algorithm correctly orders the array A of n elements.
Would it work correctly if we replaced ceil($\frac{2n}{3}$) with floor($\frac{2n}{3}$)? Justify your answer.
Give a recurrence for the number of comparisons between elements of A that StoogeSort performs with n elements.
Solve the recurrence for the number of comparisons. (Hint: skip functions ceil and functions floors, solve exactly the result.)
Show that you execute at most $ {n}\choose{2} $ swap operations. (Hint: How many comparisons are required to locate the element in position k if it is at start?)

I intuit that item two works changing ceil by floor so if the length of the arrangement is odd it does not matter if I take the larger half at the beginning or after the middle of the arrangement. But how do I show this?

I have the following help:
For the first bullet, use induction: It is easy to see it works for 1 or 2 items. Prove that if it works for $n−1$ or fewer items, then it also works for n items. For the 3rd & 4th bullets, $c_1=0$, $c_2=1$ and $c_n=3c_m$. For the final bullet, show that any pair of items is never swapped more than once.

How should I interpret the help for bullets 4 and 5? Thanks in advance.


texts:
How does Dijkstra's Quicksort Algorithm perform better than the original Quicksort Algorithm in terms of memory usage,number of exchanges made and time taken?

original quicksort refers to Tony Hoare's quicksort


texts: The communication complexity of Hamming distance mod $4$

texts:
If Alice and Bob each have a bit string of length $n$, what is the randomized communication complexity (either one or two-way) of computing the Hamming distance mod $4$?  It seems this is hard to search for online but I am sure it must be well known.

The one-way  deterministic communication complexity is clearly linear as Bob can learn Alice's entire string from the messages she sends him.  He does this by flipping each bit in his string in turn and seeing if the Hamming distance mod $4$ goes up or down (also mod $4$).

If we change the question to ask for the Hamming distance mod $2$ then Alice need only send $1$ bit to Bob. That is the Hamming weight of her string mod $2$.


texts: How much of the x86 instruction set does blender use?

texts: I'm trying to better understand benchmarks that are commonly used for computer hardware.  I've been unable to find an answer to this question.  Extra credit if you can provide a breakdown in percentage per instruction of a blender benchmark.


texts: Expectation for the number of comparisons in a randomized Quicksort

texts:
I found this link: http://theory.stanford.edu/~tim/w11/l/qsort.pdf and it kind of theoretically describes how to approach finding  expectation for the number of comparisons in a Quicksort.

Using this, how would I find and prove the expectation for an array of a concrete number of items, for example 5? (see the formula in the second section of the link)
Would my expectation be !https://i.imgur.com/7BIE3qj.png)! but replace the n by 5 for example (to get the expected number of comparisons for a 5 length array)

the second formula reads:
!(https://i.imgur.com/66gvyjp.png)!

I understand I should just replcae the n with for example 5 if I want to find the number of comparisons expected for a concrete array, however I don't think I  quite understand how the proof would apply in this case, however. I was wondering if anyone knew an easier proof for finding the expected number of comparisons in a randomized quicksort for an array of length n.


texts: Why is Machine Learning taught in Computer Science Courses but not in Mathematics?

texts: I always wonder why machine learning is native to computer science rather than its more close fields like statistics and mathematics? In machine learning we CS engineers learn stats and maths and implement it by coding. Wouldn't it be much more easier for say a mathematician and a statistician to learn coding and implementing this stuff? Be it Regression, Deep Learning, SVM, all of the things boils down to maths and stats, so why teach computer science students Machine Learning, and why not teach it to mathematicians and statisticians?


texts: User-level threads and information available to the kernel

texts:
User-level threads are transparent to the kernel. How is htop able to show user-level threads running on my system? I know that those threads are user-level threads because when I press H (for toggling display of user level threads), those threads disappear from the list.

The image below shows three user-level threads for Emacs (which is a single threaded application from the kernel's perspective)


texts:
Can someone please explain why this is correct:
function productSum(array,depth=1) {
    let sum=0;
    for(let i=0;i<array.length;i++){
        if(Array.isArray(array[i])){
            sum+= productSum(array[i],depth+1)
        }else{
            sum+= array[i];
        }
    }
    return (depth)*sum;
}

But, following is wrong:
function productSum(array,depth=1) {
    let sum=0;
    for(let i=0;i<array.length;i++){
        if(Array.isArray(array[i])){
            sum+=(depth)* productSum(array[i],depth+1)
        }else{
            sum+= array[i];
        }
    }
    return sum;
}

I haven't been able wrap my head around it. Why is does it give wrong answer if I multiply the sum with depth before the for loop on an array ends?
It is clear from the sample output that if there are multiple array items at a depth, we are supposed to multiply the sum with the depth as many times.
Eg. depth 2 is multiplied by the sum twice in the example.
Could someone please break it down for me?


texts:
We define a language $L$:

$\qquad L=\{\langle M,w,k \rangle \mid M(w) \text{ reaches configuration } \alpha q \beta \text{ with } |\alpha \beta| \geq k \}$

with $M$ Turing machines with state set $Q$ and tape alphabet $\Gamma$, $\alpha$ and $\beta \in \Gamma^*$ , and $q \in {Q}$.

A configuration like this : 10q11 or  Bq11  are in standardform ,however those configurations  BB10q11 or B10q11BB are not ,  in other words if $\alpha $ starts with many blanks  then all the blanls will be one blank , same thing with $\beta$ when it ends with many blanks .

A configuration can be  like this  :

I am not sure if the language is decidable , but if i am able to find a machine which  decides L then it  must be decidable
may main thoughts  about the contruction of the machine like below:

Let D the machine that decided L

1-after each step check if the configuration $\alpha q\beta$, with $\mid \alpha\beta \mid \geq k$, if yes then accept  else go further.

2-if until the i-step no configuration is found that  satisfied the condition and D  visted the  same  configuration twice ,which means it will go in a loop and then the condition won t be statisfied, then  we will reject
The problem here  which  i am not really sure about ,for how long do we need to wait until the loop is discovered ?


texts: Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

texts:
We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work.

Guess $T(n) \leq cn-d$. Assume true for $m < n$. Specifically, $m = n/3 < n$
Then, $T(n) \leq cn-d$.

$T(n) \leq 2(cn/3 - d + 1) + n$ $= 2cn/3 - 2d + 2 + n$  $=n(2c/3+1)+2(1-d)$. Then for values of $c \geq 1$ and $d \geq2$  we have $T(n) \leq cn - d$. Then $T(n)=\Theta(n)$.

What does everyone think?


texts: Is the number of shortest paths between every two vertices at most 4*n^3?

texts:
In every weighted graph with $n$-vertices

with negative weights,
with $n > 10$,
a weight can't appear $n$-times in graph,

there are between every two vertices at most $4n^3$ shortest paths.

I'm trying to prove whether the statement above is true or false, however I am clueless. So far I failed to find a graph where there would be more than $4n^3$ shortest paths so I'm guessing it's true?


texts: How to calculate Big O of $T(n) = aT(n^b) + f(n)$?

texts:
I'm a student studying Big O. I know that we can solve $T(n) = aT(\frac{n}{b}) + f(n)$ by compering $n^{\log_b{a}}$ to $f(n)$ or

  $O(n^{\log_b{a}} + f(n))$

Today I was faced with $T(n) = T(\sqrt n) + 1$ and I think it is $O(\log\log n)$. and I was faced with this too, $T(n) = T(\sqrt n) + O(\log\log n)$ that I think it is $O(\log^2\log n)$.

I'm wondering what is the formula (or method) to solve any kind of this type of problems (my guess is $O(f(n)a^n\log\log n)$). so:

  How to calculate Big O of $T(n) = aT(n^b) + f(n)$ with $0<b<1$?

Thanks in advance.


texts: Prove that the language { uw : |u| =2 |w| } is regular

texts:
I have a problem with this following question:

  Prove that the language $\{uw : |u|=2|w|\}$ is regular.

I tried to give this regular expression $(uw²)^*$ to resolve it.


texts: Is the union Non Recursively enumerable?

texts:
Define languages $L_0$ and $L_1$ as follows :

$L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\} $

$L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts on }w\}$

Here $\langle M, w, i \rangle$ is a triplet, whose first component $M$ is an encoding of a Turing
Machine, second component $ w$ is a string, and third component $i$  is a bit.

Let $L = L_0 ∪ L_1$. Which of the following is true?

$L$ is recursively enumerable, but $L'$ is not
$L'$ is recursively enumerable, but $ L$ is not
Both $L$ and $L'$ are recursive
Neither $L$ nor $L'$ is recursively enumerable

I know that
$L_0$ is recursively enumerable and $L_1$ is non recursively enumerable but their union is what I'm confused with .

I'm not sure though, but I am unable to design TM for $L$ which makes me think that it is not recursively enumerable ?


texts: Chernoff bound when we only have a lower bound of expecation

texts:
This question: Chernoff bound when we only have upper bound of expectation  is similar, but for an upper bound of expectation.

The standard Chernoff bound says that is $X$ is a sum of 0/1 random variables, then, for any $\delta \in (0,1)$,

$P(X \leq (1-\delta) E(X)) \leq e^{-\frac{\delta^2 E(X)}{2}}$.

Suppose we only have $\alpha \leq E(X)$. Is it true, and if so, how to prove, that

for any $\delta \in (0,1)$,

$P(X \leq (1- \delta) \alpha) \leq e^{-\frac{\delta^2 \alpha}{2}}$.


texts:
I have learnt to solve topological ordering using $in-degree$ method where we have to take the vertices having in-degree $0$ at an instance and arrange them in that order.

  For example consider this question asked in Graduate Aptitude Test in
  Engineering more commonly known as $GATE$ the entrance exam for $IIT$
  $M.Tech$ in India. The question goes like this,

  Find the number of topological ordering possible for the given
  graph-->

Here we can see that in-degree of A is 0 so we take $A$ as the stating vertex, then we have 2 options either $B$ or $C$, and so on....
The number of possible topological ordering in this case is $6$ as explained below

This method works well for these examples where the number of in-degree 0 vertices is less at a time, but how to solve problems where there are many number of 0 in-degree vertices as the one given below

I think combinatorics will come into picture in such cases, but I am unable to apply it properly. Any help will be highly appreciated.


texts: Is the language of all TMs *not* accepting a given string, Enumerable?

texts:
Is the following language in RE?
$$L = \{\langle M\rangle : M\text{ is a TM that does not accept }010\}$$

I could use Rice's Theorem with the property $P = \{L : 010\text{ is not in }L\}$ to show it isn't in R, but how do I show it is in RE?


texts: Why scholarly papers focus on DAGs instead of DCGs (Directed Cyclic Graphs)

texts:
In trying to understand how to convert DCG's (Directed Cyclic Graphs) to DAG's (Directed Acyclic Graphs) without removing all the edges, I came across this paper which says:

  Since the problem involves DCG, therefore a new algorithm to reduce the DCG into the form of a DAG should be proposed. It is simpler when no cycle exists in a graph. A DCGSimplify algorithm is presented to reduce the graph from DCG to DAG.

Update

I am wondering what advantages you gain by removing cycles from your data structure. For example, maybe it allows you to traverse it easier during graph matching, or it makes it so you can generate a graph covering of some sort that's not possible with cyclic graphs. Basically I have noticed many papers talk about DAG's, even in relation to CFGs (Control-Flow Graphs) and data-flow graphs, which in practice always have cycles. They restrict it to DAGs for some reason, and don't address Directed Cyclic Graphs, which CFGs and such are most of the time. Wondering why this is, what advantage does DAGs have from a mathematical perspective or computer science perspective.


texts: How to generate a DFA that recognizes a non-regular Grammar

texts:
How would you convert the following grammar to a DFA that recognizes its language?
\begin{align}
&G = (\{S,A,B\},\{0,1\}, S, P)\\
&P\colon
&&S\rightarrow A1B\\
&&&A \rightarrow0A|\epsilon \\
&&&B \rightarrow0B|1B|\epsilon
\end{align}

And this is the DFA that recognizes $L(G)$:

But I don't really know how to generate that DFA; to me, it makes sense that both $A$ and $B$ were accepting states, and I (wrongfully) generated mine like this:

My NFA

And its DFA conversion

How is the correct one generated?
Why isn't $A$ an accepting state?
What happens to $S$ as a state?


texts: Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?

texts:
I am supposed to find an algorithm solving the following problem:

Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$.

I don't know anything about the form of the grammar and I can't convert it into Chomsky's form as it would introduce new nonterminals and possibly remove $v$. Where do I start with this? Any suggestions?

Thanks


texts: Is the language of DFAs which do not accept themselves recognizable?

texts: I understand how a the language of turing machines which do not accept themselves is not recognizable but I'm not sure if the same proof could be used to describe a DFA... i.e a proof by contradiction in which a recognizer M recognizes a TM which does not accept itself on input ...creates a contradiction in which if M accepts then M does not accept itself.


texts:
In the 3-Path Packing problem, we are given an undirected graph $G$ and a parameter
$k \in \mathbb{N} \cup \{0\}$. We need to answer Yes/No if there exists a collection of $k$ vertex disjoint paths on three vertices in $G$.
I am interested in an easier variant of this problem where we are given an additional group $M \subseteq V$ that the middle vertex in each path is from $M$ and the adjacent nodes are not. So for any legal 3-path $u\rightarrow v \rightarrow x$, we should have $u,x \in V \setminus M$ and $v \in M$.
I am trying to find a polynomial algorithm for this problem by using maximum matching.
My solution is based on defining a vertex for any possible 3-path in the graph.
Since we are restricting ourselves to choose a middle vertex only from $M \subseteq V$ this can be done in polynomial time and space.
I am now trying to define the edges and extra nodes in a manner that will guarantee that nodes with common vertices cannot be picked together. But every time I am blocking or allowing legal/illegal choices.
This problem can also be represented as determining if there exist $k$ disjoint sets among a given group of size 3.
Any suggestions?


texts: What if block sizes are not equal among caches?

texts:
In all the books, packets of slides and similar I read, cache miss is always explained by assuming that blocks of different caches (or cache and RAM) are always of the same size. It's pretty clear how it's works in this case but the question is: what if block dimensions are not equal among caches?

For example, assuming a L1 cache of 8KB and 16B blocks (that implies 2^9 blocks) and a L2 cache of 512KB with 32B block (that implies 2^14 blocks). Assuming that a load have to be executed, i.e. LD R1,(0x0000AFAF) and suppose that there is a cache L1 miss and a cache L2 hit, what happens? What I mean is that i know that a block containing that addressed byte would be stored in L1 cache and i know where. The problem is what i have to save. I mean, have i to save half block of L2 cache (from 0x0000AFA0 to 0x0000AFAF) in a block of L1 cache or have i to save a block of L2 cache (from 0x0000AFA0 to 0x0000AFBf) in two block of L1 cache? Would be the same if i had cache + RAM instead?


texts: What is the running time of generating all $k$ combinations of $n$ items $\binom{n}{k}$?

texts:
I was solving the following problem, just for reference (441 - Lotto). It basically requires the generation all $k$-combinations of $n$ items

void backtrack(std::vector<int>& a,
               int index,
               std::vector<bool>& sel,
               int selections) {
    if (selections == 6) { // k is always 6 for 441 - lotto
        //print combination
        return;
    }
    if (index >= a.size()) { return; } // no more elements to choose from
    // two choices
    // (1) select a[index]
    sel[index] = true;
    backtrack(a, index+1, sel, selections+1);

    // (2) don't select a[index]
    sel[index] = false;
    backtrack(a, index+1, sel, selections);

}

I wanted to analyze my own code. I know at the top level (level = 0), I'm making one call. At the next level (level=1) of recursion, I have two calls to backtrack. At the following level, I have $2^2$ calls. The last level would have $2^n$ subproblems. For each call, we make $O(1)$ work of selecting or not selecting the element. So the total time would be $1+2+2^2+2^3+...+2^n = 2^{n+1} - 1 = O(2^{n})$

I was thinking since we're generating $\binom{n}{k}$ combinations that there might be a better algorithm with a better running time since $\binom{n}{k}=O(n^2)$ or maybe my algorithm is wasteful and there is a better way? or my analysis in fact is not correct? Which one is it?


texts: How to prove that a bounded pushdown automaton is regular?

texts:
I'm studying computer science and I want to show that a language which is accepted by a pushdown automaton with a bounded stack height is regular, but I'm totally lost... Can someone try to explain how we can prove it ?

Thank you in advance!


texts: Term for language that abstracts program location?

texts:
What is the technical term that describes a programming language that abstracts (or at least largely abstracts) the machine location of programs? I’m thinking here specifically of the evolution of handheld calculator programming languages, from early (and some late) models where each instruction exists in a single linear space (e.g., HP RPN calculators before the 41 series), to (some) later models such as the 41 series and the 42S, where each program exists in its own space.

Is there a formal term for this difference?

(Note that I’m thinking here exclusively of cases like the examples given, where the languages used are otherwise the same — here RPN keystep programming — and not of more radical changes in language and system architecture — e.g., RPL.)


texts: Proof that class of languages accepted by DPDA by empty stack is not closed under union

texts:
My first intuition was to take two languages $L_1$ and $L_2$ (symbol $d$ at the end is to fulfill prefix property):
$$L_1 = \{ a^i b^i c^j d : i,j \ge 0 \} \mathrm{\ \ and\ \ } L_2 = \{ a^i b^j c^j d : i,j \ge 0 \}$$
So their union would be:
$ L = L_1 \cup L_2 = \{ a^i b^i c^k d : i=j \lor j=k \} $
Then to prove $L$ not even being DCFL (e.g. in similar way as Example 10.1 from "Introduction to Automata Theory, Languages, and Computation" by Hopcroft & Ullman).
Big inconvenience would be the need to include in the proof also the proofs of all other properties (assuming this class is - just as "regular" DCFL - closed under complement etc.)

But I was told that precisely because the question is about DCFL being accepted by empty stack, the proof is actually trivial and could be expressed in just few sentences.


texts:
I'm only a layman therefore only discuss stuff naïvely.

I read some introductory articles about halting problems with a scenario that if there were such a decider accessible to us, we should be able to solve some unsolved mathematical problems. We could write some brute-force programs to check Goldbach conjecture, say, and then throw it into the decider to see what happens. Then he refers to halting problem to say that such kind of dream is not possible.

However I notice that there's difference between halting problem and his scenario. Such a brute-force checking program has nothing to do with input data, but for halting problem, we assume the decider to check for every input. So I wonder whether halting problem without input is also undecidable?

I googled and found this. Personally I think it's wrong and couldn't be corrected because of self-reference.

Thanks for your help!