Proving/Disproving that language L is non-regular/CFL Here are three examples of questions I run into. I'm not looking for solutions.

  If $L$ is CFL then $L' = \{ ww^R | w \in L \}$ is non-regular.
  If $L$ is non-regular then $L' = \{ ww^R | w \in L \}$ is non-regular too.
  If $L_2, L_3, L_4$ are regular languages and $L_1 \cup L_2 = L_3$ and $L_1 \cap L_2 = L_4$, then $L_1$ is regular.

The problem I'm facing here is that I'm having hard time to figure out what how to prove such claims.

Lets say I'd like to prove claim 1, I can't seem to understand what exactly should I prove?
If I assume that $L'$ is regular, then what way can I follow that will lead me to contradiction? I would go for the intersection with CFL language, but this won't help me as CFL is closed under intersection with regular languages. So I'm pretty lost here.

Take claim 3 for example, after spending a lot of time trying to find a counter-example, I have strong feeling that this claim is true. (please don't tell me if I'm wrong, this post is not about the answers). Yet I couldn't find out what exactly should I prove? Of course that $L_1$ is regular but in what way may I do that?

I hope you get my situation. What I'm asking from you is to describe how would your proof be written in the above claims? What would you try to archive in your proof?

Thanks a lot for your time.

In fact it turns out that there is no simple method to prove things like this. Except when you want to disprove a statement, then a well-chosen counter example suffices. But also here there are no guidelines how to find them. Experience and trial and error, I would say. In your three questions I see three different approaches.

For (1) go look for a counter-example. Since the statement is true for most languages, you have to look for trivial special cases, but still contradicting the general claim.

For (2) you can try contra-positive. Instead of $A \Rightarrow B$ consider the equivalent $\lnot B \Rightarrow \lnot A$. This is then a (somewhat exotic) closure property. Can you recover $L$ from $L'$?

And I am afraid that (3) looks like simple Boolean set algebra. It is in fact the most straightforward of the three questions.

For 1, it is clear that L' is a palindrome, actually. So, it is really easy to prove that a set of palindromes is non-regular through pumping lemma.
Here is one good solution

2nd statement also appears to be pretty much similar.

And for the 3rd statement, you should look into the closure properties of regular languages, especially, "closure under union".


Reduce Vertex Cover with size k to Vertex Cover with size n/2 Disclaimer: This is a homework question.

I would like to reduce vertex cover problem to the following problem:

$$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$

I have divided the problem into three parts:

$k = n/2$: This case is trivial.
$k > n/2$: Yes in vertex cover problem does not necessarily mean yes in $L$.
$k < n/2$: No in vertex cover problem does not necessarily mean no in $L$.

I know that I need to change graph $G$ into $G'$ somehow to map results of VC to $L$.

Any advice on how to do so is appreciated.

For $k<n/2$, add an isolated complete graph with $n-2k+2$ vertices (note it takes at least $m=n-2k+1$ vertices to cover this complete graph). Now there is a vertex cover of size $(n+(n-2k+2))/2=n-k+1$ in the new graph iff there is a vertex cover of size $(n-k+1)-m=k$ in the old graph.

For $k>n/2$, add $2k-n$ isolated vertices. Now there is a vertex cover of size $(n+(2k-n))/2=k$ in the new graph iff there is a vertex cover of size $k$ in the old graph.

This question was answered in the following video (By me):
https://www.youtube.com/watch?v=rKNasOecTu0

In a nut-shell, the key here is to modify the graph in such a way it wouldn't be profitable to select vertices from the modified graph, and by finding a full vertex cover in the original graph, you could get a half vertex cover in the modified graph.

Hope that helps :-)


Write a routine to print the numbers 1 to 6 and back to 1 again without using any loops Can anyone help with this question? I currently have this solution that prints

  1 2 3 4 5 6

but I'm having trouble going back down to 1.

public class noLoop{

     public static void main(String []args){
        noLoop(6);
     }

     public static void noLoop(int n) {

         if (n == 0) {
             return;
         }

         else {
             noLoop(n-1);
             System.out.println(n);
         }
     }
}

public class Foo {
    public static void main(String[] java_is_silly) {
        System.out.print("1 2 3 4 5 6 5 4 3 2 1");
    }
}

This is clearly a Computer Science problem to demonstrate functional programming and recursion.  It needs action on the head and tail of recursion and a middle exit.

Those who only program without applying Computer Science would not approach it that way and would get poor marks from me!

// Recursion demonstration in Java
class NoLoop
{
    public static void main(String [] args)
    {
        doit(1);
        System.out.println();
    }

    static void doit(int i)
    {
      System.out.print(i + " ");
      if (i >= 6) return;
      doit(i+1);
      System.out.print(i + " ");
    }
}


What is a monotone dataset and monotone classification? Classification algorithms, such as k-Nearest Neighbors, are well known in machine learning area, but I faced this new expression Monotone classification and I wonder what does it stand for.

I guess that it has something to do with some peculiar characteristic of the dataset, e.g. if all the objects have growing attributes and, plotted in a 2D plane, they look as if they were gathered around the line of the function f(x) = x or something like this, but as english is not my native language, I couldn't understand the raw meaning of Monotone and Monotone classifiers, the things I read were so confusing that I don't think it is worth it to mention.

I read this:

  The evaluation of teaching courses based on surveys gathered from
  students’ opinions can be categorized as a monotonic classification
  problem if it intends to predict a final qualification that summarizes
  the general quality of the course. The students are asked to evaluate
  each course according to several aspects related to interest,
  achieving appropriate class participation, teaching resources,
  capabilities of the teacher, etc.

I would like to be able to say why these surveys behave as a monotone dataset, but no explanation fits what I have in mind about the monotone definition.

A monotone classifier is a classifier that is a monotonic function.

One reasonable definition of monotone data set is that it is a data set that is consistent with some monotone model (i.e., where there exists a monotone classifier that gets 100% accuracy).  I don't know if this is a standard definition so hopefully any text that uses that phrase would provide a definition.

Why use a monotone classifier in the setting you mention? Perhaps we have some a priori reason for believing that, all else being equal, the higher the students rate their satisfaction, the higher the quality of the course.  That amounts to a monotonicity assumption about the underlying model that relates quality to satisfaction.  If we assume that the data was generated from a monotone model, it is reasonable to try to learn a monotone classifier.  Whether this is appropriate in any particular setting depends on whether you have a reason to think that the data does come from a monotone process/model or not.

I don't find any difference between the conventional classifiers we use with the definition of a monotone classifier


What exactly is an algorithm? I know that this may sound a bit out of the box, in fact i used to always think inside the box, but recently i've been thinking, possibly because computer science provides an high degree of freedom, about ways to devise programs other than the ones taught in university.

Consider the factorial function. Typically we define this function like

 int fact(int n)
 {
 int r = 1;
 for(int i=2;i<=n;i++)
 r = r*i;
 return r;
 }

I'd call this an algorithm and have no doubt that this is the right way to do it. Then, i wondered "can i do this in constant time?", which let to the following idea: what if i had an array of integers where array[n] houses the factorial of n? Once this array is filled i could simply define fact as:

 int fact(int n)
 {
 return array[n];
 }

Still i cant seem to cal this an algorithm, even though it provides the correct result and operates in constant time O(1). Can this be called an algorithm? Otherwise, why not? I could argue that filling the array would require an algorithm to have operated at some time, even if it was in our brain in order for us to fill the array, but could this be the criteria? How are these aspects handled formally?

Note that this concept could be extended to any function operating over integers independly of its number of arguments, i would just have to use a matrix if the function had 2 arguments, or 3 if the function had 3 arguments, and so forth. Also, aren't these solutions used simply because of memory consumption?

Also, not that functions may also encompass any program with output, since i could find a way to index every single possible output that a program could provide.

As another exemple, consider the common use of an array: i allocate an array initially of size N, then i add elements to array by storing the value at index n and increasing n by one unit. Then, if i want to look for an elemento, i cant help but to perform a linear search over the array. If instead i created an array of size, for instance, Integer.MAXVALUE, to store integers, initialized with zeroes, i could store an integer by placing 1 at its index. Then i could search for its existence in the array in O(1) time. What if i wanted to be able to place multiple units of the same number? No problema, i'd just increase the value stored at the integer's index.

Sorting would be a bit more complicated, but nonetheless lookup and addition could be performed in O(1) time.

The informal definition of an algorithm in a popular textbook goes something like:

An algorithm is (1) a well defined computational procedure (2) that takes some input and (3) produces some output (4) for a well defined computational problem.

In your first case you have coded an algorithm where:
The problem is to find the factorial (part 4 of definition),
given int n as input (part 2 of definition),
the code describes the computation to be performed (part 1 of definition),
the output is the factorial (part 3 of definition).

In your second case:
The problem is to find the array element at position n (part 4 of definition),
given n as input (part 3 of definition),
the code describes the computation to be performed (part 2 of definition),
the output is the element at position n (part 1 of definition).

You have stored factorials there so it gives you factorials. If you had stored squares or cubes there you'd get squares or cubes, so it cannot be said that the second snippet by itself is an algorithm to compute factorials.

And if you say that an array look up along with an array having f(n) at position n is an algorithm to compute f(n) then you have gone so deep that there is no more computation below. A well defined computational procedure should be a finite piece of information. If an infinite array of factorials is a part of the computational procedure this does not hold. So that wouldn't be an algorithm to compute factorials.

Your question and description do not relate that much.
Algorithm is theoretical and doesnt relate to any programming language.
Algorithm is a set of rules or steps (procedure) to solve a problem.
Your problem can be solved in many ways or many algorithms.

Your second solutions means to compute first a big array of factorials which initially will take a lot of time then store it. It will consume more storage but eventually it will be faster while the first one doesnt consume storage but consumes computing power so you will have to chose depending on your environment.


Finding longest balanced parentheses using $n$ smaller strings Given $n$ strings consisting only of '$($' and '$)$', how one can compute the length of the longest string that can be built by concatenating a subset of these strings in some order such that the resulting string is a balanced parenthesis?

