Prove the halting problem is undecidable using Rice's theorem Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed:

We want to reduce Rice's Theorem (decide if a language has the nontrivial property P) to the Halting Problem
We want to say "if the Halting Problem can be solved, then we can decide if a language as nontrivial property P"

Here's how I thought the proof might go:

Suppose we have a machine H that solves the halting problem. We want to use this machine to decide if a language has property P.
We construct a machine that uses H to decide a language has property P.

Example: Take P to be "language contains the string 1".

We want to use H to decide if the language of a TM M contains the string 1, i.e that the TM halts and accepts when given input 1.

Now, if M halts on 1, that doesn't mean it accepts 1, so we don't know if L(M) contains 1. On the other hand if M does not halt on 1, that certainly means that L(M) does not contain 1.

And that's where I'm stuck. Is it actually possible to use Rice's theorem to prove that the halting problem is undecidable?

Your question contains a few hints at misunderstandings of the fundamentals that would take several pages to address. So let's focus on your final question:

  Is it actually possible to use Rice's theorem to prove that the halting problem is undecidable?

No. Rice's theorem can only be used to show undecidability of index sets and the (usual) Halting problem can not be expressed as such. For details, see here and here.


Can't understand why the DP Subset Sum algorithm is not polynomial I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial.

Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the number of iterations is always (T * n) and not exponential  I'm not understanding it.

The algorithm always do 'n*T' comparisons, and writes in the matrix only 'n*T' times...I'm missing something and I don't know what it is.

The reason is that you have to take into account the binary encoding of numbers.  The input size $m$ is really the total number of bits, so if your instance is $a_1,\ldots, a_n, T$, then $m = \log T + \sum_{i\in [n]} \log a_i$.

In particular, $T$ can be super-polynomial in $m$, so the dynamic programming algorithm's runtime can be made super-polynomial as well, since it needs to take one step to build every cell of its table. (The quantity $nT$ can be made $\Omega(2^{m/3})$ for example.)

On the other hand, when all the numbers in the instance are restricted to be "small" (i.e., polynomially bounded in $m$), the SUBSET-SUM becomes tractable.  (Notice that the usual reduction from 3SAT has very large numbers in it.)

A problem is strongly NP-Complete when it remains NP-Complete even when all the numeric values are polynomial in the input length. SUBSET-SUM isn't (it's called weakly NP-Complete).

The kind of running time that is polynomial in the numeric values in the input is known as pseudo-polynomial.


Space requirement of a universal Turing machine Given a representation $g$ (e.g. the Gödel number) of a Turing machine $B$, a universal Turing machine $A$ can simulate $B$.

If $B$ is restricted to using at most $n$ memory cells of its tape and the memory cells of $A$ and $B$ can assume the same number of states, how much space does $A$ require at least to simulate any $B$?

$A$ knows the $n$ of the $B$ of the $g$ its given.

I'm not interested in how this behaves for small $n$ or constant additive terms but would like to know constant multiplicative factors. So if $A$'s space requirement is $3 \cdot n^2 + |g|$ memory cells, that'd be nice to know, not just that its space complexity is $\in \mathcal{O}(n^2 + |g|)$.

The constant depends on the size of the respective tape alphabets. If the two are the same and you're very careful, you can probably make do with only $n + O(1)$ space, where the constant only depends on the simulated machine. The idea is to store the tape of the simulated machine from the point of view of the cell pointed to by the head, interleaving both sides of the tape. This is not the most time-efficient simulation, but the blow-up in time is still only polynomial.


Complexity terminology What is the terminology used for speaking about complexity, when we don't study it asympotically (but exactly) ?

Thank you

One common keyword that denotes this concept in contradistinction to asymptotic complexity is concrete complexity.


How can we find the number of pairs of intersecting ranges on a circular number line? I recently thought of and managed to solve this algorithmic problem:
On a infinite 1-dimensional number line, we have N ranges specified by two distinct integers A and B, such that all A and B are unique. Each pair of integers then represents the starting and ending points of a range on the number line. How many distinct pairs of ranges intersect?

^^ In this example, 4 distinct pairs of segments intersect.
Obviously, there is a O(N^2) brute-force solution: just test all possible pairs in O(1) time each. However, I also thought of a O(NlogN) sweep-line algorithm: treat every A as a "segment start event" and every B as a "segment end event". Then, keep a variable curr_in_range (originally 0) that stores the current number of segments that we currently see, and then iterate through the events in sorted order of their positions on the number line. Every time we add another segment, add curr_in_range to the answer (because this new segment will intersect with every other segment that we can see) and increment it as well. Every time we remove a segment, decrement curr_in_range. In the end, this gets us the correct answer.
Happy with this algorithm, I decided to tackle a slightly modified version of this problem: What if the number line is circular? As in, it has a specified length L such that the number line contains numbers in the range [0, L)? In this case, each range would still be specified by two distinct integers A and B, but let's just say the range is always counterclockwise starting from A and ending at B. Could we still find the number of pairs of sectors that intersect in less than O(N^2) time in this scenario?
Here's my thought process on this problem:
We should be able to use a very similar algorithm to the one described above. Completely copying it wouldn't work, though, because the sectors can have B < A when it crosses over 0. My idea was to initially have curr_in_range equal to the number of sectors that cross over 0 (instead of just it at 0 like we did in the above algorithm). Then, we could treat every sector as a "sector start event" and a "sector end event", and do the same process that we did.
However, after extensive analysis, I found why this approach doesn't work. This approach won't work because it overcounts some of the intersections, as sometimes two sectors can intersect in 2 places. This is where I'm stuck.

^^ Our sweep-line algorithm will count 2 distinct pairs that intersect, when there is actually only 1.
But besides this overcounting, I found that this current algorithm isn't doing a single other thing wrong. I coded a O(N^2) brute-force algorithm and tabulated all the distinct pairs that it found, and also tabulated the distinct pairs found for the current algorithm. For every randomly-generated test case, these two tables were the same. In other words, our current algorithm is correctly detecting every intersection there is to be detected, but it just happens to overcount some of them.
So, sorry for a really long post, but my final question is:
Can someone come up with an algorithm that solves this problem? Is my thought process close to a solution or completely off?

This is solvable in $O(n \log n)$ time, too, by considering the complement of the intervals that wrap around and using a suitable data structure.
There are two types of intervals that can appear on a cycle:

Intervals that do not wrap around: e.g., $[0.3,0.5]$ does not wrap around.  In general, this includes all intervals of the form $[a,b]$ with $0\le a \le b \le 1$.

Intervals that wrap around: e.g., $[0.8,0.1]$ wraps around; it is equivalent to $[0.8,1.1]$ or $[0.8,1] \cup [0,0.1]$.  In general, this includes all intervals of the form $[b,a]$ with $0\le a < b \le 1$; each such interval is equivalent to $[b,1] \cup [0,a]$.

Let $A$ denote the set of intervals that do not wrap around, and $B$ the set of intervals that do wrap around.  Also, let $\overline{B}$ denote the complements of the intervals in $B$, i.e., $\overline{B} = \{\overline{b} \mid b \in B\}$.  For instance, the interval $[0.8,0.1]$ wraps around; its complement is $(0.1,0.8)$, which does not wrap around. It is easier to think about intervals that do not wrap around, and this decomposition  will help us to deal only with intervals that do not wrap around.
Now, we will separately count the number of overlaps between (1) an interval in $A$ and an interval in $A$;
(2) an interval in $A$ and an interval in $B$;
(3) an interval in $B$ and an interval in $A$; and
(4) an interval in $B$ and an interval in $B$.
(1) can be counted with your sweepline algorithm, as we don't need to deal with wraparound.  (4) can also be counted in the same way, as two intervals overlap iff their complements overlap.  I will show below how to count (2); case (3) will then follow by symmetry.  This covers all the cases, so it suffices to count up these four cases and sum them up.
Note that intervals $a \in A, b\in B$ overlap iff $a$ is not a subset of $\overline{b}$.  So, it suffices to count the number of pairs $a \in A, \overline{b}\in \overline{B}$ where $a$ is a subset of $\overline{b}$; then you can subtract that from $|A| \cdot |B|$.
To do that, you can use the data structure in Data structure for interval subset queries.  Store all the intervals $\overline{B}$ in the data structure.  Then, for each $a \in A$, count the number of intervals in $\overline{B}$ that $a$ is a subset of.  This can be done in $O(\log n)$ time per query interval $a$, for a total time of $O(n \log n)$.
Therefore, you can count each of the four cases in $O(n \log n)$ time, and thus compute the overall sum in $O(n \log n)$ time as well.  I think.  I encourage you to check my reasoning to make sure I haven't made any mistakes.


How a program is copied to RAM from harddisk I know that for executing a program, it should be copied to RAM. But the problem is whole of it may not be copied always.

Since the size of the RAM is limited, there is mechanism called virtual memory. If the addressed thing is not in memory, a page fault occurs and the data is copied to the RAM. My question is who keeps track of which data is in the RAM and not in the RAM?

The operating system (with help from the CPU) keeps a page table, which is a mapping of each virtual page for to the physical page it is mapped to.  The page table also includes a bit for whether a particular page is currently mapped.  For every load and store instruction the hardware walks the page table (or at least a cached portion of it.)  If the virtual page is currently mapped to a physical page, the hardware figures this out and returns the right data.

If the virtual page is currently unmapped then the operating system receives an interrupt.  At this point it looks into the memory map for the process.  This is a list of ranges of virtual memory, the permissions that should be applied to that range, and the file (if any) on disk that stores the data from that range when it is not in RAM.  Typically for the main executable there will be a text segment, data segment and sometimes a read-only data segment (for constants), as well as a bss (zero initialized data) segment, a stack, and the heap managed by malloc.  There may be (usually are) additional text and data segments for each shared object (shared library) that the program needs to load.

You can use mmap() to tell a Posix operating system to create a new region in the memory map, the permissions for that region, and which file to use to back that region.  On Linux, for an existing process you can get a listing of its currently mapped regions using the pmap command.


Temporal logic - mixing AF and AG in CTL formula Let's look at example AF(φ1 -> AG(φ2)).

Does it mean that:

In all paths it eventually happens that if φ1 was satisfied, φ2 is satisfied all along the path (so it basically means φ2 is satisfied in all states in all paths)

or

In all paths it eventually happens that if φ1 was satisfied, φ2 is satisfied starting when the φ1 satisfaction started

or

Something else?

If 1, then isn't it equivalent to AF(φ1) -> AG(φ2)?

If 2, will the G start at the current or at the next iteration?

For example if φ1=p , φ2=q, are both A and B in the language, or just A?

A. q-p-q-pq-q-q-q-q-q...

B. q-p-q-p-q-q-q-q-q...

Does it mean that: 1. or 2. or 3.?

Your second interpretation is correct: $\varphi_1 \rightarrow AG(\varphi_2)$ is a CTL state formula, and to check whether it is satisfied by a state $s$, the path formula $G(\varphi_2)$ is evaluated relatively to the paths starting in s.