Example: If we have the strings $\{"(()",")(",")","(("\}$, one can build the string $"(())()"$ which has length 6.  We cannot construct a longer one from the previous set, thus the answer is 6.

In general, the answer is always even, and always $\geq 0$ because we can always take the empty set.

Problem source: North American Invitational Programming Contest (NAPIC) 2017, Problem A.

First, let's remark that the order in which you put the selected strings is not significant as long as it is valid.  That means that you can put the strings in a canonical order and you know that the solution is a subsequence of that sequence.  The canonical order I suggest is first the strings which increase the number of opened parenthesis (with D.W. triplet notation, the triplets $\langle i,j,\ell \rangle$ for which $j>i$) tied resolved by increasing $i$, then those which don't change the number of opened parenthesis ($i=j$) then those which decrease the number of opened parenthesis($i>j$) this time solving the tie by decreasing $i$.

Then you apply the favorite technique of programming contests: dynamic programming. You are filling an array of $n$ columns.  An entry $c,r$ of $\ell$ states that with the $c$ first strings in our canonical order, you can have $r$ opened parenthesis pending with a total length of $\ell$.  This is filled using the content of the column $c-1$ with the initial column stating that with no strings you have a $0$ opened parenthesis pending and a length of $0$.  You have to pay attention to avoid entries which would need to have more opened parenthesis than available, and when an entry is reachable with two lengths to keep the longest one.