Therefore, a state $s$ satisfies your formula $AF(\varphi_1 \rightarrow AG(\varphi_2))$ iff all paths starting at $s$ eventually reach a state $s'$, such that if $\varphi_1$ holds in $s'$, then all paths starting at $s'$ satisfy that all states on this path satisfy $\varphi_2$.

  If 2, will the G start at the current or at the next iteration?

G starts at the current state/iteration. A path satisfies $G\varphi$ iff all states on this path satisfy $\varphi$, including the current state.

  For example if φ1=p , φ2=q, are both A and B in the language, or just A?

I am not sure what you mean by the "language" of a CTL formula. For LTL it makes sense to define the language of a formula, containing the words / label sequences that satisfy the formula. CTL does not reason about linear sequences, but about branching time, so usually for a CTL formula we are interested in the labeled transition systems whose initial states satisfy the formula (alternatively, you can unroll the transition systems and use CTL formulas to reason about languages of  infinite, finitely-branching, labeled trees). I assume you meant "language" in this sense, i.e. A and B are meant as sketches of transitions systems or their unrolling, with the left-most state as the initial state.

Then A and B both satisfy the formula: Both have an initial state that is not labeled with $\varphi_1 = p$. Hence both initial states satisfy the CTL state formula $\varphi_1 \rightarrow AG(\varphi_2)$. Therefore, it is true that all paths starting from their initial states eventually (in this case immediately) reach a state that satisfies $\varphi_1 \rightarrow AG(\varphi_2)$. Thus, the initial states satisfy $AF(\varphi_1 \rightarrow AG(\varphi_2))$.

References: Baier, Christel, and Joost-Pieter Katoen. Principles of model checking. MIT press, 2008.


Search algorithm that returns the lowest cost path to one, of many possible goal nodes? I am working on a problem where I have a set of goal nodes of which some, all, or none of will appear in a search tree.

Is there a search algorithm which returns the lowest cost path to one goal node, when there are potentially many different goal nodes present in a tree, or failure?

This can obviously be solved by iterating through the set of goal nodes and applying a search algorithm on each of the goals and then comparing the paths to find the lowest cost path, but I would like know if there is a more elegant solution.

Thanks

Yes, any of the standard search algorithms will do that.

You seem to be under the misapprehension that search algorithms stop "when they reach node $x$." They don't: they stop when they reach a node with any property you tell them to use. That property could be "node $x$", or "any node in $x_1, \dots, x_k$", or "any node with score more than $10$" or any other condition you choose.


Regular expression for words in a language where each letter appears at least once What is a regular expression or finite automaton that will accept words in the alphabet $\{a,b,c \}$ where each letter appears at least once?

Acceptable words:  $ abc, cba, cbcbcba, abbbcaabb$

Unacceptable words: $aab, babababababa, bbbbbaaaaa$

I would be interested in seeing both the regex and the automaton. Then I can place it into regexper.com

In Regular expression to show that all strings contain each symbol atleast once we find the regex

$$ (a+b+c)^*a(a+b+c)^*b(a+b+c)^*c $$

The word $cba$ does not fit, and the answer raises questions about the complexity or size.
For kicks, I draw the automaton [1].

COMMENT It's not clear to me at all this is a duplicate to the linked question.  They talk in general about deciding if

$$ \qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \} $$

is a regular language.  None of the answers address my specific case in question.  Looking at notes, my guess the alphabet is $\Sigma = \{ a,b,c\}$ and $\Sigma^\ast$ is the free monoid.  It's unclear to me what choice of $L$ returns the $L'$ I am looking for.

Or if anyone can show me how this is an intersection, complement or other regular language operation please let me know.

A DFA for your language is:

The name of the states are self descriptive.

Following comments from D.W., here is a way to compute such an automaton. It is a bit tedious and error prone by hand, but easy to do by computer with the proper algorithms. These ideas are to be found in this reference question.

You define 3 languages on the alphabet $\Sigma^*=\{a,b,c\}$, $L_a$, $L_b$, and $L_c$, such that each contains all string that have at least one occurrence of the subscript symbol.

For example $L_a=\{w\mid |w|_a\geq 1\}$

The language you want is $L_a\cap L_b \cap L_c$.

The corresponding finite automata are much easier to define. Then you only have to apply twice the standard crossproduct construction to get the automaton for the intersection.

The advantage of using standard construction is that it spares you the need to prove your result correct (if done by a computer ... I would not trust a human being).

A regular expression is:

$$\begin{align}   (\;\;\;
    (aa^*b & +bb^*a)(a+b)^*c \\
   +(bb^*c & +cc^*b)(b+c)^*a \\
   +(cc^*a & +aa^*c)(c+a)^*b\;\;\;) \;\;  (a+b+c)^*
\end{align}$$

You can more or less read it from the DFA. Otherwise, just use the standard algorithms, and good luck.


In a Binary Tree, can two nodes have the same value? In a Binary Tree, can two nodes have the same value? For example:

     3
    / \
   4   4
  / \
 1   2

They are two different nodes, but they have the same value. Here is code:

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

const r = new TreeNode(3);
r.left = new TreeNode(4);
r.right = new TreeNode(4);
r.left.left = new TreeNode(1);

If you say "binary tree", my answer is " yes", since binary tree to me only says: A tree of nodes that only have at most 3 edges, of which two (binary) are pointing in the same direction (to tree leafs).

If you mean a "binary search tree", my answer is "no", since a search tree does not have any advantage in allowing duplicates, since SEARCHING for ONE value in a BST can only result in ONE value, not in two or more. Since BST search is a deterministic algorithm, one of the two mentioned duplicates will never be found and hence is totally useless. Inserting a duplicate in a BST must be skipped since its position in tree is already occupied.


Data structure for A*'s "open" set I'm looking at Wikipedia's pseudocode implementation of A* and found myself wondering about what they call openSet. That is, the neighbours we've seen, but not yet analyzed.

The first part of the outer loop reads:

 current := the node in openSet having the lowest fScore[] value

And this makes sense to me, as I intuitively think of openSet as a heap. So we just pop() and get whatever's most interesting to look at next.

But when looping through the neighbours in the inner loop, this happens:

 if neighbor not in openSet // Discover a new node
                openSet.Add(neighbor)

And obviously, that's not going to go well with a heap. So what I'm wondering is this:

How is this contains() check meant to be carried out? Am I supposed to use something like an AVL tree to get logarithmic performance on both lookup and pop?

Would it make sense to keep a separate hashset to keep track?

Or can I altogether ignore this step?

What would be most effecient?

I think I never heard the term "Open Set" as we usually call it "OPEN list" (and by convention we use upper-case letters). I mention this to highlight the fact that this structure is closer to a list than a set indeed ---thought sets might be used as well, see below.

Anyway, your understanding of the purpose of the OPEN list is perfect. It should contain all nodes generated that are awaiting for expansion, in contraposition to the so-called CLOSED list that contains all nodes that have been already expanded.

There are many different implementations of the OPEN list. For a good review of different ways to implement it, see Chapter 3 of Stefan Edelkamp, Stefan Schroedl Heuristic Search: Theory and Applications, Morgan Kaufmann 2011. In the following I'm just describing three typical alternatives:

Plain open list

The first alternative consists simply of using a list which sorts nodes in ascending order of their $f$-value. Extracting nodes from the list is done in $O(1)$ as it just suffices to take the first item from the list. Inserting is a little bit more difficult. The best would consist of creating a small OPEN list with the descendants of a node that has just been expanded and to sort it in ascending order of their $f$-values. Next, merge this sort list with the global OPEN list. The operation has a cost which is logarithmic in the size of the global OPEN list, but be aware that its size grows exponentially.

Bucketed open list

If the $f$-values of all nodes are known to be discrete and also to be bounded by a constant $B$, then create an array with $(B+1)$ locations, each one pointing to one different list. This ensures that inserting nodes in the OPEN list takes only $O(1)$: given a node with an $f$-value equal to $x$, just add it to the tail of the list pointed to by location OPEN[x]. Extracting is a little bit more difficult, but still very easy. You have to keep track of the lower non-empty index $x$, min x. When popping a node return the first node in the list pointed to by OPEN[min x]. Clearly, this requires some maintanenance: first, when removing all nodes with an $f$-value equal to min x, it is necessary to update this lower bound; secondly, if a node with an $f$-value strictly less than the current min x is inserted, min x has to be updated as well.

Using sets

A$^*$ might additionally require to perform searches in the OPEN list. Strictly speaking, this is not required and the only purpose for doing it is to save some memory ---which anyway will grow exponentially. Note please that this will not avoid redundant expansions, as the CLOSED list already serves specifically to that purpose (in a nutshell: before the expansion of any node verify it is not in the CLOSED list; if so, skip the current expansion; otherwise, expand it and insert it into CLOSED) so I do not think it is really common practice to avoid the insertion of nodes in OPEN that are already in OPEN.

Anyway, if you are interested in saving some additional memory at the expense of investing some additional CPU running time, create a set with the current contents of the OPEN list (implemented in either way) and use it only for performing searches. Yeap, you might be thinking that you are then using twice the memory required by A$^*$ but be aware that the memory consumption of this algorithm is exponential in the depth of the paths generated, so that multiplying the memory usage by a low constant (such as two) will not prevent your algorithm from finding solutions that otherwise could have been found.

Hope this helps,


Erasing $\epsilon$ production from CFG I would like to delete the $\epsilon$-production from the context free grammar with the following rules P:

$$S \rightarrow ASB , BSA, \epsilon$$
$$A \rightarrow aS$$
$$B \rightarrow bB, b$$

Now we were only given this algorithm for that task:

collect all variables from which the empty word is derivable.

-> which in this case is only S

Add to the new rules P' every rule $A \rightarrow \alpha'$, with $\alpha \neq \epsilon$, for which P had a rule $A \rightarrow \alpha$, so that $\alpha'$ results from $\alpha$ by erasing all variables that were collected in step 1.

In this case I would erase $S \rightarrow \epsilon$ and since P included $A \rightarrow aS$ I would add $A \rightarrow a$ to P', giving me:

$$S \rightarrow ASB , BSA$$
$$A \rightarrow a$$
$$B \rightarrow bB, b$$

The grammar with these rules does not, however yield the same language as P, in fact the S never disappears. Can anybody please tell me what I'm doing wrong and how to do it correctly?

You cannot erase the $ϵ$-production from this grammar and keep the same
language. The reason is that since you have the production $S\to ϵ$, the
language contains $ϵ$. And the only way a CF language can contain $ϵ$ is with
an $ϵ$-production.


Is there an structure that allows for a flat representation of trees with constant access to any element? One can, for example, represent 2d arrays such as:

[[1,2],[3,4],[4,5]]

as flat arrays:

[1,2,3,4,5,6]

as long as he transforms the indices before accessing:

index(x,y) = x + y*2 // because internal width=2

This is often faster. My question is: is it possible to use a similar approach of representing an structure as a flat array, for, instead of n-dimensional tables, free-form trees such as:

[[1,2,3],4,[5,[6,7]],8]

Well, it depends a bit on the operations. You cannot do anything reasonable if you want to realize you data structure inside an $n$-elementary array. The 2d array works, since there is a bijection between the 2d array entries and the 1d array entries. There is also such a bijection for any fixed tree, but I think this is not what you are looking for.

Notice that your tree decoding [[1,2,3],4,[5,[6,7]],8] also uses more structure than a normal 1d array. So if you ask for data structures of size $O(n)$ with $O(1)$ operations than you can actually do something.

One idea is to use a array where you store the DFS-tour (sometimes called Euler tour) of your tree, and the information about the time when you discover and when you finished a vertex in the DFS search. This can be stored inside an array of size $4n$ plus another $n$ for the values at the nodes, and it allows you to navigate through the tree using $O(1)$ operations per step.

With more involved data structures you can also answer level ancestor queries (what is the $i$-th vertex about vertex $x$?) or lowest common ancestor queries in constant time with a data structure of size $O(n)$. If you want to know more about these two data structures, look up the references in wikipedia.


Hindley-Milner type inference for language with implicit type casting I've only implemented the HM algorithm on a small academic language with a few primitive types and functions. In that case, the unification algorithm would return a type error if two different primitive types were given. For example, if statements unify their condition with primitive type bool, producing the following results:

if (true) ... // type safe
if ("5") // type error, cannot unify string and bool

I've now been tasked to implement a type inference algorithm on a language that allows type casting on primitive types. For example, one cast is int -> bool such that if(5) ... is now a valid expression.

The problem is, I can't figure out how to adapt the unify algorithm. Specifically, I'm stuck on dealing with the one directional nature of type casts, e.g. int -> bool is defined, but bool -> int is not. The unify algorithm has no notion of direction. Unifying type a and type b is the same as unifying type b and type a. So in the case of the if statement, if I say that unify int with bool is allowed, then unify bool and int must also be allowed, and suddenly the statement true + false is type safe.

I've searched for details of existing type systems that do this, but unfortunately I've only found resources that either show a basic HM inference algorithm similar to the first one I implemented, or are completely off topic.

Hindley-Milnor type inference doesn't support implicit type casting, so you can't fix that easily.  You'd need a fundamentally different algorithm for type inference, and I'm not sure whether such a thing exists.  I think there are ways to handle type inference with implicit type casts if you don't care about supporting polymorphic types, but as far as I know, the combination of polymorphic types, type inference, recursion, and implicit type casts is hard to handle simultaneously.

In contrast, it's straightforward to extend HM type inference to handle explicit type casting.


Finite state automaton's reaction to simultaneous events What does happen if two events simultaneously occur at a particular state of a finite state automaton (FSA)?

For example, assume that an FSA's event table at its state $s$ is as follows:

$\delta(s,e_1)=s_1$ and $\delta(s,e_2)=s_2$. What will be the system's next state if both $e_1$ and $e_2$ occur exactly at the same time?

Finite-state automata take a sequence of events as input. There is a single event in the input sequence at any given position. What if there are two different values at position 3 in the sequence $ababcaccab$? There aren't, that's just how the mathematical object is constructed.

The input to a FSA is not necessarily a sequence of events that happen one after the other. For example, when an FSA is used for string parsing, there's no concept of time. But let's assume that you're using an FSA as part of a model of something that reacts to events over time. Note that this is no longer just about automata theory, but also about what you're modeling. What if you want to express that two events are simultaneous? Then you'll need to use a more sophisticated mathematical tool.

The core of the mathematical tool can still be a finite state automata, but instead of taking a sequence of events as input, you'd take a sequence of sets of events. The thing is, in practice, this is rarely useful, because in practice, things do not happen simultaneously. At most, they happen simultaneously up to measurement error. Given that measurement error is, by definition, variable, the same physical process may or may not be observed as simultaneous if you try it again several times. Therefore it is not useful to consider simultaneity in the model: it brings extra complexity to the math without providing any extra insights regarding the physical process.

Simultaneity is a useful concept regarding events that have a duration: event A may end after event B starts, in which case events A and B overlap. But if you're interested in that, then you can't model A and B as single events, you need to distinguish separate events “A starts, B starts, A ends, B ends”. These start/end events happen sequentially.

There is one world where things do happen sequentially, which is the world of discrete time. Discrete time is used to model digital circuits (because it corresponds to how they work). Two events may happen during the same clock cycle; that's the definition of simultaneous here. A digital circuit is modeled as a finite state automaton in a straightforward way, but then each element in the input sequence is not an individual event such as “input 42 switches from 0 to 1”, but a collective event made of the state of all the states of all the inputs.


Why is a subset of a undecidable language decidable? I have problems with the understanding why a subset of a undecidable language is decidable. We've proved in the lecture that $HALT$$_T$$_M$$=${$<M,w>$|M is a TM and M halts on input w} is undecidable. Can someone give an example of a subset from $HALT$$_T$$_M$ and explain why it is decidable? Is $\Sigma^*$ a valid subset of $HALT$$_T$$_M$?

An undecidable language is necessarily infinite. A finite subset of it is always trivially decidable.


NFA to DFA convertion explanation I've converted this NFA to a DFA and I get a similar soultion automata but I'm not sure if I really understand everything.

Please correct me if I'm explaining it wrong, I would love some feedback.

From the state 0 we only have the set {0} since there doesn't exist any ε-transition.
After that we have to input "a" to move to state 1 and here I've got a question. Does it include the 0 also since "a" can either take you to state 1 but also to state 0 since it loops?

Continuing we want to move to state 2 via "a" input. Why does it include the "0"? Is it because you have to consider all the inputs from each set in the state 1? Like, if you input "a" at 0 you loop but you can also go to state 1. From 1 if you input "a" you move forward to state 2. Which gives us the set {0,1,2}.

If this is correct, then the procedure for state 3 should be the same, right?
Also, at the third state {0,1,2,3} he can't just loop "b" since the other states can't "handle" the input so you have to create a new state containing the set {0,3} which can handle the "b" input?

Sorry if this is a bit long, I just want to understand what is going on really.

You've basically got it. The reason why the a loops is because whichever state you were in, you can end up in any one of them (if you were in 0, maybe you took the looping a and ended up in 0).

The way I think of it is, with the NFA, you are maintaining a list of states you are in at any one point. When you convert to DFA, we have a state for any set of states we can be in (the power set of all the states in the NFA). We can tidy this up if we want (removing inaccessible nodes etc.) but that is the basic principle.

So with yours, you state in state 0. Then we read an a and at this stage we could be in {0, 1}. Then we read in another a and now we could have done:

Been in state 0 and stayed in state 0
Been in state 0 and advanced to state 1
Been in state 1 and advanced to state 2

Therefore we could now be in any of {0, 1, 2} so that's the node we go to in the DFA.


Finding solutions to $n m\equiv x \mod n$ Given a modulus $n\in\mathbb{N}$ and another natural number $0<x<n$, what's an efficient algorithm to enumerate all pairs of natural numbers $(a,b)\in\mathbb{N}^2$ such that both $a$ and $b$ are less than $n$ and $$ab\equiv x \mod n\text?$$

Let's solve the problem for a specific $a$. Observe that
$ab \equiv x \pmod{n}$ if and only if there exists a $m \in \mathbb{Z}$ such that

$\qquad ab + mn = x$

By the Bezout theorem, the above has solutions if and only if $x \mid (a, n)$ (the "if" arrow is the theorem, the "only if" arrow is trivial). One of those solutions can be found by the Extended Euclid algorithm, and all the others can be obtained observing that if $(b, m)$ is a solution, then

$\qquad \left( b + \frac{n}{(a, n)}, m + \frac{a}{(a, n)} \right) $

is also a solution. Repeating the above process for all $a \in \mathbb{Z}/n\mathbb{Z}$ yields all the pairs you are looking for. While it's rather naive, I don't think you can get much better than that if you're looking for all solutions.


Min-cut in a network with zero flow from source to sink The max-flow min-cut theorem guarantees that the min-cut of a directed network equals the maximum flow. And we can compute $S$ and $T$, are disjoint subsets containing source node and sink node respectively from the residual graph.

What will be $S$ and $T$ if the max-flow from source to sink is 0, that is, there is no directed path from $s$ to $t$? Is $S$ going to be the singleton set {s} or its the empty set $\phi$ and $T$ be the vertex set $V$?

No, your gut feeling is not correct.

Consider the following flow network with source $s$ and sink $t$, where the capacity of every edge is 1. The max-flow from source to sink is 0. The s-t cut $(\{s,A\}, \{B,t\})$ is a minimum cut since the only connecting edge $(B, A)$ goes from sink side to source side.

$$ s \longrightarrow A \longleftarrow B \longrightarrow t$$

You could learn several lessons from this simple problem.  One is that source and sink are symmetric in some strong sense. It looks like your gut feeling does not respect this symmetry. Another lesson is that a few simple examples should be included in your repository. Always try constructing some simple or extreme examples when you want to check a proposition of unknown truth value.


Interpret bits as a signed integer in 2s complement Imagine you load this data as a 4-byte word into a register R. What is the value in R on a big endian machine and what is it on a little endian machine if you interpret the bits as a signed integer encoded in 2s complement

On a big endian machine the register R would be something like this

not considering the last sentence, interpret the bits as a signed integer encoded in 2s complement, which I don't understand completely.

Should I convert all bits, 0s to 1s and 1s to 0s and then sum 1 to all the string or to sum 1 to each byte in the string?

Thanks.

To convert a 4-byte = 32-bit word to its negative you apply the two's complement operator.  The operator is, as you said, invert all the bits, then add 1 to the word.

You can tell a 4-byte = 32-bit word represents a positive value if its most significant bit (the one all the way on the left) is "0".  If the most significant bit is a "1" then the 32-bit word represents a negative value.  Thus your example big-endian register, 01001101101101101111001111010111 must represent a positive number.

I assume you know how to convert a positive binary number to its decimal or hexadecimal equivalent.  The hexadecimal equivalent of 01001101101101101111001111010111, for example, is 0x4db6f3d7.

If, on the other hand the leading bit had been a "1", as in, (just making a number up): 11001101101101101111001111010111 that represents a negative number.  The negative of what positive number?  The positive number that you will get if you apply the two's complement operator.  Flip the bits and add 1.  So the negative of
11001101101101101111001111010111
must be
00110010010010010000110000101000
+                              1 =
00110010010010010000110000101001,
which is hexadecimal 0x32490c29
so
11001101101101101111001111010111 must be -0x32490c29.


Does #$P$-Completeness imply approximation hardness? Let $\Pi$ be some counting problem which is known to be #$P$-Complete.

Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?

No. Counting independent sets in graph is #P-hard, even for 4-regular graphs but Dror Weitz gave a PTAS for counting independent sets of $d$-regular graphs for any $d\leq5$ [3]. (In the model he writes about, counting independent sets corresponds to taking $\lambda=1$.)