You avoid the  exponential behavior because you know that the strings have a bounded length of 300 (thus you can't have more than $300\; c$ opened parenthesis after $c$ columns instead of the $2^c$ entries which would have been possible without that bound)  and thus you are sure that after the ninth or so column, you'll have duplicate entries.

Your problem is $\text{NP}$-hard. It is an optimization version of the following decision problem.
\begin{array}{|l|}
\hline
\textbf{Decision problem }\mathcal{P}\textbf{:}\\
\text{Given }n\text{ strings consisting only of `(' and `)', does there exist a subset of strings}\\
\text{which when concatenated in some order yield a string with balanced parenthesis?}\\
\hline
\end{array}

I will now prove that Problem $\mathcal{P}$ is $\text{NP}$-hard.

We reduce subset sum problem which is known to be $\text{NP}$-complete to Problem $\mathcal{P}$.

Subset Sum Problem [NP-Complete]: Let $S=\{a_1, \cdots, a_k\}$ be the finite set of (including negative) integers. We need to decide whether there exists a subset $R \subseteq S$ such that sum of elements in $R$ is zero.

Reduction to Problem $\mathcal{P}$:
We encode all $a_i \in S$ to strings of parenthesis in the following manner.

If $a_i = +m$, then its string encoding is $\text{Encode}(a_i) = `` \underbrace{((\cdots(}_{m \text{ times}} "$
If $a_i = -m$, then its string encoding is $\text{Encode}(a_i) =`` \underbrace{))\cdots)}_{m \text{ times}} "$

Now we encode sum operation. Let $S' = \{a_1, a_2, \cdots a_q \} \subseteq S$ be any non-empty set such that $a_1 \geq a_2 \geq \cdots \geq a_q$.
Then sum over $S'$, $\Sigma \ S' = \text{Encode}(a_1) \circ \text{Encode}(a_2) \circ \dots \circ \text{Encode}(a_q)$, where $\circ$ is a string concatenation operation.
With this encoding, following invariant property holds: Sum of a value $(i-j)$ is encoded as a string of the form $`` (^i \ )^j "$.
Thus, the sum is zero iff parenthesis are balanced.

You can convince yourself that this reduction is polynomial one. This proves NP-hardness of your optimization problem. One way you can solve your problem is by encoding it in SAT or Integer Linear Programs. Then you can use state of art solvers like Z3, LP_SOLVE or GLPK to get a solution.


Worst case running time to search for an element in a balanced BST with $n2^n$ elements What is the worst case running time to search for an element in a balanced binary search tree with $n 2^n$ elements?

The answer is $\Theta(n)$.

My answer:

To search an element in BST is $\log (n)$ so
$$
\begin{align*}
\log(n 2^n ) &=  \log(n) + \log(2^n) \\
            &=  \log(n) + n\log 2 & \text{(base is 2)} \\
            &=  \log(n) + n
\end{align*}
$$

  Why have they used $\Theta$ in the answer?
  And why only $n$?

You state that searching an element in a BST takes time $\log n$, but this is wrong on two counts. First, this is (roughly) the worst-case number of comparisons. Second, the running time itself isn't exactly $n$ but is roughly $C\log n$ for some constant $C$ that depends on the exact machine model (assuming that comparisons take constant time). For this reason, it is better to use $\Theta$ notation (look it up!) and state that the worst-case running time of element lookup in a BST is $\Theta(\log n)$, where $n$ is the number of elements in the BST.

In our case, the number of elements is $n2^n$, and so the running time is $\Theta(\log(n2^n)) = \Theta(\log n + n) = \Theta(n)$. Asymptotically, $n + \log n = \Theta(n)$, and so there is no need to explicitly mention $\log n$.

In question, they are asking only the worst case time,so, they comparing  log n(log base 2) time with n time. So, the worst case time is n becasue n is larger than the log n time..


Maximum length path between any two nodes in a tree with possible negative edge weights Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a graph with edge weights 1 but that won't work here.

All I can think of is going for a $O(N^2)$ approach with LCA but thats a glaringly bad approach for huge trees ($N \sim 100000$)

You can find this path in linear time:

If the tree is unrooted, pick an arbitrary node as root.
Traverse the tree in postorder and for each node:

2.1. Find the longest and second longest path ending in the current node by maximizing over all children and extending the longest path ending in the child by the edge between parent and child.
If there are no two children that result in paths of positive length, set the second longest (and if necessary also the longest) path as starting and ending here (length 0).

2.2. Find the longest path in the subtree that starts at the current node by maximizing over the longest paths in all subtrees below the current one and the path resulting from joining the two paths found in the previous step.

Now the longest path in the subtree started at the root is the one you are looking for.

Note that the longest path between any two nodes in a tree is also the shortest path (indeed a tree only has one path between any pair of nodes)

Now, you cannot do this in sub-quadratic time since in order to obtain the distances between all pairs of nodes you need to compute $O(n^2)$ of data.


Is zero allowed as an edge's weight, in a weighted graph? I am trying to write a script that generates random graphs and I need to know if an edge in a weighted graph can have the 0 value.

actually it makes sense that 0 could be used as an edge's weight, but I've been working with graphs in last few days and I have never seen an example of it.

Allowed by whom? There is no Central Graph Administration that decides what you can and cannot do. You can define objects in any way that's convenient for you, as long as you're clear about what the definition is. If zero-weighted edges are useful to you, then use them; just make sure your readers know that's what you're doing.

The reason you don't usually see zero-weight edges is that, in most contexts, an edge with weight zero is exactly equivalent to the absence of an edge. For example, if your graph represents countries and the amount of trade done between them, a zero-weight edge would mean no trade, which is the same as having no edge at all. If your graph represents distances, a zero-weight edge would correspond to two places at distance zero from each other, which would mean they'd actually be the same place, so should both be represented by the same vertex. However, in other contexts, zero-weight edges could make sense. For example, if your graph represents a road network and edge weights represent the amount of traffic, there's a big difference between a road that nobody uses (zero-weight edge) and no road at all (no edge).

Think of a graph of the road system in Cambridge UK, the notes are shared between cyclists and car drivers, so are most of the edges.    Doing so greatly decreases the cost of maintaining the data.

Now if we define the edge weight as being travel time in seconds, cleanly each edge will have two weights, one for cars anther for bikes.   Some weights will be infinite as cars are not allowed on cycle ways.

Now consider two road junctions that very close to each other so close they are only serrated by a few posts that stop car drivers.   (For example a cross road, where car drives can only turn left, but cyclists can go in any direction.)   We then get some edges with infinite weight from car drivers and 0 weight for cyclists.

(Clearly the graph could then be pre-processed to create a simpler graph for the routing of cyclists, before working out the best routs.)


What is the difference between a 'page' of memory and a 'frame' of memory? WP has an adequate discussion of paging, which I think I understand.. However I am confused by the articles repeated use of the term Page Frame.

I thought frames and pages were different things.  Could someone please clarify the difference.

Short version: "page" means "virtual page" (i.e. a chunk of virtual address space) and "page frame" means "physical page" (i.e. a chunk of physical memory).

That's it, pretty much. It's important to keep the two concepts distinct because at any given time, a page may not be backed by a page frame (it could be a zero-fill page which hasn't been accessed, or paged out to secondary memory), and a page frame may back multiple pages (sometimes in different address spaces, e.g. shared memory or memory-mapped files).

A page frame is a storage unit within the main memory, while a page is the contents in the frame.


Designing a DFA and the reverse of it There is a theorem that says if a language is regular, its reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?

$L^R$ is the reverse of the language $L$ and for designing $L^R$ you must:

Reverse all edges in the transition diagram.
The accepting state for the LR automaton is the start state for the main automaton.
Create a new start state for the new automaton with epsilon transitions to reach of the accept states for the main automaton.
Convert this NFA back into a DFA.

To write the reverse of a DFA, Change all the initial states to final and the final ones to initials(for the later, if there are multiple final states, use a new state and use null transitions to each of them). At last... Reverse the edges.


Why Do Computers Use the Binary Number System (0,1)? Why Do Computers Use the Binary Number System (0,1)? Why don't they use Ternary Number System (0,1,2) or any other number system instead?

Since we're in Computer Science, I'll answer this way: they don't.

What do we mean by a "computer?" There are many definitions, but in computer science as a science, the most common is the Turing machine.

A turing machine is defined by several aspects: a state-set, a transition table, a halting set, and important for our discussion, an alphabet. This alphabet refers to the symbols which the machine can read as input, and that it can write to its tape. (You could have different input and tape alphabets, but let's not worry about that for now.)

So, I can make a Turing machine with input alphabet $\{0,1\}$, or $\{a,b\}$, or $\{0,1,2\}$,
or $\{\uparrow,\downarrow\}$. It doesn't matter. The fact is, I can use any alphabet I choose to encode data.

So, I can say that $0001001$ is 9, or I can say that $\uparrow \uparrow \uparrow \downarrow \uparrow \uparrow \downarrow$ is 9. It doesn't matter, since they're just symbols we can distinguish.

The trick is that binary is enough. Any sequence of bits can be interpreted as a number, so you can convert from binary to any other system and back.

But, it turns out unary is enough too. You can encode 9 as 111111111. This isn't particularly efficient, but it has the same computational power.

Things get even crazier when you look into alternate models of computation, like the Lambda calculus. Here, you can view numbers as functions. In fact, you can view everything as functions. Things are encoded not as bits, 0s and 1s, but as closed mathematical functions with no mutable state. See the Church numerals for how you can do numbers this way.

The point is that, 0s and 1s is a completely hardware specific issue, and the choice is arbitrary. What encoding you're using isn't particularly relevant to computer science, outside of a few subfields like operating systems or networking.

We only use binary(1,0) because we currently do not have the technology to create "switches" that can reliably hold more than two possible states. (Quantum computers aren't exactly on sale at the moment.) The binary system was chosen only because it is quite easy to distinguish the presence of an electric current from an absense of electric current, especially when working with trillions of such connections. And using any other number base in this system ridiculous, because the system would need to constantly convert between them. That's all there is to it.


Can a regular language have uncountably many strings? Obviously it can have a countably infinite number of strings. (Take the language descibed by the regular expression 0* as an example.) But can a RL have uncountably many strings? I'm leaning toward no, but I can't really back it up.

No, there are only countably many finite strings over any finite alphabet.  Given an alphabet $\Sigma = \{s_0, \dots, s_d\}$, you can associate the string $w$ with the number $1w$ written in base-$d$, giving an injection from the natural numbers to $\Sigma^*$.  (The reason we use the number $1w$ rather than $w$ is to avoid problems with, e.g., $2$, $02$, $002$, etc. all mapping to the same number.)

Yes,a regular language can have uncountable number of strings as a regular language can have unlimited strings by Kleene closure or sigma closure.


How many words of memory map to the same cache entry? I am going over some practice questions for the Major field exam and it asks:

A processor with a word-addressable memory has a two-way set-associative cache. A cache line is one word, so a cache entry contains a set of two words. If there are  M  words of memory and C cache entries, how many words of memory map to the same cache entry?

I am not sure how to even approach this problem since I am not too familiar with computer organization. Any help would be appreciated. Thanks!

The correct answer is M/C. This question is on the Computer science Major Field Assessment Test. https://www.ets.org/Media/Tests/MFT/pdf/mft_samp_questions_compsci.pdf

Cache has C/2 fixed locations

which further implies, we have

M / (C/2) = 2M/C

words of memory which map to same location


Finding the max XOR of two numbers in an interval: can we do better than quadratic? Suppose we're given two numbers $l$ and $r$ and that we want to find $\max{(i\oplus j)}$ for $l\le i,\,j\le r$.

The naïve algorithm simply checks all possible pairs; for instance in ruby we'd have:

def max_xor(l, r)
  max = 0

  (l..r).each do |i|
    (i..r).each do |j|
      if (i ^ j > max)
        max = i ^ j
      end
    end
  end

  max
end

I sense that we can do better than quadratic. Is there a better algorithm for this problem?

We can achieve linear runtime in the length $n$ of the binary representation of $l$ and $r$:

The prefix $p$ in the binary representation of $l$ and $r$, that is the same for both values, is also the same for all values between them. So these bits will always be $0$.

Since $r>l$, the bit following this prefix will be $1$ in $r$ and $0$ in $l$. Furthermore, the numbers $p10^{n-|p|-1}$ and $p01^{n-|p|-1}$ are both in the interval.

So the max we are looking for is $0^{|p|}1^{n-|p|}$.

For each binary digit, there are 4 possibilities: 1_and_1, 1_and_0, 0_and_1, or 0_and_0. The possible lower digits makes no or log-vanishingly-small difference to the xor output of choice of the next digit. The best possible algorithm is to ignore all lower digits and only consider the next 2 avaiable, given earlier choices about higher digits. If this is 1_and_1 or 0_and_0, the choice is clear, but if this digit is 1_and_0 vs 0_and_1 (which have equal xor but unequal value) then recursively it should equal the https://en.wikipedia.org/wiki/Edit_distance algorithm, meaning worst case of log squared.


Size of the language accepted by a Turing Machine I want to figure out if the following language is Turing decidable, Turing acceptable but not turing decidable, or neither. The language is

{ρ(M) : |L(M)| ≤ 10}

My question for this problem is what does |L(M)| ≤ 10 mean? At first, I thought it meant that the language will only accept strings that are less than or equal to 10 in length, but I am not sure

... what does $|L(M)| \leq 10$ mean?

This means that the size of the language accepted by the TM $M$ is less than or equal to $10$. In other words, TM $M$ accepts no more than $10$ strings (inputs), while the length of any accepted input may be greater than $10$.

if the problem is knowing if a TM accepts (or recognices) less than 10 words, then it can be acceptable or decidible, coz to recognize only 10 or less words you need to test the entire language associated to the original alphabet and determinate the "non-recognotion" of almost all words...

so neither

respecting the question of the matter of the size of the accepted words in relation to the fact of being decidible or not...
usually is easier to recognice have more than N words than less than N...
 because "more than" means you only need to find the first N words and finish.
On the other side, "less than" means you need to check all words to be sure that there are only N words and no more(wich means infinite cases to check)


Show that Knapsack-like problem on directed graph is NP-hard Let $G=(V,A)$ represent a directed acyclic graph, where a value $v_i \ge 0$ is assigned to every vertex $u_i$. Let $T$ represent a threshold and $N = |V|$. Problem statement:

maximize: $\sum_{i=1}^{N}v_i x_i$

subject to: $\sum_{i=1}^{N} x_i \leq T$ and $x_i \in \lbrace 0,1 \rbrace$

and $x_i(x_j-1) = 0 \quad \forall a\in A: u_i \to u_j$

In other words, we want to choose up to $T$ vertices that maximize the sum of their values, with the restriction that if a vertex $u_i$ is chosen, any reachable vertices $u_j$ must also be chosen. Therefore, $x_i(x_j-1) = 0$ for a given arc $u_i \to u_j$ represents that if $u_i$ is chosen ($x_i = 1$) then $u_j$ must be chosen as well ($x_j = 1$).

I want to prove that this is a NP-hard problem. To do that, I have taken the 0-1 knapsack problem, which is NP-hard:

maximize: $\sum_{i=1}^{M}v_i x_i$

subject to: $\sum_{i=1}^{M} w_i x_i \leq T$ and $x_i \in \lbrace 0,1 \rbrace$

The 0-1 knapsack may be reduced to an instance of the original problem. Assume an instance of the original problem, with the following properties of $G$:

$v_i = 0$ for every vertex $u_i$ with incoming arcs.
All vertices have at most 1 incoming arc.

The 0-1 knapsack may be reduced to this instance by the following polynomial transformation:

There are $M$ items, where $M$ is the number of vertices $u_i \in G: v_i > 0$.
The value $v_i$ of each item the value $v_i$ of vertex $u_i$.
The weight $w_i$ of each item is $1+$ the number of reachable vertices from $u_i$.

Explanation:

Since vertices with a non-zero value have no incoming arcs, they may be chosen independently, as there is no possibility for such a vertice to be chosen twice, as a "dependency" of another one. Thus, individual items in the knapsack problem may be mapped to these vertices.
As no vertice has more than 1 incoming arc, no vertice may be reached by multiple vertices. This guarantees that the weights of each knapsack item are independent of each other.

Questions

Have I formulated the original problem correctly, using the mathematical notations? It's been quite some time since I have formally formulated a graph theory problem.
Is this reduction enough to prove that the original problem is NP-hard? I only have reduced the 0-1 knapsack only to an instance of the original problem, not the original problem itself. Does this imply that the original problem is "at least as hard, if not harder" than the 0-1 knapsack?
Assuming that question (2) stands, is my reduction correct?
Alternatively, could I demonstrate my case via another reduction?

$x_i \leq x_j \forall (i,j) \in A$ is a linear constraint that represents your requirement (if $x_i=1$ it would push $x_j$ to take value $1$ as well). You get a constrained knapsack problem. You can easily reduce a knapsack to it by considering a graph that simply has no arrows.


Is Big-Oh notation preserved under monotonic functions? I was just looking at the big-Oh notation. I wanted to know if the following is true in general
$$f(n)=O(g(n)) \implies \log (f(n)) = O(\log (g(n)))$$

I can prove that this is true if $g$ is monotonically increasing, but am not sure if this holds in general.

By definition,
$$ f(n) \in O(g(n))$$
means there exists some positive constant $c$, such that for any large enough $n$,
$$ |f(n)| \le c |g(n)|$$
or equivalently, $\lim_{n\to\infty} \frac{f(n)}{g(n)}  \le c < \infty$

Taking $\log$ of both sides, for any large enough $n$ it holds that
$$ \log (f(n)) \le log (c) + \log(g(n)) $$

so,
$$\frac{\log f(n)}{\log g(n)} \le \frac{\log c}{\log g(n)}+ c$$

Now can this go to infinity? only if  $\log(g(n)) \to 0$

So let's try, and take $f(n)=2^{-n}$ and $g(n)=1/n$. Obviously $f(n) \in O(g(n))$.
Yet, taking the logs we have $\log f(n) = -n$, $\log g(n) =-\log n$, and it is clear that no constant $c'$ will satisfy $|\log f(n)| \le c' |\log g(n)|$ for large enough $n$. Yet, I always find it weird to discuss $O$ of negative functions.

EDIT:

Here's example w/o negative function. Get back to the requirement of $\log(g(n)) \to 0$. Take $g(n) = 1+1/n$. Thus $\log (g(n)) \to 0$.
(actually, the above example of $2^{-n}$ vs $1/n$ satisfies $g(n)\to 0$ rather than $log(g(n))\to 0$. Oops).

If we take $f(n) = 2 + 1/n$ then $\log f(n) \to 1$ (binary log, obviously).

so while $f(n) \le 3g(n)$ for every $n\ge 1$, it is not true that
$\log f(n) \le c' \log g(n)$ for all large enough $n$, as the right-hand side approaches zero, while the left-hand side approaches 1.

while g(n) and f(n) are non negative , and bigger than 1, this is true for every functions.


PERMUTE-BY-SORTING with similar priorities Let $a$ and $b$ be integers, and let $\text{RANDOM}(a,b)$ be a method returning an integer from the range $[a,b]$ uniformly at random. Now consider the following program, that takes as input an array $A$ of integers.

PERMUTE-BY-SORTING(A)
    1. n = A.length
    2. let P[1..n] be a new array
    3. for i = 1 to n
    4.     P[i] = RANDOM(1, n^3)
    5. sort A, using P as sort keys

I'm solving the problem 5.3-6 in CLRS, which is asking me to explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. In other words, the algorithm should produce a uniform random permutation, even if two or more priorities are identical.

Because priorities are repeated in $P$, we will not get a uniform random permutation. I thought of adding i to step 4 but that doesn't produce the uniform random permutation. More specifically, the problem is that if two or more priorities are identical we will not get a uniform random permutation since the probability is not same for all the numbers. Ex 1,2,2,3 the probability of 2 in the example is 1/2 and the probability of 1 is 1/4 and 3 is 3/4.

The easiest way is to generate a random permutation in $P$. Here is pseudocode:

Initialize $P$ with $P[i] = i$ for $i = 1,\ldots,n$.
Repeat for $i = 1,\ldots,n-1$:

Let $j$ be a random number in the range $i,\ldots,n$.
Swap $P[i]$ and $P[j]$.

If our initial array is A = <1, 2, 3, 4> and we choose random priorities P = <36, 3, 97, 19>,   we would produce an array B = <2, 4, 1, 3>

Now if random priority array P= <36,3,3,19> and now we use elements of P to sort array A, using say merge sort, our resulting array B would be <2,3,4,1>. As we saw, all the elements are still equally likely to be produced.


Why is data in computer science considered to be discrete? I understand that "structure" of data is totally dependent on Boolean Algebra, but:

  Why is data considered to be a discrete mathematical entity rather than a continuous one?

Related to this:

  What are the drawbacks, or invariants, that are violated in structuring data as a continuous entity in $r$ dimensions?

I am not an expert in the field as I am an undergrad math student, so I'd really appreciate it if someone would explain this to me like I'm five.

Answer

  why was the data considered to be a discrete mathematical entity rather than a continuous one

This was not a choice; it is theoretically and practically impossible to represent continuous, concrete values in a digital computer, or actually in any kind of calculation.

Note that "discrete" does not mean "integer" or something like that. "discrete" is the opposite of "continuous". This means, to have a computer that is truly able to store non-discrete things, you would need to be able to store two numbers a and b where abs(a-b) < ε for any arbitrarily small value of ε. Sure, you can go as deep as you want (by using more and more storage space), but every (physical) computer always has an upper bound. No matter what you do, you can never make a (physical) computer that stores arbitrarily finely resolved numbers.

Even if you are able to represent numbers by mathematical constructs (for example π), this does not change anything. If you store a graph or whatever that represents a mathematical formula, then this is just as discrete as anything else.

Addendum

The rest is just a little perspective beyond the field of computer science. As the comments have shown, the physical topic is not undisputed, and as you can see I have formulated my next paragraph in a way that is rather uncommitted to whether it's true or not. Take it more as a motivation that the concept of "continuum" is not a trivial one. The answer given above does not depend on whether space is discrete or not.

Note that all of this is not so much a problem of computers, but a problem with the meaning of "continuous". For example, not everyone even agrees, or did agree in the past, that the Universe is continuous (e.g., Does the Planck scale imply that spacetime is discrete?). For some things (e.g., energy states of electrons and many other features in Quantum (sic) Mechanics) we even know that the Universe is not continuous; for others (e.g., position...) the jury is still out (at least regarding the interpretation of research results...). (Notwithstanding the problem that even if it is continuous, we could not measure to arbitrary precision => Heisenberg etc.).

In mathematics, studying the continuum (i.e., the reals) opens up a lot of fascinating aspects, like measure theory, which makes it utterly impossible to actually store a "continuous" kind of number/data.

For a computer to work with data, the data must exist within the computer's accessible memory
A computer's accessible memory is finite
Only finite data can exist within a computer's accessible memory
Non-discrete values are infinite

Data in computer science is considered to be discrete.


Grammar for ${a^n b^n c^{n+m}}$ Can we define a grammar for the following language?

$$L = \{a^n b^n c^{n+m} | n,m>=0\}\,.
$$

I can define one for this:
$$L=\{a^nb^n|n,m>=0\}
$$

  S --> aSb | λ

or this one:
$$L=\{b^nc^{n+m}|n,m>=0\}
$$

  S --> Ac
  A --> bSc | Sc | λ

but I can't solve the first one, any hint?

GRAMMAR FOR THE LANGUAGE:{a^n b^n c^n/n>=1}

S->abc|A

A->aABc|abc

cB->Bc

bB->bb

FOR EXAMPLE:INPUT STRING aaabbbccc when n=3

S->A

->aABc

->aaABcBc (A->aABc)

->aaabcBcBc   (A->abc)

->aaabBccBc   (cB->Bc)

->aaabBcBcc   (cB->Bc)

->aaabbcBcc   (bB->bb)

->aaabbBccc   (cB->Bc)

->aaabbbccc   (bB->bb)

Grammar for the language $\{a^nb^nc^n \mid n\ge1\}$:
$S\to aSBC\mid aBC$
$CB\to BC$
$aB\to ab$
$bB\to bb$
$bC\to bc$
$cC\to cc$


Polytime algorithm for SUBSET-SUM assuming P=NP In the Wikipedia page on P vs. NP problem there is an algorithm that "solves" SUBSET-SUM in case P=NP in polynomial time. (It's idea is to find a TM that gives a certificate). But it gives "yes" in polynomial time and runs forever if the answer is "no". It can be obviously fixed to give "no" in exponential time (just to run exponential algorithm if the first one is running for too long).

But can we explicitly describe an "honest" algorithm, which solves (and I mean, really solves) SUBSET-SUM (or any other NP-complete problem) in polynomial time assuming P=NP?

By "honest" and "really solves" I mean that the algorithm meets the classical definitions for a polynomial-time algorithm, i.e., here should exist constants $C_1, C_2$ such that at any input $x$ algorithm would terminate in no more than $C_1 \cdot |x|^{C_2}$ steps and output "yes" if $x \in $ SUBSET-SUM and "no" otherwise. The Wikipedia algorithm does not satisfy the first condition, so it doesn't "really solve" the problem.

I can half-answer this, but I believe the deeper question you are getting at is something I am in the process of learning better :)

The algorithm on wikipedia, call it W, is based on the idea: rather than guess at certificates why not just guess at the deterministic P algorithm D itself? This is expensive, but since it is independent of the input it is O(1) (if such an algorithm exists). The algorithm actually always decides even if P != NP, because there is of course a series of "brute force" programs that print out just one possible certificate then halt, so W can fall back to a very slow brute force.

The problem is that you actually have no way to verify the program it returns to you. You may imagine running W and find it seems to prefer a certain program, but you may find that on larger input it eventually finds a flaw in that program and moves on. It may seem to settle on an algorithm that seems to be $n^7$ but later on find a mistake in it and switch to an $n^{2000}$ algorithm. You will never know when it has found the "right" one.

This is actually the same idea used in the proof of the Karp-Lipton theorem: given enough computation power you can use it to just start guessing entire classes of programs and verify that they work (the proof is exactly, "guess a program, and verify that it works, then use it", which takes a bit of computational power - more than NP - to pull off.)

I am not aware of theory regarding how complicated a solution can be, but perhaps someone more knowledgeable can answer.

The more concrete scenario in the P=NP reality is that someone actually constructs an algorithm to any NP-complete problem, such as SAT.

I think you asked a good question and I'm curious how to fill in the gaps in my answer, regarding how W may be analyzed and made more useful in semi-practice.

I'll try a partial answer to your question, but I think it should be enough for your quest.

Being NP-complete resorts to being NP AND NP-HARD.

Being NP-HARD means every problem in NP could be translated, via a polynomial time transformation, into this problem.

SSP is know to be NP-HARD (and NP-COMPLETE).

This means, for instance, that you could look-up in the internet, for the specific Polynomial-Time transformation that SHOWS that SSP is NP-HARD (on any paper that proves it).

That transformation is an "honest" algorithm, is guaranteed to run in Polynomial-time, and is written in some paper, somewhere. Let's call it 'SSP-T' (for SSP transformation).

The only way to prove that P=NP is to EXHIBIT an polynomial-time algorithm for a problem in NP.

So if you assume that P=NP, you are assuming YOU HAVE IN YOUR VERY OWN HANDS an "honest" polynomial-time algorithm for solving one (any-one) NP problem.
Let's call that algorithm: 'H'

Now... given any problem in NP, let's call it 'My-NP-problem'...

The Solution you are looking for is:

Apply SSP-T to transform it into an instance of SSP,
Now use SSP-T again to transform this SSP instance into an instance of 'H' (the ONE --any-one-- problem NP that YOU KNOW how to solve in P --based on the assumption that P=NP--),
Run H to find a solution.
Use SSP-T to interpret the solution under SSP
Use SSP-T once more to interpret the solution under 'My-NP-problem' (the arbitrary problem you wanted to solve in the beginning).

And there you go!

These 5 sequential steps are the "honest" algorithm you were looking for.

Each step runs in polynomial time and is guaranteed to exist by the very definition of each concept.

You could have chosen any other NP-HARD problem, instead of SSP,
because the definition of NP-HARD is the one that guarantees (by definition!) that:

SSP-T exists,
is an algorithm,
is bidirectional,
is valid and applies to any NP problem; and
runs in Polynomial-Time

In fact if you look the most usual way to show that any problem is NP-HARD is VIA a transformation into SAT-3, which was one of the first problems to be shown NP-HARD (sometime in the 60s/70s).

Let me know of any weakness you might find in the reasoning/explanation I gave.


Advances in recent time in Von-neumann self replication idea I have read about Von-neumann self replication from  Theory of Self-reproducing automata, which are lecture notes reconstructed from lectures in book of the same name. Theory of Self-reproducing automata

  Its looks really interesting that neumann has formalize this even far before the discovery of DNA. I'm looking the work now from biological perspective and the work by Jeremy England his paper on Statistical Physics of Self-Replication and other similar work in irreversible biological process.

The work that Von-neumann did was around 50's. Is there any recent relevant work in this field based on the neumann's work. One that i could see is Enhancing the Robustness of
Self-Replication Processes

Thank You.

For those who don't know, I am the world's only producer of a von Neumann 29-state self-replicating cellular automaton.
Indeed, respecting vNCA, I am the world's expert.  Ask Sayama (U Binghamton), Reggia(U of Maryland), or Adamatzky (U of South of England).
While DW may be a moderator, he does not know anything about von Neumann's cellular automata, I dare say he has not designed such self-replicators, and he certainly had not designed a machine zygote.  For my design of a machine zygote, see here:
https://www.researchgate.net/publication/235432119_Computational_Ontogeny
One more thing, it is 29 states, not 28.


DFA for Strings with third symbol from RHS as 1 How can we make a DFA for given condition in title from alphabets {0,1} (binary).

What can be the regular expression for this?

My calculated expression is (a+b)*a(a+b)(a+b) , please correct me if i'm wrong and help find the correct expression and it's DFA.

You probably want to substitute $a$ with $1$ and $b$ with $0$ but apart from that your solution is correct.

Finding an equivalent NFA is easy with Thompson, Glushkov etc. From that you can derive an DFA via powerset construction. However, for this short expression you also can just write the DFA down. Imagine the states as storage what the last 3 symbols were, and accept if the third last was a 1, i.e. name the states 000 to 111 where 000 is the initial state and all states with a leading 1 are accepting. A transition is just a shift-left with the last read symbol on the right, i.e. $\delta(abc, d) = bcd$, with $a,b,c,d \in \{0,1\}$.

Check this out , it's not neat but it will get the work done. Correct me if i'm wrong in this DFA.


Intersection and union of a regular and a non-regular language Let $L_1$ be regular, $L_1 \cap L_2$ regular, $L_2$ not regular. Show that $L_1 \cup L_2$ is not regular or give a counterexample.

I tried this: Look at $L_1 \setminus (L_2 \cap L_1)$. This one is regular. I can construct a finite automaton for this: $L_1$ is regular, $L_2 \cap L_1$ is regular, so remove all the paths (finite amount) for $L_1 \cap L_2$ from the finite amount of paths for $L_1$. So there are a finite amount of paths left for this whole thing. This thing is disjoint from $L_2$, but how can I prove that the union of $L_1 \setminus (L_1 \cap L_2)$ (regular) and $L_2$ (not regular) is not regular?

We can prove this by contradiction.
Lets define $\overline{L_1} = \Sigma^* \setminus L_1$. Then we can reformulate $L_2$:

$L_2 = ((L_1 \cup L_2) \setminus L_1) \cup (L_1 \cap L_2) = ((L_1 \cup L_2) \cap \overline{L_1}) \cup (L_1 \cap L_2)$

We know:

Regular Languages are closed under union, intersection and complement
$\overline{L_1}$ and $L_1 \cap L_2$ are regular
$L_2$ is not regular

Now assume $L_1 \cup L_2$ is regular: Then $((L_1 \cup L_2) \cap \overline{L_1}) \cup (L_1 \cap L_2)$ is regular (as it is only a union/intersection of regular languages), so $L_2$ would be regular. That is a contradiction, therefore our assumption is false, and $L_1 \cup L_2$ can not be regular.

That is wrong. Consider $L_1 = \{a, b\}^*$, $L_2 = \{a^n b^n : n \ge 0\}$. $L_1$ is regular, $L_2$ isn't; but $L_1 \cup L_2 = L_1$.


Would proving P≠NP be harder than proving P=NP? Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP.

Let Q be one of known NP-hard problems.
To prove P=NP, we need to design a single polynomial time algorithm A for Q and
prove that A correctly solves Q.

To prove P$\neq$NP, we need to show that
no polynomial time algorithm solves Q.
In other words,
we have to rule out all polynomial time algorithms.

I have heard people say this makes the second more difficult task
(assuming that it is really true).

  Is there a reason to think that proving P=NP (assuming that P=NP)
  would be easier than proving P$\neq$NP (assuming that P$\neq$NP)?

As Raphael explains, this question is ill-posed, since at most one of P=NP and P≠NP should be provable at all. However, a similar question arises in theoretical computer science in several guises, the most conspicuous of which is in the field of approximation algorithms.

Given an NP-hard optimization problem (say, maximization), we can ask how well we can approximate it. Proving an upper bound on the possible approximation is akin to P=NP, while proving a lower bound on the possible approximation is akin to P≠NP. The former is much easier than the latter. Indeed, to prove an upper bound all one has to do is to come up with an approximation algorithm and analyze it. In contrast, all known lower bounds are conditional: they are valid only if P≠NP (indeed, if P=NP then every NP-hard optimization problem would become solvable). To prove these lower bounds, we show that if we could approximate the problem too well, then we would obtain a polynomial time algorithm for some NP-hard problem. Usually this is done via the intricate technical machinery of the PCP theorem. This field, known as hardness of approximation, can be approached only be specialists, and is technical more challenging than most approximation algorithms. So in this case at least, P=NP is indeed easier than P≠NP.

I believe it is impossible to prove P<>NP, because you would have to rule out all algorithms that could prove P=NP.  There could be an infinite number of these possible.  There is no way to disprove infinity, therefore it’s not possible.  On the other hand all it would take is a single algorithm to prove P=NP, if it is so.  Therefore, either P=NP which someone will prove, or we will never know.


Is there a strictly non-deterministic one-counter language whose complement is one-counter? Let
$A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$

Clearly, $\text{Deterministic one-counter} \subseteq A$

Is it the case that $ A = \text{Deterministic one-counter}$?

I know that for context-free languages the analogue is not the case. For example,
let $P =\{ ww^r\}$.
Then both $P$ and $\bar{P}$ are context-free but $P$ is not deterministic.
Hence $A$ defines a (strict) subset of the context-free languages.

The question is: can we construct a similar one-counter example for which the same holds?

In response to Shaull's comment above :

The first one is an image of 1-counter accepting $a^ib^j$ s.t. $j<i$

The secong one is an image of 1-counter accepting $a^ib^j$ s.t. $j>i,\ j<2i$

The third one is an image of 1-counter accepting $a^ib^j$ s.t. $j>2i$

Here a/-/plus means on seeing a, irrespective of the counter value, increment the counter.
b/>1?/sub means on seeing b, if counter value is greater than 1, then decrement the counter.

nop =>  no operation

$\lambda $ => empty string


When to use DFS and when use BFS? Preparing for an interview.

I see two cases where each one is specially suited

BFS:  When you need to find shortest path between vertices (if one exists).

DFS:  If you need to find cycles in a directed graph:

Uses-case where both can be used:  Finding cycle in undirected graph, Is there a path from one vertex to another

Are there any other specialized or common cases?

In general DFS is considered to be simpler (though if graph is very deep, I am assuming we can have a stack overflow due to excessive recursion). So, if both can be used for a use-case, use DFS?

Bfs and Dfs both are good state space search algorithms. If search space is infinite then its good to use Bfs because dfs can be lost in infinite space and will not return any result.
Also, Bfs searches result in neighbors and then go neighbor by neighbor on other hand dfs searches for answer branch by branch. If you search key is near starting point then go for bfs


what is the name for the space between the leaves of a tree I am trying to write a data-type not for a tree, but for the spaces in between the leaves of thee tree.  In number theory (a part of math) this is known as a topograph does it have a name in CS?

The empty space is called "OTIOSE".   Pronounced "oh-she-ohs"

otiosity

Synonyms & Antonyms for otiose
Synonyms
abortive, barren, bootless, empty, fruitless, futile, ineffective, ineffectual, inefficacious, profitless, unavailing, unproductive, unprofitable, unsuccessful, useless, vain


What is the most efficient way to compute factorials modulo a prime? Do you know any algorithm that calculates the factorial after modulus efficiently?

For example, I want to program:

for(i=0; i<5; i++)
  sum += factorial(p-i) % p;

But, p is a big number (prime) for applying factorial directly $(p \leq 10^ 8)$.

In Python, this task is really easy, but i really want to know how to optimize.

(This answer was initially posted by the asker jonaprieto inside the question.)

I remember Wilson's theorem, and I noticed little things:

In the above program, it is better if I write:
$$\begin{align}
(p-1)! &\equiv -1 &\pmod p\\
(p-2)! &\equiv (p-1)! (p-1)^ {-1} \equiv \bf{1} &\pmod p\\
(p-3)! &\equiv (p-2)! (p-2)^ {-1} \equiv \bf{(p-2)^{-1}} &\pmod p\\
(p-4)! &\equiv (p-3)! (p-3)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}} &\pmod p\\
\ (p-5)! &\equiv (p-4)! (p-4)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}}\bf{(p-4)^{-1}}  &\pmod p\\
\end{align}$$

And you can find $(p-i)^{-1}$ because $\operatorname{gcd}(p, p-i) = 1$, so with the extended Euclidian algorithm you can find the value of $(p-i)^{-1}$, that is the inverse modulus.

You can view the same congruences too,  like to:
$$\begin{align*}
(p-5)! &\equiv (p-24)^{-1}&\pmod p\\
(p-4)! &\equiv (p+6)^{-1}&\pmod p\\
(p-3)! &\equiv (p-2)^{-1} &\pmod p\\
(p-2)! &\equiv 1&\pmod p\\
(p-1)! &\equiv -1&\pmod p\\
\end{align*}
$$
so, the sum is equal: $$ (-24)^{-1}+(6)^{-1} +(-2)^{-1}$$
and if you factorize in the beginning the factorials you get
$$ 8\cdot (-24)^{-1} \pmod p$$
And, voila, inverse modulus is more efficient than factorials.

This is my implementation use of the wilson's theorem:

The factMOD function is the one to call to compute (n!) % MOD when MOD-n is little against n.

Do someone know an other efficient approach when it's not the case (e.g: n=1e6 and MOD=1e9+7) ?

ll powmod(ll a, ll b){//a^b % MOD
  ll x=1,y=a;
  while(b){
    if(b&1){
      x*=y; if(x>=MOD)x%=MOD;
    }
    y*=y; if(y>=MOD)y%=MOD;
    b>>=1;
  }
  return x;
}
ll InverseEuler(ll n){//modular inverse of n
  return powmod(n,MOD-2);
}
ll factMOD(ll n){ //n! % MOD efficient when MOD-n<n
   ll res=1,i;
   for(i=1; i<MOD-n; i++){
     res*=i;
     if(res>=MOD)res%=MOD;
   }
   res=InverseEuler(res);
    if(!(n&1))
      res= -res +MOD;
  }
  return res%MOD;
}