Computing the permanent of a 0-1 matrix is also #P-hard (this is in Valiant's original #P paper [2]) but, relaxing your requirement a little, there's an FPRAS due to Jerrum and Sinclair [1]. This corresponds to counting perfect matchings in bipartite graphs.

References

[1] Mark Jerrum and Alistair Sinclair, "Approximating the permanent." SIAM Journal on Computing, 18(6):1149–1178, 1989. (PDF)

[2] Leslie Valiant, "The complexity of computing the permanent." Theoretical Computer Science, 8:189–201, 1979. (PDF)

[3] Dror Weitz, "Counting independent sets up to the tree threshold." STOC 2006. (Unpublished full version: PDF.)


Given a directed acyclic graph (DAG) - what can you say about each case? Suppose $G$ is a DAG with $n$ vertices, and $v$ is a vertex of $G$. What can we say regarding $v$ if the following holds:

A. In all topological sorts, $v$ is at the end of the list.

So my initial answer is that $v$ is the "sink" vertex, but in some case its not always correct, can't seem to find a feature that cant be said on $v$?

B. In all topological sorts, $v$ is at the top of the list.

So this one is the opposite which is the source vertex and has arrows coming out of him and no one points to him.

A. Let's prove that $v$ will be a vertex which can be reached by every node (it is the mother vertex of the transpose of the graph) by contradiction. Suppose that there is a node $u$ such that $v$ is unreachable by it. Consider every node in the DAG reachable by $u$. There must be at least one node in this set that has no leaving edges. (Otherwise you could start from $u$ and always follow a leaving edge from the current node so after at most $|V| - 1$ steps you would visit an already visited node. But this implies a cycle which isn't allowd in a DAG.) So no other node is reachable by $u$ and $u$ could be last in a topological cue instead of $v$ and we reached a contradiction. As a result $v$ is reachable by every node. This is equivalent with (A)'s statement as a node being reachable by every node can appear only last in any topological cue.

Also $v$ is a sink because if it wasn't there would be at least one edge leaving it so it couldn't be at the end of any topological cue. (A)'s statement implies that $v$ is a sink but the reverse doesn't always hold.

B. $v$ is a mother vertex (every node is reachable by it). The proof is similar.


Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true Given $S$ of positive integers $>$ $1$ is there some combination with even $SUM$ > $2$ that is NOT the sum of two primes?
$SUM$ = 10
$S$ = $[4,6]$
$No$,
Sum of Two Primes
$5 + 5 = 10$.
Combination $4+6=10$
It has an $O(1)$ algorithm if Goldbach is True (always output $NO$). Otherwise, it would seem to be NP-complete because it would require solving Subset-Sum.
Question
Will a many-one-reduction from $Subset-sum$ work for this decision problem in poly-time?

If there is a finite number of exceptions to the Goldbach conjecture then it is still solvable in linear time.
Note that there is a non-zero probability that the Goldbach conjecture is false. Heuristically, the probability for an infinite number of exceptions is zero.


Simplifying a boolean expression I need to prove:

XY + ~XZ + YZ = XY + ~XZ

I cannot think how to do this.

I have tried factorising, but I just don't know of any rule that removes one of the terms like above.

I start with the LHS, naturally:

All I can do is get to:

Y(X+Z) + ~XZ

Here is an ugly solution, found with the Karnaugh table and the equation : A = A.B + A./B

XY + /XZ + YZ

= X.Y.Z + X.Y./Z + /X.Y.Z + /X./Y.Z + X.Y.Z + /X.Y.Z

(removing two redundant terms)

= X.Y.Z + X.Y./Z + /X./Y.Z + /X.Y.Z

= XY + /X.Z


solving recurrence by substitution, calculations doesnt add up I have this recurrence $p(n) = 2p(n-2) + n$, and I have guessed that the solution is $O(n^2)$, however, when I do the following calculations, I cannot get the inequality to hold

$p(n-2) \leq c(n-2)^2$ (induction hypothesis)

$2c(n-2)^2 + n \leq cn^2$ (substitution)

$cn^2-8c + n \leq cn^2$

Can anyone see where I go wrong? I also tried for even larger $O(n^x)$ but it still doesn't work.

Using the so-called substitution method, we get (for even $n$)
$$
\begin{align*}
p(n) &= 2p(n-2) + n \\ &= 4p(n-4) + 2(n-2) + n \\ &= 8p(n-6) + 4(n-4) + 2(n-2) +n \\ &= \cdots \\ &= 2^{n/2} p(0) + 2^{n/2-1} 2 + 2^{n/2-2} 4 + \cdots + 2^0 n.
\end{align*}
$$
Let's assume for simplicity that $p(0) = 0$. We can write
$$
p(n) = \sum_{k=0}^{n/2-1} 2^k (n-2k) = 2^{n/2+2} - n - 4 = \Theta(2^{n/2}).
$$
(Solution courtesy of Wolfram alpha.)


Isn't this language in $\mathrm{P}^{\mathrm{NP}}$? For an undirected graph $G$, let us denote $\gamma(G)$ the chromatic number of $G$. Let us define for positive integer $n$, the language
$$
L_n = \{\langle G\rangle : \gamma(G) = n\}.
$$
This is the language of undirected graphs with chromatic number $n$.
I think $L_n \in \mathrm{P}^{\mathrm{NP}}$, for any $n$.

My argument is the following. We can look at the language,
$$
\mathrm{CHROMNUM} = \{\langle G, k\rangle : \gamma(G) \leq k\}.
$$
It is clear that $\mathrm{CHROMNUM} \in \mathrm{NP}$, since we can verify an instance just by displaying an at most $k$-coloring of $G$.

Thus, consider oracle Turing machine $M^{\mathrm{CHROMNUM}}_n$, which on input $G$, simply checks that $\langle G, n \rangle \in
\mathrm{CHROMNUM}$ and that $\langle G, k \rangle \not \in \mathrm{CHROMNUM}$ for all $k \leq n$.

I've just read about $\mathrm{P}^{\mathrm{NP}}$, so I wanted to be sure that this kind of argument is correct.

Yes, your argument is correct.

$\textbf{P}^\textbf{NP}$ is the class of problems which are Cook-reducible (i.e., polynomial-time Turing-reducible) to $\textbf{NP}$. A Turing reduction to $\textbf{NP}$ is simply a reduction with oracle access to a problem in $\textbf{NP}$, in this case the problem $\text{CHROMNUM}$.

In fact, using your reasoning and the fact that $\langle G, k \rangle \not\in \text{CHROMNUM} \implies \langle G, k' \rangle \not\in \text{CHROMNUM}$ for all $k' \le k$, you can prove that you only need two oracle queries (independent of $n$). That is, your reduction resumes to checking the following:
$$\langle G, n \rangle \in \text{CHROMNUM} \land \langle G, n - 1 \rangle \not\in \text{CHROMNUM}$$
This means you only need one $\textbf{NP}$ query and one $\textbf{coNP}$ query (since checking if something is not in an $\textbf{NP}$ language is in $\textbf{coNP}$). As it turns out, there is a class of problems which are characterized by having the same type of reduction, the difference polynomial time class $\textbf{D}^\textbf{P}$, and which, incidentally, coincides with the second level of the Boolean hierarchy.


Segmentation and paging I am given a system with a segmented paging architecture. Both physical and virtual address spaces contain $2^{16}$ bytes each.  The virtual address space is divided in $8$ equal size segments. The page table consist of $2$ byte page table entries.

Question 1:

What is the minimum page size in bytes so that page table for a segment requires at most 1 page to store it?

My interpretation:

There are $2^{16}$ virtual addresses. These are evenly divided between $8$ segments so each segment is $\frac{2^{16}}{2^3}=2^{13}$ bytes.

Now each segments will be divided into pages. Each page will be $2^n$ bytes. So there are $2^{13-n}$ pages (and page table entries) per segment. A page table entry is $2$ bytes long and page size is $2^n$. So $2^{n+1}$.

$2^{13-n} = 2^{n+1}$ gives $n = 6$.  But the answer should be $n = 7$.

I know I made a mistake in page table entry as I didn't get the page table entry concept properly. Is that a f (f+d = memory address)? I am not getting page table entry. Please explain to me this concept.

Question 2:

Assume that page size is $512$ bytes. Each page table entry contains (besides other information) $1$ valid bit, $3$ bits for page protection and $1$ dirty bit. How many bits are available in a page table entry for storing the aging information for the page?

My way of thinking about the answer here:

$16$ bits for physical memory. Page size is $512$ bytes means $9$ bits required. That's $16-9= 7$ bits for a frame.

Now I'm stuck.

Answer to question 1:
If $2^n$ is the size of the page then there are $2^{13-n}$ pages.
We know that each page table entry is 2 bytes.
So size of the page table will be $2\times 2^{13-n}$ bytes because $2^{13-n}$ is the number of pages and each page has an entry in the page table.
They have given that page table takes at most one page to store.
So, $2\times 2^{13-n}=2^n \Rightarrow n=7$.

Answer to question 2:
Each page table entry is two bytes which is $16$ bits so the remaining bits other than the valid bits (protection bits and the dirty bit) are $16-5=11$ bits.
Page size is $512=2^9$ bytes.
Physical address space $2^{16}$ bytes.
Number of bits required to represent a page is $16-9=7$ bits.
So, the available bits to store the aging information is $11-7=4$ bits.


Counting words that satisfy SAT-like constraints with BDDs I have the following #P-complete problem:

Given an alphabet $\Sigma$ and a matrix $M$ where each entry can be a symbol from $\Sigma$ or the wildcard symbol $*$, find the number of strings $s$ with the property that there exists $i$ such that for all $j$, $M_{i,j} \neq *$ implies $s_j = M_{i,j}$.

Example:
If $\Sigma = \{a,b,c\}$ and $M$ =
$$\left(\begin{matrix}
a&*&b \\
*&c&*
\end{matrix} \right)$$
then there are three satisfying strings: $aab,abb,acb$.

I was told this can be solved using BDDs, somehow, such that a lot of caching is possible. How does that work? Also, what are other algorithms for this?

Proof of #P-completeness:
We reduce from #UNSAT, the problem of counting the number of unsatisfying assignments for a boolean formula. Given a formula $\varphi$ with $n$ variables and $m$ clauses, make an $m$ by $n$ matrix $M$ over the alphabet $\Sigma = \{0,1\}$ such that
$$M_{i,j} = \begin{cases}
1\text{ if the $j^{th}$ literal is unnegated in the $i^{th}$ clause,} \\
0\text{ if the $j^{th}$ literal is negated in the $i^{th}$ clause,} \\
*\text{ otherwise.}
\end{cases}
$$
Then the number of strings with the above property equals the number of unsatisfying assignments for $\varphi$.

Yes, you can use a BDD to solve this, but BDD's aren't magic: they don't magically allow you to solve a #P-complete problem efficiently.  You can use BDD's to solve this, but the resulting solution might be highly inefficient.