DFA for strings with number of 0's odd only in substring longer than 1 I'm trying to design and DFA that accept string with an odd number of 0`s, but counting only the ones within sub-strings with two or more 0.

So, for example, 011000, will be accepted since it has 4 0`s, but only three or them are inside a sub-string of two or more. But 0001000, wont be accepted.

I believe your language is not regular and if I'm not mistaken, the pumping lemma suffices:
Let us assume by contradiction your language is regular, thus it should hold all 3 conditions of the pumping lemma.

Let $w=0^{2p+1}111$, notice $w\in L$ because $2n$ is always even, thus by adding $1$ we have an odd number of $0$s.

Now let us take a simple example where $p=1$, but this should work for any $p$.

In this case, $p=1$, notice $|w|>p$, since $|w|=5$, essentially $w=000111$. In our case this means $y=0$ and because $|xy|\le 1$ and because $|y|>0$  where 1 is our pumping length this means $x=\epsilon$.

This leaves $z=0011$. However, for $i=2$, we receive: 000011 which is $y^2z \equiv 000011 $.

Then the number of 0s in your substring is now even, meaning $000011 \notin L$.
Again, we can do this for any pumping length $p$ by simply pumping up or pumping down.

Thus there won't be a DFA/NFA for that. You can try using a TM.

For more information: pumping lemma.


Floyd's Cycle detection algorithm | Determining the starting point of cycle I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)

I can see how the algorithm detects cycle in O(n) time. However, I am unable to visualise the fact that once the tortoise and hare pointers meet for the first time, the start of the cycle can be determined by moving tortoise pointer back to start and then moving both tortoise and hare one step at a time. The point where they first meet is the start of the cycle.

Can someone help by providing an explanation, hopefully different from the one on wikipedia, as I am unable to understand/visualise it?

You can refer to "Detecting start of a loop in singly linked list", here's an excerpt:

Distance travelled by slowPointer before meeting $= x+y$
Distance travelled by fastPointer before meeting $=(x + y + z) + y = x + 2y + z$
Since fastPointer travels with double the speed of slowPointer, and time is constant for both when both pointers reach the meeting point. So by using simple speed, time and distance relation (slowPointer traveled half the distance):
\begin{align*}
2*\operatorname{dist}(\text{slowPointer}) &= \operatorname{dist}(\text{fastPointer})\\
2(x+y) &= x+2y+z\\
2x+2y &= x+2y+z\\
x &= z
\end{align*}
Hence by moving slowPointer to start of linked list, and making both slowPointer and fastPointer to move one node at a time, they both have same distance to cover.
They will reach at the point where the loop starts in the linked list.

The tortoise and the hare are two pointers that are initialized with the value of the "top" of the list. In each cycle of the loop, the hare increases by 2 incremental items, while the tortoise increases by one. If at any point, the hare equals the hare, a loop has been detected. If the hare equals the end, a loop is not found.

This post explains it better line-by-line:

https://www.thiscodeworks.com/floyd-s-cycle-detection-algorithm-aka-the-tortoise-and-the-hare-algorithms-logic-interesting/5e10a9b796432f6f7b798b29


Context-free grammar for"not-at-all" palindromes I need to bulid a context-free grammar for

$\qquad \mathscr{L_4}=\{w\in\{a,b,c\}^* \mid w\text{ is not palindrome at all}\}$

Not palindrom at all:
We will say that a word $w$ is not palindrome at all if for all $i$ such that $1\leq i\leq |w|$ the $i$ letter from the beginning of $w$ is not the same like the $i$ letter of $w$ from the end, for example $abbacb\in \mathscr{L_4}$ but $ca\color{gray}bba\color{gray}bcb\notin\mathscr{L_4}$, the word must contain a even number of digits, because if there were an odd number of digits, so the middle digit "equals to itself".

My attempt:
 Let's denote $S_{\text{pal}}$ from palindrome grammar and  $S_{\neg\text{pal}}$ for the not palindrome at all grammar

$$\\S_{\neg\text{pal}}\to a S_{\neg\text{pal}}b\big|bS_{\neg\text{pal}}a\big|aS_{\neg\text{pal}}c\big|cS_{\neg\text{pal}}a\big|cS_{\neg\text{pal}}b\big|cS_{\neg\text{pal}}b\big|\epsilon$$

Similar question here.
I'm not sure if my attempt is correct or not

Just use something like:

$
S \rightarrow a S b \mid a S c \mid b S a \mid b S c \mid c S a \mid c S b \mid a b \mid a c \mid b a \mid b c \mid c a \mid c b
$

This ensures the $i$-th symbol from the beginning is different from the $i$-th from the end.

Your attempt looks correct to me

$$\\S_{\neg\text{pal}}\to \color{red}a S_{\neg\text{pal}}\color{blue}b\big|\color{blue}bS_{\neg\text{pal}}\color{red}a\big|\color{red}aS_{\neg\text{pal}}\color{green}c\big|\color{green}cS_{\neg\text{pal}}\color{red}a\big|\color{blue}bS_{\neg\text{pal}}\color{green}c\big|\color{green}cS_{\neg\text{pal}}\color{blue}b\big|\varepsilon$$

Let us say that for a word of length $n$ such that $n\in\mathbb{N}$ is even  for each letter in the $i$ from the begining  $1\leq i\leq n$ you ensure that in the place $i$ from the end you have a diffrent letter

for example: $\color{red}a\color{blue}b\color{green}c\color{blue}b\color{red}a\color{blue}b\in \mathscr{L_4}$


Worst run-time for 3 nested loop Suppose we need to find a tight asymptotic bound on the worst case run time of the following program

t = 0;
for i = 0 to n-1 do
  for j = i+1 to n-1 do
    for k = j+1 to n-1 do
      t++;

I can't for the life of me figure out what the run-time would be. I have a feeling it would have n! in there somewhere, but I can't seem to wrap my head around it. All help is appreciated

I suggest you slightly modify your program, as follows:

int i, j, k, t = 0;
for (i = 0; i <= n - 1; i++)
  for (j = i + 1; j <= n - 1; j++)
    for (k = j + 1; k <= n - 1; k++)
      t++;

Now run this program for various values of $n$ and print the corresponding values of $t$, which is your runtime $T(n)$. Make a guess at the growth rate of $T(n)$ based on this. Try to prove your guess.

Another idea is to try to understand what happens when you have only one loop, then two nested loops, and then all three nested loops. The first case in particular is pretty easy.

(n-1)(n)(n+1)/6
This is the formula

n(n+1)(n+2)...(n+r-1)/r!

where r is the number of nested loops.


Dynamic programming: speed of top down vs bottom up approaches I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. Is the top down approach significantly slower because of the recursion?

I thought that bottom up approaches needed to compute everything: eg if we have a result array of size n, we run a loop from i=0 to i=n to find result[i], whereas the top down approach only computes relevant entries (we start at i=n then go down to 0, but we might skip some of the entries in between). So I thought the top down approach would be faster.

Or maybe there was just a bug in my top down approach.

Update:
The problem on LeetCode is:
" You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1."

I defined an array result of size amount+1; result[i] is the minimum number of coins needed to reach amount i (with result[0] = 0).

If we have N coins, and coin j has value V[j], the recursion is:
result[i] = 1 + minimum of result[i-V[j]] for all j=1...N (only the j for which i-V[j]>=0)

I used a bottom up and top down approach to compute result[amount]:

If we don't have a coin of value 1, we won't need to compute result[i] for every i with a top down approach.

The time limit was exceeded for top down with this input: Coins: [186,419,83,408], Amount: 6249

Top down approach would be faster in cases where the no of entries that you have to compute are significantly less than than the total number of entries. Remember, recursive approach is slow than iterative approach because there is some overhead of function call too.

Top down approach fails in some cases because it works by recursion. In recursion you require space (stack space) for storing each function call. Now, if the depth of your recursion tree is large you may run out of stack space. In that cases iterative approach (like bottom to top approach) works because you can use memory from heap and running out of stack space is not an issue there.