How do you use BDD's to solve this?  Broadly, you build a BDD that represents all strings that satisfy the property, and then you count how many strings are accepted by this BDD.

To learn how to build a BDD that accepts all strings that satisfy the property, I suggest that you study basic material on BDDs.  The key property that's relevant here is that given BDDs for the sets $S,S'$, it is easy to construct a BDD for the set $S \cup S'$.  So, you build a BDD for the set of strings that are accepted by each row of the matrix, and then you take their union to get a BDD for the union.  Beware that the resulting BDD could have exponential size.

Once you have a BDD, it's easy to count the number of strings accepted by a BDD.  It's an especially simple application of dynamic programming: for each node $n$ in the BDD, you count the number of paths from $n$ to some leaf.  These numbers can be filled in by visiting the nodes in bottom-up order, and using dynamic programming.

There's nothing fancy here.  Once you are familiar with BDD's, everything here should look bog-standard.  So, if this looks mysterious, I recommend you spend some quality time with a textbook that explains how BDD's work.

Other algorithms: you could also use any algorithm for #SAT.  There are off-the-shelf algorithms and tools for computing #SAT.  It's straightforward to translate your problem to an instance of #SAT, and then apply one of those tools.  See, e.g., https://cstheory.stackexchange.com/q/1295/5038, Is there a sometimes-efficient algorithm to solve #SAT?, https://cstheory.stackexchange.com/q/18135/5038.


What is meant by "give pattern of a regular expression" I have an alphabet $A = \{b,B\}$ and I'm asked to write down the pattern of the regular expression $(\epsilon|bb|b)(B|bb)(b|\epsilon|b)$. What does the question actually want me to do? I'm not sure. Does it want me to give the possible patterns that can be formed with $b$ and $B$? But then surely the question would not have been phrased the way it is.

I'm just confused about what I need to do here and what is expected of the answer. If anyone could give an example it would be very helpful.

Note: This is not the original question, I changed and simplified it.

A pattern (in the context of languages and automata) is a way of defining a set of strings. A string matches a pattern if it belongs in the set defined by that pattern. So, your regular expression is actually a pattern. The question, I think, would be to find the pattern given a set of strings!


Isomorphism of a DFA and the minimal DFA I have a DFA A, I minimize A and the minimized DFA obtained is M.
My question is if in general A and M are isomorphic?

No. If the result of minimizing was always isomorphic to the thing you started with, minimization would do nothing!

For a concrete example, consider any automaton with more than one state, which has every state accepting. This automaton accepts $\Sigma^*$ and is not isomorphic to the minimal automaton for that language, which has just one state.


Are co-semidecidable languages separated by decidable ones? Can I use principles of set theory in order to solve the following question?

  For every $A,B \in \mathsf{co\text{-}RE}$ with $A \cap B = \emptyset$, there is a separating language $C$ with $A \subseteq C$ and $B \cap C = \emptyset$ so that $C$ is recursive.

This is a classical exercise in computability.
Since $A,B\in coRE$, there exist TMs $M,N$ that recognize $\overline{A}$ and $\overline{B}$ respectively.

Consider the following TM $K$:
Given a word $w$, run in parallel $M$ and $N$ on $w$. That is, simulate $M$ for a single step, and then $N$ for a single step, and repeat.

If $M$ accepts at any point, reject.
If $N$ accepts at any point, accept.
(if both accept, reject, so we first check $M$ for acceptance).

Define $C=L(K)$.

If $A\cap B=\emptyset$, then $\overline{A}\cup\overline{B}=\Sigma^*$, so either $M$ or $N$ eventually accepts, so $K$ always halts. Thus, $C$ is decidable.

We claim that $C$ satisfies the requirements: if $x\in A$, then $M$ never accepts $x$, so $N$ accepts $x$, so $K$ accepts, so $x\in C$. Thus, $A\subseteq C$.

If, by way of contradiction, $x\in B\cap C$, then $K$ accepts $x$, which means $N$ accepts $x$, so $x\notin B$ - contradiction. So $B\cap C=\emptyset$.

We conclude that $C$ satisfies the requirements.


Is it proven that quantum computation is no better at solving NP complete problems than classical computation? Is it proven that quantum computation is no better at solving NP complete problems than classical computation or it's just believed?

It is suspected that NP-complete problems cannot be solved in quantum polynomial time (i.e., that they are not in BQP), but this hasn't been proved. We don't expect a proof in the near future, since this would imply that P is different from NP.


Kosaraju's algorithm's time complexity I've reading up on Kosaraju's algorithm to compute the strongly connected components of a directed graph and I found that

using an adjacency list representation gives a time complexity of $\Theta(V+E)$.
using an adjacency matrix representation gives a time complexity of $O(V^{2})$.

Why $\Theta$ in the first case and $O$ in the second case?

Any algorithm for computing strongly connected components must examine at least $\binom{|V|}{2}$ entries in the worst case (proof below). In particular, since Kosaraju's algorithm is correct, its (worst-case) complexity is $\Omega(|V|^2)$, and so also $\Theta(|V|^2)$. There is no particular reason why Wikipedia used big O for one and bit $\Theta$ for the reader – probably a different author.

Edit: One possible reason for using big O rather than big $\Theta$ is that sometimes the algorithm is lucky and runs faster. Whether this happens or not could depend on the particular implementation of DFS.

Suppose $A$ is an algorithm examining less than $\binom{|V|}{2}$ entries. We will show that the algorithm cannot always know what the strongly connected components are. Run the algorithm, and for each entry of the adjacency matrix queried by the algorithm, return $0$. When the argument terminates, there are more than $\binom{|V|}{2}$ off-diagonal entries not queried, and in particular there exist vertices $i \neq j$ so that neither the $(i,j)$ nor the $(j,i)$ entry are queried. We could complete the adjacency matrix in two different ways: the all zeroes matrix, or the one in which both these entires are $1$. In the former case, there are $n$ connected components, in the latter, only $n-1$.


I can not see why MSD radix sort is theoretically as efficient as LSD radix sort Here is the pseudocode for LSD radix sort from http://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf

   public static void lsd(String[] a)
   {
        int N = a.length;
        int W = a[0].length;
        for (int d = W-1; d >=0; d--)
        {
             int[] count = new int[R];
             for(int i = 0; i < N; i++)
                   count[a[i].charAt(d) + 1]++;
             for(int k = 1; k < 256; k++)
                   count[k] += count[k-1];
             for(int i = 0; i < N; i++)
                   temp[count[a[i].charAt(d)]++] = a[i];
             for(int i = 0; i < N; i++)
                   a[i] = temp[i];
        }
   }

I guess that by 256 they mean $R$. We have a simple for loop, so the time is $\Theta(W(R+N))$ The reason why I use $\Theta$ is because the bound is tight, this is how many operations you will be doing no matter what, so it's worst case and best case performance at the same time. The space requirements are $\Theta(N+R)$

The following is the pseudocode of MSD:

    public static void msd(String[] a)
    {
        msd(a, 0, a.length, 0);
    }

    private static void msd(String[] a, int lo, int hi, int d)
    {
        if (hi <= lo+1) return;
        int[] count = new int[256+1];
        for (int i = 0; i < N; i++)
             count[a[i].charAt(d)+1]++;
        for (int k = 1; k < 256; k++)
             count[k] += count[k-1];
        for (int i = 0; i < N; i++)
             temp[count[a[i].charAt(d)]++] = a[i];
        for (int i = 0; i < N; i++)
             a[i] = temp[i];
        for (int i = 0; i < 255; i++)
             msd(a, l+count[i], l+count[i+1], d+1);
   }

Since the recursion we will stop recursing after $W$ levels in the worst case, the space complexity becomes $\Theta(N + WR)$

however what about time? Just from space itself, it seems like MSD is actually pretty bad. What can you say about the time? To me it looks like you will have to spend $R$ operations for every node in your recursion tree and also $N$ operations per every level. So the time is $\Theta(NW + R*amountOfNodes)$.

I do not see how and why MSD would ever be preferred in practice given these time bounds. They are pretty horrible, but I am still not sure whether I get the time bounds in a correct way, for instance I have no clue how big is amountOfNodes..

Keep in mind that I would like the analysis to be in terms of R and N. I know that in practice R is usually small so it's just a constant, but I am not interested in this scenario, since I would like to see how much does R affect the performance as well.

I asked a kind of similar question yesterday but I did receive any replies, I think the reason for that was because my question was not well structured, so I could remove this question if the admins wanted. Thank you in advance!

If I understand OP's question correctly - the question is what is the time-complexity estimate for MSD radix sort, taking into account what OP calls AmountofNodes or recursive frames for an MSD sort, which must fill the count[] array ($R$) per each recursive frame and than iterate through the count[] array to create subfiles. I couldn't find this in the literature and I presume jsguy hasn't found a satisfactory explanation either.

I'm going to assume we are talking about the Naive MSD sort as described in the OP's pseudo code. (otherwise if you have 20 items in a subfile and $R = 256$, a hash-table would be significantly cheaper than the count[] array).

From the looks of it worst case time-complexity for that should be $\Theta(NW + NR^{(W-1)})$, where each item is unique. Specifically a worst-case number of $R$ calls will happen if none of the recursive calls terminate early (before $W_{i-1}$) and if a subfile is broken up as much as possible from the root (the maximum number of recursive calls started from any subfile is $R$).

Considering a set of subfiles $N$ - if the set is already dense duplicates only cost $W$ ($N > R^W$ and all combinations appear), if the set is sparse ($N < R^W$ and without duplicates), adding a duplicate costs at most $R(W-1)$ (if a single subfile would otherwise have terminated early at $W_1$).

If the set $N$ is sparse, either some combinations will not diverge at level $W_0$ (which is always more expensive than diverging at some further level $W_x$) or as many as possible will diverge at each level but some will terminate before $W_{i-1}$ because the branch will have only a single item remaining - therefore for sparse sets the worse-case is to have maximal divergence at each level $W$ until there are two duplicates in each subfile, for which the above estimate of $R(W-1)$ per item should apply.

edit: As to why people use MSD Radix sort, I hope someone that works with an application that utilizes Radix sort can answer that, I suspect there are cases like long RNA strings where there are very long strings with a very small $R$, and the ability to parallelize is an advantage (just a guess though). My worst case estimate definitely sounds pretty bad, but I think in practice no one tries to split a file of two duplicate items into $R$ buckets at every single $W_i$.


Composition of polynomial and logaritmic function Let $f$ be a computable function in $PSPACE$ It is true that Turing machine that computes $f$ can produce only $EXP$-size output at most. I see that $\log 2^n = n$ we can "control" the output. But, it doesn't convince me.

Please explain

Consider a Turing machine computing $f$. Suppose that it has $q$ states and $m$ tapes, that the tape alphabet is $\Sigma$, and that on input of length $n$, it uses at most $M(n)$ space. The number of possible configurations of the Turing machine is at most $N(n) = qM(n)^m|\Sigma|^{M(n)}$. In particular, if it runs for more than $N(n)$ steps then some configuration must repeat, and so it never terminates. Since the machine computes $f$, it does terminate, and so it runs in time $N(n)$. In particular, the output size is at most $N(n)$.

When $M(n)$ is polynomial, $N(n)$ is exponential ($2^{n^{O(1)}}$).


Pseudo-number generation compared to Blum-Micali A few years ago I made a pseudo-random number generator to use in a monte carlo simulation for a lecture in my University.

My instructor ask me why I did that generator instead of using C equivalent rand.

The algorithm is $x_{n+1} = e^{x_n + k} \mod 1$ using float point values with $K$ big enough to contain a complete cycle inside $\epsilon$ (a very small value).

Yesterday I find another PRNG using a similar formula: Blum-Micali algorithm

$x_{n+1} = g^{x_n} \mod p$

The answers are... could my algorithm be based on the Blum-Micali one?

Could my algorithm contain the Blum-Micali properties?

Thanks in advance.

No, your algorithm is fundamentally different.  The resemblance is purely superficial.  The Blum-Micali generator is based on integers modulo a large prime number, and leverages deep number theoretic ideas.  Yours is based on the fractional part of real numbers (hence the "mod 1"), and is not based on number theory and not related to Blum-Micali.  Blum-Micali is cryptographically secure.  Your scheme seems unlikely to be.


Matching Algorithm - How to maximize matched quantity with unique matching rules? Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules:

$$\begin{aligned}
A\leftrightarrow B\\
C\leftrightarrow D\\
B+C\leftrightarrow F\\
D+A\leftrightarrow E\\
G+H\leftrightarrow B\\
\end{aligned}$$

The input to the matching algorithm is an array of variable size consisting of elements in $S$. Each item in the array has a particular size or "quantity" that can be matched (I imagine this can simply be modeled as edge weights).

For notational clarity -

$A \leftrightarrow B$ indicates "If an item exists in the input array of type A, it may match with an item of type B". The reverse is also true, so if there is $B$ it may match with $A$.

$B+C\leftrightarrow F$ indicates "If an item exists in the input array of type $B$, and another of type $C$, they may together match with an item of type $F$", the reverse is also true, so if there is $F$ and $C$, they may together match with $B$. $F$ by itself may not match with either $B$ or $C$.

The first question is, how to maximize the total quantity matched?

Second question is, how to optimize time complexity? If the algorithm is NP, please provide some proof or reason as to why it cannot be solved in P.

Intuitively, I think the problem could be modeled as a weighted bipartite graph and solved with a max-flow algorithm or dynamic programing. Once I construct the bipartite graph, the problem becomes easy to solve as bipartite graphs have been heavily studied.

The challenge is I'm not sure how to algorithmically construct the graph in a provably correct way given the rules or if it implies a different approach should be used. I'm thinking it may help to sort the input array by quantity and then not connect an edge if a vertex is marked as 'matched', but that alone doesn't solve the problem (i.e. BFS/DFS do not seem so help). Other potential avenues may be more generally 2D dynamic programing or set covers (although set covers are also in NP).

An Example with the (not quite bipartite) Graph Approach:

Take input array $[A:5,\ A:4,\ D:6,\ B:3,\ E:5]$, where $A:5$ indicates an item A with quantity 5. The bipartite graph should look like the below where the colors indicate potential matches (ignoring quantities) except that it allows for impossible matches, namely $\{A, E, A, B\}$ should not be possible but is according to the graph:

The potential matches should be:

$A, E, D$ (top edges)
$A, B$ (bottom edges)
$A, E, D$ (first bottom then top edges)
$A, B$ (top then bottom edges)

Ultimately the solution including quantity would be 2 matches with some quantity left over:

${A:5/5,\ E:5/5,\ D:5/6}$
${A:3/4,\ B:3/3}$

Left over

$D:1$
$A:1$

The problem you are describing is a special case of the (weighted) 3-dimensional matching problem.1

Unlike regular 2-dimensional matching, maximum cardinality 3-dimensional matching is NP-hard, which means that weighted 3-dimensional matching is NP-hard. Therefore, solving this problem exactly in polynomial time doesn't seem feasible, unless the specific case you have here is easier than the general problem.

This special case seems easier than the general problem. My idea is to represent it as a minor modification to the regular 2d maximum weight matching problem. Note that for each of your combinations of 3 items, there is at least one item type that is not present in another combination (e.g. $E$ is only present in the combination $(A,D,E)$), I will call such an item type conflict-free. First, select a conflict free type for each combination of $3$ types: Here, I pick $E$ for $(A,D,R)$, $F$ for $(B,C,F)$, and $H$ treat items of such type differently than the others.

More concretely, for any combination of items $x,y,z$ of type $X,Y,Z$, where $Z$ is the chosen conflict-free type, we add only the edge $(x,y)$ of weight $f(q(x), q(y),q(z))$, where $q(i)$ denotes the quantity of item $i$ and $f$ is a function that determines the value of a matching based on the weight (including the type is of course also possible). Combinations with only $2$ types can be modeled as usual. Solving the maximum weight matching problem on this graph (which in your case is bipartite) provides the maximum sum of values that can be made.

For example, on the input $[A:5,\ A:4,\ D:6,\ B:3,\ E:5]$, the graph will look like the following:

Red edges and their weights indicate the maximum matching. Note that the item of type E is not part of the graph, but only influences the weight of the two edges between types A and D. So the approach works for this case.

However, if we have items of type E with different quantity, we the weights of the edges will depend on which edges are selected. To see this, take the input $[A:5,\ A:4,\ D:6,\ D:4,\ B:3,\ E:5,\ E:1]$. We now get the following graph:

The edges between type $A$ and $D$ now no longer have a simple value as their weight, but a list of values. This is because each edge has to use one of the two $E$'s, but the same one cannot be reused. This means in particular that the blue matching has a value of $12+3=15$ instead of $12+12=14$, because the item $E$ of quantity $5$ can only be used once. Therefore, it is the red matching of value $21$ that is optimal.

I do not know whether the standard algorithms for weighted bipartite matching can deal with this modification on the weights or whether there we can make a modification to the standard algorithm to handle this.

1: Possible matches of the form $X+Y\leftrightarrow Z$ for items $x, y, z$ can be represented by the 3d-edge $(x,y,z)$ of weight the minimum of the quantities of the items $x,y,z$. Matches of the form $X\leftrightarrow Y$ for items $x,y$ can be represented by the 3d-edge $(x,y,d)$ of weight minimum of the quantities of items $x,y$ and a dummy vertex $d$ that is in no other 3d-edge.


Could the Halting Problem be "resolved" by escaping to a higher-level description of computation? I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox.

So I got to wonder: mathematicians did eventually manage to make set theory consistent by transitioning from Cantor's naive formulation of the field to a more complex system of axioms (ZFC set theory), making important exclusions (restrictions) and additions along the way.

So would it perhaps be possible to try and come up with an abstract description of general computation that is more powerful and more expressive than Turing machines, and with which one could obtain either an existential proof or maybe even an algorithm for solving the halting problem for an arbitrary Turing-machine?

Well, you can always consider a Turing machine equipped with an oracle for the ordinary Turing machine halting problem. That is, your new machine has a special tape, onto which it can write the description of an ordinary Turing machine and its input and ask if that machine halts on that input. In a single step, you get an answer, and you can use that to perform further computation. (It doesn't matter whether it's in a single step or not: it would be enough if it was guaranteed to be in some finite number of steps.)

However, there are two problems with this approach.

Turing machines equipped with such an oracle can't decide their own halting problem: Turing's proof of the undecidability  of the ordinary halting problem can easily be modified to this new setting. In fact, there's an infinite hierarchy, known as the "Turing degrees", generated by giving the next level of the hierarchy an oracle for the halting problem of the previous one.
Nobody has ever suggested any way in which such an oracle could be physically implemented. It's all very well as a theoretical device but nobody has any clue how to build one.

Also, note that ZFC is, in a sense, weaker than naive set theory, not stronger. ZFC can't express Russell's paradox, whereas naive set theory can. As such, a better analogy would be to ask whether the halting problem is decidable for weaker models of computation than Turing machines. For example, the halting problem for deterministic finite automata (DFAs) is decidable, since DFAs are guaranteed to halt for every input.


What is the instruction format for an accumulator machine? I need to learn about accumulator machines, but there is next to nothing written about them. Computer architecture channels seem to be flooded with general-purpose register ISAs (like MIPS, x86, etc).

I know that accumulator machines only have one register (called the Accumulator Register) that is implicit and not specified in any of the operations. In general, an instruction for an accumulator architecture is supposed to look something like: add memaddress.

However, I need to get more specfic. I need to know exactly how many bits are in the various instruction fields (i.e. opcode) for an instruction of an accumulator machine.

I have the following accumulator machine:

$2^{24}$ words of memory (words are 32-bits wide)
Fixed format instruction (but how many bits??)
A 32-bit accumulator register
An index register X
Index addressing mode: address field + X when indexing is indicated in the instruction
Capable of performing a total of 128 operations

The last bullet tells me that the opcode of an instruction would be 7 bits since $2^{7}=128$.

What would the instruction format be for a load/store instruction vs. an arithmetic instruction like add? It would help greatly if I knew how many bits the fixed format instruction should be.

Fixed format instruction means that all instructions have the same size of $k$ bits. You ask to learn what $k$ is.

As you say, the opcode takes 7 bits. So $k \ge 7$
In order to support memory operations (such as add mem or load mem etc) we need to be able to give an address (=mem). If the dressing mode is direct, and given there are 24 bits address, we have that $k \ge 7+24$.
But the description of your CPU suggests that there is other addressing modes. Specifically, there is another register, index register that allows accessing the memory of [X+mem] where X is the content of the indexing register and $mem$ is the 24 bits of address we already counted for. Now, do we need to state X in the instruction itself? - No. we just need to be able to mention the addressing mode is different = a different opcode.
what about load immeidate (i.e., loading an immediate value directly into the accumulator)?

I don't know.

Your description doesn't give any information or constraints on this issue and there are many different ways to implement the same action. In particular, one can think of "load-byte" instruction which will update the (LSByte of the) accumulator with some fixed value. The current $k$ is enough for such instruction as long as the immediate value is at most 24bits.  If you wish to have a way to update the entire 32bits of the accumulator using a single instruction you will have to increase $k$ to support this operation as well.

So unless there are other demands or clarifications to the description you gave, we get that $k \ge 31$.


A Black Box Algorithm I'm taking an introductory quantum computations class and I am attempting to solve the following question(s), but we haven't touched on black box algorithms like this in class, and I honestly don't know how to solve the question at all.  Would it be possible to help me through the steps?