What makes it slow isn't top down vs. bottom up. It will be slow if (a) you calculate the same intermediate result again and again, and (b) if you calculate results that in the end you don't need.
Typically top-down will tend to waste time by evaluating the same intermediate results again and again, unless you do something about it. And typically bottom-up will calculate intermediate results that you never need, unless you do something about it. Which is worse depends on the nature of the problem, and on your cleverness avoiding multiple or unnecessary evaluations.


Theta estimation of two functions I'm in a data structures class, and am working on an assignment right now that asks me to find the theta complexity of certain loops. I missed class the day we were introduced to the topic, and everything I can find online expects more prior knowledge than I feel I have. Can someone just explain this in beginners terms for me? I don't know what Big-O or theta even refer to in this notation. I think I have a loose idea of what "complexity" refers to (a measure of how efficient code is, depending on how long a function will take in different circumstances?)

The problem in question:

Demonstrate the $\Theta$-complexity of the functions below. In order to demonstrate that $f(n) = \Theta(g(n))$ you must find two constants $C_1$ and $C_2$ such that
$$ C_1g(n) ≥ f(n) ≥ C_2g(n). $$

a.) $f(n) = n^3 - 3n^2 + 5$.

b.) $f(n) = 2\log_2 n - 4$.

The exercise being asked about is pretty stupid (this is criticism against the person who set it as an exercise, not the OP). Every (positive) function $f$ is its own big $\Theta$, that is $f(n) = \Theta(f(n))$. Nevertheless, whoever asked the question expected the following answers: $f(n) = \Theta(n^3)$ and $f(n) = \Theta(\log n)$. There are many online and offline resources that can explain why this is the case and how to prove it, or you can try working through the algebra yourself.

Please let the poser know that the following answers are as mathematically correct as the expected one: $n^3 - 3n^2 + 5 = \Theta(17n^3 - 2n\log n + 4\log\log n)$ and $2\log_2 n - 4 = \Theta(4\log_4 n - 2)$. In order to rule out these answers, the poser should have phrased the question as follows:

  For each of the following functions $f(n)$, find a function $g(n)$ of the form $n^\alpha (\log n)^\beta$ such that $f(n) = \Theta(g(n))$, and prove that $f(n) = \Theta(g(n))$.

Note that in general a function $g(n)$ of that specific form might not exist, for example if $f(n) = n\log\log n$, or for the following more exotic function: $$f(n) = \begin{cases} n & \text{ if $n$ is odd,} \\ n^2 & \text{ if $n$ is even.} \end{cases}$$
Such functions nearly show up in modular exponentiation, FFT-based algorithms, and fast matrix multiplication, though in these cases the difference is only in the constant (e.g. $n$ vs. $2n$) rather than the asymptotics.

The Complexity of an algorithm is the behavior that it have in memory or time (execution). This means that, for example, if you have an algorithm to explore a matrix of dimensions nxn to find a number, then the algorithm have a Complexity equals to Big-O(n^2). This because, in the worst case, you need to explore the nxn locations of the matrix. The theta complexity, refers to algorithms that have an exact behavior, i.e., if you have an algorithm to explore everyone of the locations of a Matrix with nxn dimension, that algorithm have a Complexity Theta(n^2), because you are exploring (no more, no less) the complete matrix nxn.

This is very abstract, I recommend you read about Asymptotic analysis


Lexicographic permutation list Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order?

Thanks.

You might not be able to generate lexicographic permutations for any sequence of arbitrary objects. In order to do so, you will need some way of comparing two objects and determining which one is smaller.

Assuming you have this, you could use the following algorithm to generate all permutations of a sequence of $n$ objects in lexicographic order.

Start by sorting the input sequence, $A$, of $n$ objects
Find the largest index $k$ such that $A[k] < A[k+1]$.  If no such $k$ is found, terminate. The sequence $A$ contains the last lexicographic permutation.
Find the largest index $l$ such that $A[k] < A[l]$
Swap $A[k]$ and $A[l]$
Reverse the sub-sequence starting from $A[k+1]$ to the final element, $A[n-1]$

Note that this algorithm generates the next lexicographic permutation of $A$ in-place. To generate all permutations, you can repeat this until no more permutations are found.

I found the following code here:

https://github.com/nzanella/universitycode/blob/master/lexpermlist.c

The code exploits the idea that the next permutation can be computed from the previous one by group theoretic multiplication by a product of four specifically indexed permutations in each step, which can be discerned from the code.

/* lists all permutations of the first n positive integers */
/* in lexicographic order.                                 */

#include <stdio.h>

#define N 20 /* maximum length of an n-tuple */
#define TRUE 1
#define FALSE 0

typedef int Bool;

int a[N + 1], n;

void step_in(void);
void next_permutation(const int left_index, const int right_index);
void print_permutation(void);
void get_n(void);
void initialize_a(void);

main()
{
   get_n();
   initialize_a();

   step_in();

   return 0;
}

/**********************************************************
 * step_in: this recursive function manipulates the       *
 *          values of left_index, right_index, and        *
 *          direction. These variables control the        *
 *          general flow of the algorithm, determining    *
 *          whether a permutation is to be computed or    *
 *          printed and whether the function is to be     *
 *          exited.                                       *
 **********************************************************/

void step_in(void)
{
   static enum {LEFT, RIGHT} direction = RIGHT;
   static left_index = 0;
   int right_index;   /* successive calls of step_in hide */
                      /* previous values of right_index   */

   for (;;) {
      if (direction == RIGHT) {
         ++left_index;
         right_index = n;
         if (left_index == n - 1) {
            print_permutation();
            next_permutation(left_index, right_index);
            print_permutation();
            direction = LEFT;
            break;
         }
         else if (left_index < n - 1)
            step_in();
         else {
            /* special cases where n equals 0 or 1 are treated here */
            print_permutation();
            break;
         }
      }
      else {
         --left_index;
         if (left_index < right_index) {
            next_permutation(left_index, right_index);
            --right_index;
            direction = RIGHT;
            step_in();
         }
         else
            break;
      }
   }
}

/**********************************************************
 * next_permutation: permutes the elements of the array a *
 *                   amongst themselves to obtain a new   *
 *                   permutation of these elements.       *
 **********************************************************/

void next_permutation(const int left_index, const int right_index)
{
   int i;
   int temp[N + 1];
   int top = left_index;

   temp[top] = a[right_index];
   ++top;

   for (i = n; i > right_index; top++, i--)
      temp[top] = a[i];

   temp[top] = a[left_index];
   ++top;

   for (i = right_index - 1; i > left_index; top++, i--)
      temp[top] = a[i];

   for (i = left_index; i <= n; i++)
      a[i] = temp[i];
}

/**********************************************************
 * print_permutation: prints current permutation.         *
 **********************************************************/

void print_permutation(void)
{
   int i;

   printf("\n(");
   if (n > 0) {
      printf(" %2d", a[1]);
      for (i = 2; i <= n; i++)
         printf(", %2d", a[i]);
   }
   printf(" )\n\n");
}

/**********************************************************
 * get_n: prompt user for permutation length n. Read all  *
 *        characters entered by user up to the newline    *
 *        character. Repeat if either invalid data or an  *
 *        illegal permutation length is entered.          *
 **********************************************************/

void get_n(void)
{
   Bool invalid_int_val;
   char next_char;

   for (;;) {
      invalid_int_val = FALSE;
      printf("\n");
      printf("Enter n: ");
      scanf("%d", &n);
      for(;;) {
         if ((next_char = getchar()) == '\n')
            break;
         else if (next_char != ' ' && next_char != '\t') {
            invalid_int_val = TRUE;
            for(; getchar() != '\n';)
               ;
            break;
         }
      }
      if (invalid_int_val || n < 0 || n > N) {
         printf("\n");
         printf("The number n must be an integer between %d and %d. Try again.\n", 0, N);
      }
      else
         break;
   }
}

/**********************************************************
 * initialize_a: initializes array a.                     *
 **********************************************************/

void initialize_a(void)
{
   int i;

   for (i = 1; i <= n; i++)
      a[i] = i;
}


How many vertices should be disconnected to make a graph acyclic? Given an undirected graph with some cycles:

we can "disconnect" the red vertex by adding a separate vertex to each of the edges adjacent to it:

In this case, disconnecting a single vertex makes the graph acyclic.
My questions:

What is a term for the smallest number of vertices that must be "disconnected" like this, to make the graph acyclic?
What is an algorithm for finding a smallest such set of vertices?

(I found some related concepts, but they are different:

The circuit rank is the number of edges that have to be removed to make the graph acyclic; it always equals the number of edges minus the number of vertices plus the number of components.
The vertex connectivity is the number of vertices that have to be removed to make the graph disconnected.)

A set of vertices whose removal makes the graph acyclic is called a feedback vertex set (FVS). What you seem to be doing is finding the smallest FVS, subdividing all edges incident to each vertex in the FVS, and finally deleting the vertices in the FVS.
Computing the smallest FVS is NP-hard, but it admits 2-approximation.

If you have a connected graph, e.g. Prim's algorithm gives you a spanning tree (no cycles).


Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results) I'm reading Homer and Selman's "Computability and Complexity" book. In some Corollary 5.3 it says:

  For all ε > 0, DTIME(O(n)) = DTIME( (1+ε) n).

Now I'm confused with this corollary and Rosenberg's result (p87 in the same book):

  DTIME(n) ≠ DTIME(2n).

Why can we not use the corollary to show that DTIME(n) = DTIME(2n)?

$\mathrm{DTIME}(O(n))$ is the set of problems that can be solved in deterministic $O(n)$ time for some constant implicit in $O$, in other words, it is the union of the $\mathrm{DTIME}(cn)$ for all $c>0$.  That this union is, in fact, equal to $\mathrm{DTIME}(cn)$ for any given $c>1$ (i.e., $1+\varepsilon$) means that all the $\mathrm{DTIME}(cn)$ for $c>1$ are equal, it does not say anything about $\mathrm{DTIME}(n)$, so there is no contradiction with the fact that $\mathrm{DTIME}(n)\neq \mathrm{DTIME}(2n)$ (although the results could have been stated in a clearer way).