Question.  Consider the set of all functions $f:\{0,1\}^n \rightarrow \{0,1\}$ that are of the form $f(x_1,x_2,...,x_n)=x{_j{_1}} \oplus x{_j{_2}} \in \{1,2,...,n\}$ with $j_1 \neq j_2$.  Suppose we are given such a function as a black box (without information about $j_1,j_2$ and our task is to determine the set $\{j_1,j_2\}$.

(a) Show that any classical algorithm must male at least $\Omega(log(n))$ queries to f to solve this problem exactly.  (We have used the $\Omega$ notation to give lower bounds, defined as following: Suppose $f(n), g(n)$ are functions form the positive integers to the real numbers.  Then we say $f(n) \in \Omega(g(n))$ if there exists a positive, real c, and an integer $n_o$ such that for all $n>n_o, f(n)\geq cg(n)$.

We are also given the following hint: Note that the data that a k-query classical algorithm obtains is a k-bit string. Next, consider how big k needs to be so that there are enough k-bit strings to be uniquely assigned to each $\{j_1,j_2\}$.

(b) Give a quantum algorithm in the black box model that solves ths problems exactly with a single query to f.

Any possible assistance would be amazing.  Thank you!

Regarding part (a): just like in the classical lower bound for sorting, any black box algorithm which queries $f$ can be described as a binary decision tree whose leaves contain the correct answer $\{j_1,j_2\}$. Every pair $\{j_1,j_2\}$ is possible, so the tree must have at least $\binom{n}{2}$ leaves, hence it must have height at least $\log_2 \binom{n}{2} = \Omega(\log n)$.

If you don't understand the argument, look up the $\Omega(n\log n)$ lower bound on sorting in the comparison model (also known as the decision tree model).

Can we do it with $O(\log n)$ queries? Suppose for simplicity that $n = 2^k$ is a power of $2$. If we feed the algorithm the bit string $x(b_{k-1}\ldots b_0) = b_i$ then we get the $i$th bit of $j_1 \oplus j_2$, so using $\log_2 n$ queries we can find $j_1 \oplus j_2$. Suppose for simplicity that $j_1 \oplus j_2 = 1$. If we feed the algorithm the bit string defined by $x(b_{k-1}\ldots b_1 0) = 0$, $x(b_{k-1}\ldots b_1 1) = b_i$, then we recover the $i$th bit of $j_1$ (or $j_2$), so using $\log_2 n - 1$ more queries, we recover $j_1,j_2$. In total, we used $2\log_2 n - 1$ queries, which practically matches the lower bound $\log_2 n + \log_2 (n-1) - 1$.

Unfortunately I can't help you with part (b).


Prove $|d_{s}(u)-d_{s}(v)|\leq1$ in BFS Trying to prove the following problem:

Given a graph $G=(V,E)$ and vertex $s\in V$, prove that: $\forall (u,v)\in E,\ |d_{s}(u)-d_{s}(v)|\leq1$ where $d_s(v)$ is the shortest path from $s$ to $v$ in BFS.

What I did: Let assume that it's isn't true, meaning there is $(u,v)\in E$ so $|d_{s}(u)-d_{s}(v)|>1$. Lets run BFS on graph $G$. If in BFS process there is edge $(u,v)$, this means that $d_{s}(u)+1=d_{s}(v)$ so $|d_{s}(u)-d_{s}(v)|=1$ which contradicts $|d_{s}(u)-d_{s}(v)|>1$. This means that there is at least one edge $w\in V$, in the path from $u$ to $v$.
Now I'm stuck. I don't come empty handed, I have the following theorems:

Given graph $G=(V,E)$ and vertex $s\in V$, for each edge $(u,v)\in E$ we have $\delta\left(s,v\right)\leq\delta\left(s,u\right)+1$ where $\delta(s,v)$ is the shortest path between $s$ and $v$ (or $\infty$ if no such path) in graph $G$ (note the difference between $\delta$ which on $G$ and $d$ which on BFS).
For each vertex $v\in V$ we get $d(v)=\delta(s,v)$ in BFS.

I think I might need to use those two theorems here but I don't see it. My problem is that there is at least one vertex $w$ and not exactly one. How can I prove it?

First of all your question is quite confusing:

There is at least one edge $w \in V$

Is it an edge or a vertex?
Maybe it would be easier for you to look at some edge $(u,v) \in E$ and think about the moment in time $\tau$, when the BFS algorithm reached either $u$ or $v$ for the first time (it could reach them both at the same time).


Are problems that are fractions of constraints of NP-complete problems also NP-complete? We know that Hamiltonian path, clique and independent sets are NP-complete but what about half or the square root of each problem or a fraction of $n$ ? That is, for a graph, $G$ of $n$ nodes,

is there a Hamiltonian path of size $\frac{n}{2}$ or of $\sqrt{n}$ or any number of nodes less than $n$?
is there an independent set of size $b$ in  $\frac{n}{2}$ or of $\sqrt{n}$ or any number of nodes less than $n$?
is there a clique of size $k$ in $\frac{n}{2}$ or of $\sqrt{n}$ or any number of nodes less than $n$?

There is no general rule that they necessarily need to be NP-complete in general.
For the specific examples you list, I expect the answer will be that each of those specific examples are NP-complete, but I haven't tried to prove or verify that; that's just speculation.


Find a CFG for the language $\{ x\$y \mid x,y\in\{a,b\}^* \wedge |x| \ne |y| \}$? Consider the language below, on the alphabet $\Sigma = \{a,b,\$\}$:
$$L = \left\{ x$y \mid x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$

I need to define a CFG for this language. I've tried couple of CFGs but they all failed in one way or another.

I'd be glad for help.

Hint:
$$
L = \{ \Sigma^{m+1} \Sigma^n \$ \Sigma^n : n,m \geq 0 \} \cup \{ \Sigma^n \$ \Sigma^n \Sigma^{m+1} \},
$$
where $\Sigma = \{a,b\}$.


An equivalent of $\neg ((a \wedge b) \Leftrightarrow c)$ based on a specific requirement I am solving a problem that is asking to provide an equivalent for $\neg ((a \wedge b) \Leftrightarrow c)$ and the equivalent shouldn't contain $\wedge$ (and), $\Rightarrow$ (implication) or $\Leftrightarrow$ (iff).
What I have worked out is:
$\neg(\neg((\neg a \vee \neg b) \vee \neg c) \vee \neg(\neg(\neg a \vee \neg b) \vee c))$
I wonder based on the requirement stated above, is there a shorter equivalent for my answer?
Update
$\oplus$ is not allowed in the requirement either.

Outgoing from requirements can you  use $\oplus$? if yes, then, as we know, that $\neg(a\Leftrightarrow b) = a \oplus b$, then we can obtain
$$\neg ((a \wedge b) \Leftrightarrow c) = \neg (\neg a \lor\neg b) \oplus c$$
Update.
Accordingly to your update I wrote my one: not shorter, slightly different, but logically equivalent yours one
$$\neg \big[(a \wedge b) \Leftrightarrow c\big] = \\
=\neg \big[\big((a \wedge b) \Rightarrow c \big) \land \big(c \Rightarrow (a \wedge b)\big) \big]=\\
=\neg \big[ \big(\neg (a \wedge b) \lor c \big) \land \big( \neg c \lor (a \wedge b) \big) \big]=\\
=\neg \big[ \big(\neg a \lor\neg b \lor c  \big) \land \big(\neg c \lor \neg(\neg a \lor\neg b) \big) \big]=\\
= \neg\big(\neg a \lor\neg b \lor c \big) \lor \neg\big( \neg c \lor \neg(\neg a \lor\neg b) \big) $$


Euclidean algorithm - runtime in specific case I'm going to solving many times this specific equations:

$$2^{x+y} \cdot c - a^{y} \cdot z = 1$$

in which $$a$$ can be equal to: $$-7,-5,-3,-1,1,3,5,7.$$ And $$x+y$$ will be equal to $$128.$$ It has to be done with euclidean algorithm, but how many step it requires in average in this specific case?

I know that euclidean algorithm requires at most $$5\log_{10}b$$ steps (Wikipedia), where b is the smaller number, but in this case we don't know which number will be smaller, $$2^{x+y}$$ or $$a^{y}.$$ That's why I have a problem with this case.

Your problem amounts to solving $2^{128} c - a^y z = 1$.  I assume you are given $a,y$ and must find $c,z$ that satisfy the equation.

I suggest you first solve
$$a^y z \equiv 1 \pmod{2^{128}}.$$
This has as solution
$$z \equiv (a^{-1})^y \pmod{2^{128}},$$
so you can find a solution for $z$ by computing the inverse of $a$ modulo $2^{128}$ (using one invocation of the Euclidean algorithm; or by a Hensel lifting method if you prefer), and raising it to the $y$th power using a fast exponentiation algorithm.  Then, compute $c = (1 + a^y z)/2^{128}$.


Determining if given languages are regular or recursively enumerable I came across following problem:

  Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine
  $L_1 =\{M|M$ accepts at most 2016 strings$\}$
  $L_2=\{M|M$ accepts at least 2016 strings$\}$
  If $L=L_1\cap L_2$, then which one of the below is correct?
  A) $L'$ is recursively enumerable
  B) $L\cap L'$ is recursively enumerable
  C) $L\cup L'$ is recursively enumerable
  D) $L$ is recursively enumerable

The solution given was:

  $L_1$ by definition is regular language (“atmost”).
  $L_2$ by definition is recursively enumerable (“at least”).
  Recursively enumerable languages are closed under regular intersection. Hence, $L = L_1 ∩ L_2$ is recursively enumerable. Thus option D. Recursively enumerable languages are not closed under complementation. Hence $L’$ is not recursively enumerable. Hence option A is wrong. And since $L’$ is not recursively enumerable, options B and C are also wrong.

My doubt

I am struggling with how $L_1$ is regular and $L_2$ is recursively enumerable, that is with first two sentences:

  $L_1$ by definition is regular language (“atmost”).
  $L_2$ by definition is recursively enumerable (“at least”).

Usually language definition specifies criteria on format of input string which will allow us to reject or accept it. But here the definition specifies how many strings the language has or its corresponding Turing machine accepts.

I found this similar sounding problem, in which the answer gives membership algorithm and hence proving language in that problem is indeed recursively enumerable. But I feel this does not applies in my problem. Correct? Or the problem is incorrect in telling number of strings languages can accept instead of format of acceptable strings?

Your intuition is entirely correct; this solution is nonsense. $L_1$ isn't a regular language; it's not even a decidable language, by Rice's Theorem, and also not recognizable (aka recursively enumerable).

$L_2$ is in fact recognizable. The following algorithm recognizes it:

  Take an encoded Turing machine $M$ as input. First simulate it on every input of length ≤ 1 for 1 step, then on every input of length ≤ 2 for 2 steps, and so on. Keep track of how many distinct inputs it's ever accepted. If this number ever exceeds 2016, return True.

But as it turns out, none of this matters to the actual problem. Note that (C) is taking the union of a language with its complement, and the union of any language with its complement is $\Sigma^*$. This language is regular, thus decidable, thus recognizable. So the correct answer is (C).

EDIT: Of course, the intersection of a language with its complement is $\varnothing$, which is also regular, thus decidable, thus recognizable. So (B) is also true.