In a purely mathematical sense, if n = 0, than DTIME(n) DOES = DTIME(2n), because 0 multiplied by any number = 0. So, if n = 0, DTIME(n) = DTIME(2n).

I dont know if this helps, but I hope it does.


Understand the time complexity for this LCS (longest common subsequence) solution I would appreciate an intuitive way to find the time complexity of dynamic programming problems. Can anyone explain me “#subproblems * time/subproblem”? I am not able to grok it.

Code for LCS -

public static String findLCS(String str1, String str2 ) {
    // If either string is empty, return the empty string
    if(null == str1 || null == str2)
        return "";
    if("".equals(str1) || "".equals(str2)) {
        return "";
    }
    // are the last characters identical?
    if(str1.charAt(str1.length()-1) == str2.charAt(str2.length()-1)) {
        // yes, so strip off the last character and recurse
        return findLCS(str1.substring(0, str1.length() -1), str2.substring(0, str2.length()-1)) + str1.substring(str1.length()-1, str1.length());
    } else {
       // no, so recurse independently on (str1_without_last_character, str2)
       // and (str1, str2_without_last_character)
       String opt1 = findLCS(str1.substring(0, str1.length() -1), str2);
       String opt2 = findLCS(str1, str2.substring(0, str2.length()-1));
       // return the longest LCS found
       if(opt1.length() >= opt2.length())
           return opt1;
       else
           return opt2;
    }
}

I am just providing the actual code instead of pseudo code (i hope pseudo code or the algo is pretty self explanatory from above)

I assume you are interested in worst-case complexity.

A dynamic programming approach (recursively) breaks a problem into "smaller" problems,
and records the solution of these subproblems to make sure
that subproblems are not computed several times. So when the time required to combine subproblems is constant (it is the case for LCS), you only have to find an upper bound for the number of possible subproblems that will be solved along the program.

Here the subproblems are of the form
findLCS(s1,s2) where s1 is a prefix of str1, and s2 a prefix of str2.
There are (1+str1.length()) possible prefixes for str1, and
(1+str2.length()) for str2.
The number of possible subproblems is therefore (1+str1.length()) * (1+str2.length()).
Furthermore, a solution is obtained in constant time from its subproblems.
Hence complexity O( str1.length()*str2.length() ).

N.B. on some sequences all subproblems will be indeed computed, e.g., when letters in str1 and str2 are distinct.
Consequently, the quadratic bound is "tight".

N.B.2 you may find (short) explanations on the wikipedia page for LCS

The code posted doesn't implement Dynamic Programming, so the time complexity is in fact O(2^n).

See this Wikipedia article and this GeeksforGeeks post for pseudocode and specific implementations.This post also shows how to get the LCS in a recursive/iteratively way using DP.

To implement Dynamic Programming is necessary to implement a cache mechanism to prevent calculating the same sub-results multiple times.


Which of the following statements are true for the given special cases of the Traveling Salesman Problem? I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:

  Which of the following statements is true?

  Consider a TSP instance in which every edge cost is either 1 or 2. Then an optimal tour can be computed in polynomial time.
  Consider a TSP instance in which every edge cost is negative. The dynamic programming algorithm covered in the video lectures might not
  correctly compute the optimal (i.e., minimum sum of edge lengths) tour
  of this instance.
  Consider a TSP instance in which every edge cost is negative. Deleting a vertex and all of its incident edges cannot increase the
  cost of the optimal (i.e., minimum sum of edge lengths) tour.
  Consider a TSP instance in which every edge cost is the Euclidean distance between two points in the place (just like in Programming
  Assignment #5). Deleting a vertex and all of its incident edges cannot
  increase the cost of the optimal (i.e., minimum sum of edge lengths)
  tour.

I argue as follows:

The DP algorithm doesn't make any assumptions on the edge costs, so option 2 is incorrect.

If all edge weights are negative, then deleting a vertex and all of its incident edges can certainly increase the minimum sum because in effect, that edge weight is now added to the previous minimum. Thus, option 3 is incorrect.

Take the optimal tour in the original instance. Now, instead of visiting the deleted vertex v, skip straight from v's predecessor to its successor on the tour. Because Euclidean distance satisfies the "Triangle Inequality", this shortcut only decreases the overall distance traveled. The best tour can of course only be better. Thus, option 4 is correct.

However, I'm not able to find any significance for TSP problems with unit edge costs. Is option 1 merely a trick, or is there more to it?

Statement 1 is false (assuming P $\neq$ NP) because any instance $G$ of the NP-complete Hamiltonian Cycle problem can be reduced to an instance of the TSP in which every edge cost is either 1 or 2.

Why? Define a TSP instance on a complete graph $K_n$, with edge cost 1 whenever the corresponding edge is also in the original graph $G$, and edge cost 2 otherwise. Now a TSP tour of cost $\le n$ exists in the complete graph if and only if $G$ has an Hamiltonian cycle.

OP here.

Papadimitriou and Yannakakis have shown that it is possible to approximate the TSP problem 1 in polynomial time within accuracy $ \frac{7}{6} $. This guarantee has been further improved by Bläser and Shankar Ram to $ \frac{65}{56} $. However, no matter how good those results are, they are still approximations, and not an optimal solution. Thus, option 1 is incorrect.

The DP algorithm doesn't make any assumptions on the edge costs, so option 2 is incorrect.

If all edge weights are negative, then deleting a vertex and all of its incident edges can certainly increase the minimum sum because in effect, that edge weight is now added to the previous minimum. Thus, option 3 is incorrect.

Take the optimal tour in the original instance. Now, instead of visiting the deleted vertex $ v $, skip straight from 's predecessor to its successor on the tour. Because Euclidean distance satisfies the Triangle Inequality, this shortcut only decreases the overall distance traveled. The best tour can of course only be better. Thus, option 4 is correct.


Why is the vulnerable time in pure aloha twice the frame time? The time required to send a frame is called frame time.
Vulnerable time is the time during which no transmission should be done to avoid any collision.

My question is what kind of problem will be created if vulnerable time was equal to frame time?

This is because in pure ALOHA, even if a bit of a frame collides with a bit of another frame, both the frames get discarded. Also, in pure ALOHA, a station doesn't listen to the medium before transmitting. So, it has no way of knowing that another frame was already underway. If another frame was indeed underway already, then the newly transmitted frame becomes vulnerable. That is why it is called "vulnerable time". It equals twice of the frame time because it counts the time in which the transmission of another frame should start so as to make the current frame vulnerable. This time interval includes:

the frame time because if transmission of another frame were started in the frame time of the current frame, collision would occur.

a time interval (equal to the frame time) before the frame time because if transmission of another frame were started in this time interval, collision would still occur.

My question is what kind of problem will be created if vulnerable time was equal to frame time?

If the vulnerable time were equal to frame time, any frame (say A) transmitted prior to the considered frame (say B) could be transmitted within the frame time of the considered frame (B), resulting in a collision.
Suppose a sender X starts transmitting at time instant '0' and finishes at instant 't'. Then any other sender Y should start at or after instant 't' and continue till instant '2t' (because if Y start its transmission even a tiny amount of time before 't', there will be collision). Here, the vulnarable time for the frame transmitted by Y is the sum of its own frame time (i.e. 't' to '2t') and another time duration (i.e. '0' to 't'), effectively being '0' to '2t'. This is the time interval during which no sender should send on the channel to ensure that the frame sent by Y doesn't collide.

In aloha vulnerable time is twice frame time. To see why this is, suppose you transmit the msg bit in 10sec(FT) to the receiver. So when you start transmission of msg bit and before completing 10 sec if anyone is transmit another msg bit than there will be collision occur same as 10sec before you transmit the msg bit than less collision occur. So we can say total vulnerable time is twice of frame time.


Booth bit-pair recoding technique In Booth's bit-pair recording technique how to multiply a multiplicand with -2 or 2? For example while multiplying 01101(+13, multiplicand) and 11010(-6, multiplier), we get 01101 x 0-1-2.

How to multiply the multiplicand using -2?

In bit recoding multiplication, e.g.   01101 times 0, -1, or -2.

For multiplying with -1:
Take 2's complement of 01101 i.e: 10011
For multiplying with -2:
Add 2's complement of 01101 i.e: 10011 + 10011= 100110

First you must come to thr lsb of bit pair recoding i.e say 0 -1 2. So here lsb is 2 it means we must multiply 10 with multiplicand because based in the recoding table if it is positive 2 then we multiply and same procedure must be followed for next bit i.e -1 and so on


Why does DFS only yield tree and back edges on undirected, connected graphs? Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge.

Now, from intuition and in class lectures by Steven Skiena, I know that the above holds true, since it dives all the way down, and then throw a rope back to a previous vertex. I also know that DFS is great in finding cycles.

However, my problem here is that I don't know how to prove that the edge is either a tree edge or a back edge.

A depth first search on a directed graph can yield 4 types of edges; tree, forward, back and cross edges. As we are looking at undirected graphs, it should be obvious that forward and back edges are the same thing, so the only things left to deal with are cross edges.

A cross edge in a graph is an edge that goes from a vertex $v$ to another vertex $u$ such that $u$ is neither an ancestor nor descendant of $v$. So what you need to argue is that in an undirected graph, there's no way you can get a cross edge. It might help to think of why the can occur in directed graphs, and why you can't have this case in undirected graphs.

In the undirected graph we get only tree and back edges .
the reason for no forward edges is because in undirected the forward edges get converted into back edges , it is so because in undirected there is no restriction in which direction to visit the vertex, so in case we have any vertex we can visit it from the child itself to the parent which counts as a back edge.

now lets talk of cross edge
here also since edges are undirected so, the cross edges get converted to the tree edges as they can be visited as and when we go to any of that edge vertex
 for more details you can view this MIT vedio https://youtu.be/AfSk24UTFS8?t=36