What is the type of linked list where order doesn't matter I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about linked listed implementation:

  Insertion into a singly-linked list is a nice exercise in pointer
  manipulation, as shown below. Since we have no need to maintain the
  list in any particular order, we might as well insert each new item in
  the simplest place. Insertion at the beginning of the list avoids any
  need to traverse the list, but does require us to update the pointer
  (denoted l) to the head of the data structure.

I'm wondering what kind of list is that because I can't use it for index based access. All other basic implementations I've seen provide index based access.

When searching for an item, their implementation shows direct object comparison:

list *search_list(list *l, item_type x)
{
    if (l == NULL) return(NULL);
    if (l->item == x)
        return(l);
    else
        return( search_list(l->next, x) );
}

So I'm thinking maybe they didn't account for index based access.

This book also distinguishes Container and Dictionary categories of DS:

  We use the term container to denote a data structure that permits
  storage and retrieval of data items independent of content. They are
  distinguished by the particular retrieval order they support (LIFO,
  FIFO). By contrast, dictionaries are abstract data types that retrieve
  based on key values or content.

It seems that the linked listed implementation at hand falls into a container category with the object reference as the key, something alike a map DS.

Is this assumption valid?

I took a look at the book you are referencing, and it does appear that Steven Skiena made an unordered Dictionary implemented as a linked list.  It's not a terribly efficient data structure, but he was only using it to illustrate basic linked list coding techniques, so I expect he just wanted to keep things as simple as possible.

For what it's worth, a stack is a container that only allows you to add to or access from the very top item, which isn't really index based in the way we'd usually use that term.  I mention this only to highlight that Containers do not need to have index-based retrieval.


Runtime analysis of bit operations In class we have learned that division takes O($k^2$) where k is the bitlength of the numbers used in the operation. What would be the runtime of a function that looks like this?

while a % 2 == 0:
    a = a / 2

I am guessing the worst case is $O(log(k)k^2)$ as a decreases by 2 each time but each division takes $k^2$

Numerical division of arbitrary numbers is $O(k^2)$, but division by 2 is a special case that is always $O(k)$, and a % 2 is $O(1)$, since it only requires examining a single bit. Since the loop requires $O(k)$ iterations, that makes the whole computation $O(k^2)$ in terms of bit operations.

In practice, however, you'd either

have a stored in a shift register to begin with, which means that the division (shift) operation is $O(1)$, making the overall implementation $O(k)$.
use a pointer to find the first nonzero bit of a (which takes $O(k)$) and then copy the bits to the result just once (which is also $O(k)$), making the overall implementation $O(k)$


What's the difference between $a^*+b^*$ and $(a+b)^*$? What's the difference between the regular expressions $a^*+b^*$ and $(a+b)^*$. Do both of these generate the same language? I was told in a lecture that $(a+b)^*$ will generate string concatenation of $a$ and $b$. How could this be possible?

$a^*+b^*$ generates words that either consist of any amount of $a$s or any amount of $b$s, like: $a$, $aaaaa$, $bbbb$
$(a+b)^*$ generates secquences of either $a$ or $b$, for example: $abab$, $aabb$, $bbaa$,...

So, the main difference is, that in 1 you either get strings only containing as or only containing bs. Regex 2 produces a language where you have no order of characters and can put both in.

So, both don't produce the same language, but 1 is a subset of 2.


How do non-deterministic algorithms work on current machines? I have some questions regarding the exact nature of non-deterministic algorithms. Is it right that non-deterministic algorithms do not rely on any randomness whatsoever? In which case, this Wikipedia article which mentions Fermat's little theorem includes generating random numbers. I had thought that non-determinism was more of a concept than one that could be put into practice at this given moment - so what exactly are the 'non-deterministic algorithms' on the Internet, such as on the Wiki page above?

Furthermore, D. Harel's book Algorithmics introduces non-determinism in that whenever the machine must make a choice between two or more branches to next states, it ALWAYS picks the one which will lead to an accepting state, if there are any accepting states. In this way, how can non-deterministic algorithms exist on current machines, as they don't have 'insight' as to what will happen further down the line?

Finally, does converting from a non-deterministic FSM to a deterministic FSM take an exponential amount of time? If not, what bearing would this have on the P=NP problem?

Is it right that non-deterministic algorithms do not rely on any randomness whatsoever?

Yes and no. Non-determinism just means that there in the computation there is a choice that needs to be made based on information not available to the algorithm. There are multiple solutions to this choice, one of which is randomness - for example in random pivot quicksort.

I had thought that non-determinism was more of a concept than one that could be put into practice at this given moment - so what exactly are the 'non-deterministic algorithms' on the Internet, such as on the Wiki page above?
Furthermore, D. Harel's book Algorithmics introduces non-determinism in that whenever the machine must make a choice between two or more branches to next states, it ALWAYS picks the one which will lead to an accepting state, if there are any accepting states. In this way, how can non-deterministic algorithms exist on current machines, as they don't have 'insight' as to what will happen further down the line?

There are four main approaches (to my knowledge) for dealing with non-determinism: parallelism, randomness, backtracking and superstates.

Parallelism: whenever a choice needs to be made split the program and investigate all choices in parallel.

Randomness: use randomness to choose a single choice out of all.

Backtracking: deterministically choose a choice (e.g. the first one) and continue computation with that choice. When that choice wasn't correct go back and choose the second options, etc.

Superstates: track all possible states the program can be in, and whenever input is received apply that input to all possible states, merging states and rejecting states eagerly.

Note that not all approaches are always valid and/or feasible. Parallelism is rarely feasible as it requires a lot of physical resources and not much non-determinism, randomness is only correct if each choice is correct, and it's just a matter of performance.
To directly implement a NFA either 3 or 4 is used. Another example of 4 are full CFG parsers that can handle ambiguity such as an Earley parser.

Finally, does converting from a non-deterministic FSM to a deterministic FSM take an exponential amount of time?

By necessity, because the resulting output can have an exponential number of states.


Negative numbers in Subset-Sum If I have a set $A$ with positive and negative numbers, and a number to find C.

It is possible to reduce the problem to one with only positive numbers in set $A$?

I mean, it is possible to find a new set $A$ and a new number $C$, so $A$ were only positive numbers, but the same problem?

Hint: Let $A = \{ a_1,\ldots,a_n \}$. Choose a large number $M$ and consider the set $\{ M + a_1, \ldots, M + a_n, M, \ldots, M \}$ ($n$ times the number $M$) and the target $nM + C$. If you want an actual set, instead of taking $n$ times the number $M$, take $M,2M,4M,\ldots,2^{\lceil \log_2 n \rceil}M$ (we assume that $0 \notin A$; otherwise, remove $0$ from $A$).


Polynomial multiplication coefficients I was wondering about the following interesting questions:
Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial.
What about finding a specific coefficient (or even deciding whether it is 0 or not) of some degree $k$ of the multiplication of an input? It is trivial to see that linear time in k is a must and sufficient as stated by D.W.
If one can preprocess the polynomial and query some specific coefficient is there an interesting $o(polynomial-multiplication)$ preprocessing and $o(k)$ per query ?

Yes, there are more efficient ways.  If you have two polynomials $p(x)=\sum p_i x^i$ and $q(x) = \sum q_i x^i$, then the coefficient of $x^k$ in $p(x) q(x)$ is given by

$$\sum_{i=0}^k p_i q_{k-i}.$$

This can be computed in $O(k)$ time, which is more efficient than multiplying the polynomials and extracting the coefficient of $x^k$.

With preprocessing, you can just multiply the polynomials during the preprocessing phase and store all of the coefficients.  Then looking up any desired coefficient can be done in $O(1)$ time.


Running time complexity of finding maximal power of divisor that divides natural number Given $n \in \mathbb{N}$, a divisor $p\vert n$, I would like to efficiently find $e\in\mathbb{N}$ with $p^e \vert n$, and $e$ maximal with this property. I will assume that multiplication/division of two $b$-digit numbers has time complexity $O(b^{\log_{3}{5}})$. (Ie. I use the Toom-Cook algorithm.)
Then it can be shown that the naive repeated division approach has a complexity that's worse than $O(\log^{2}(n))$.

An alternative I considered is performing a binary search like algorithm on $\{0, 1, ... \log{n}\}$, where I assume that $\log{n}$ is given. This means that instead of checking all $\log{n}$ candidate powers, it suffices to consider only $\log{\log{n}}$ elements of the above set of possible powers. For each candidate power $p^f$ a division $p^f \vert n$ is required, which can be performed in $O(b^{\log_{3}{5}})$. We only need to compute the maximal power of $p$, $p^{\log{n}}$ as we can store intermediate powers (even if we use repeated squaring , precisely because a binary search is performed on our search space). The cost of computing $x^y$ via repeated squaring is $O((y \log{x})^{\log_{3}{5}})$. Hence the overall complexity of this approach is $$O(\textit{exponentation_cost} + \textit{division_costs}) = O((\log{n} \log{p})^{\log_{3}{5}} + \log{\log{n}} \cdot (\log{n})^{\log_{3}{5}})$$

Now supposing that $p$ is small relative to $n$, that is $p \in O(\log{n})$, then the above expression belongs $O((\log{n} \log{\log{n}})^{\log_3{5}})$, which isn't too bad.

My questions are:

Does the above analysis look sensible?
Is there a standard/better way to do this?

Here is one more approach you could consider, depending on whether you care more about theoretical running time or pragmatic solutions:

Use binary search to find the smallest $k$ such that $p^{2^k}|n$ but $p^{2^{k+1}}\not|n$.
Compute $m = (n/p^{2^k}) \bmod p^{2^k}$.
Recursively find the smallest $i$ such that $p^i|m$ but $p^{i+1}\not|m$.

(In the third step, you know $0 \le i < 2^k$, so you have a narrower range for your search, and $m$ is smaller than $n$, so you are working with smaller numbers.)

Then it follows that the solution to your problem is $e=2^k + i$.

Note that $k \le \lg {\log n \over \log p}$, so you can find $k$ with binary search in $O(\log \log {\log n \over \log p})$ steps, where each step does a single trial division.  In the worst case, $m$ might not be much smaller than $n$, so this might not save you much.  But in many cases, $m$ will be vastly smaller than $n$, so step 3 is a lot easier than the original problem.  In particular, on average $m$ will be on the order of magnitude of $\sqrt{n}$ or less, so heuristically we might expect that after $\lg \lg n$ recursions we're dealing with constant-sized numbers, and heuristically we might expect the total running time to be dominated by step 1.  This won't always be true in the sense of worst-case complexity, though.


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

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

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

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

thanks

It's a variant of Set cover which is Classical NP-Complete problem.
Here is the problem definition.

Reduction: Take All courses as a Universal set U which you want to cover.
Then make collection of sets $S=\{P_1,P_2,...,P_m\}$ where, $P_i$ is the set of subjects for which a professor $i$ can design a question.
and you can go similarly in reverse direction.

So there is no polynomial time algorithm for your problem unless P=NP.