Why can't we prove decidability of $L= \{ \langle M \rangle : M$ accepts $ \epsilon \}$ with a configurations graph? Since every deterministic Turing Machine can be translated to a graph of configurations such that $M$ accepts a word $w$ iff there is a path from the initial configuration that matches $w$ to an accept configuration, we can define a decider $D$ for $L$ such that:

$D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.

Though this seems simple and valid (to me), there is a well-known result showing that $L$ is undecidable. I can't figure out what is the flaw in the proof and will be happy for any help to figure it out

$D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.

The problem here is that, even if you define the TM so that there are only finitely many accepting configurations (e.g. by requiring that the final tape be empty), the configuration graph itself may have infinitely many vertices. This is because the configuration includes the contents of the tape, and the tape contains however many cells the TM has written to, which is in general unbounded.

Every vertex can be identified by a finite string (the configuration description), and each vertex is connected to only a finite number of other vertices (determined by the transition relation), so the graph is locally finite. But the whole graph may still have an infinite number of vertices that are reachable.


Operators in descriptive complexity When we talk about operators in descriptive complexity, are they something like this: for example, if transitive closure operator $TR$ is available, we can use variable $y$ that we define as $TR(x)$ where $x$ is input? or is it something else?

Also, when we say $FO(t(n))$, what does quantifier block being iterated $t(n)$ times mean?

First Part: Let's first define the TR operator (Why do you use $TR$ and not $TC$?)
Given a formula $\phi$ with free variables $x_{i_1},\dots,x_{i_{2k}}$ than the string $\psi =TR(x_{i_1},\dots,x_{i_{2k}},\phi)(y_{i_1},\dots,x_{i_{yk}})$ is also a formula.
If you now consider an interpretation $\mathcal{I}$ than $\psi$ is true under  $\mathcal{I}$ iff $(y_{i_1},\dots,y_{i_{2k}})^{\mathcal{I}}\in R^+$, where $(y_{i_1},\dots,y_{i_{2k}})^{\mathcal{I}}$ is the tuple assigned to $(y_{i_1},\dots,y_{i_{2k}})$ by $\mathcal{I}$, $R$ is the binary Relation on $k$-tuples defined by $\phi$ and $^+$ the transitive closure.

As your input is (only) a structure, your Formula can't have free variables, but of course it can have constants, e.g. $\psi = TR(x_1,x_2,\phi,c_1,c_2)$ where $\phi$ is $x_1 P x_2$.

Let's assume your input ${\mathcal{G}}$ is a graph and two of it's vertices: $(V,E,v_1,v_2)$ ($E$ being a symmetric relation, not a set of pairs). Then $P^{\mathcal{G}} = E = R$ (the $R$ from above). Now $\psi^{\mathcal{G}}$ is true (i.e. your input accepted) iff $v_1$ and $v_2$ belong to the same connected component.

Second part: $t(n)$ is a function of the input size, so if your input has size $n$ the quantifier block is repeated as-is $t(n)$ times, using the same variables in each instance.

Again the example of checking whether there is a path:

$$QB(x,y) = (\forall z: \neg(x = y \vee  x E y))\\(\exists z )(\forall u)(\forall v (u = x \wedge v = z) \vee (u = z \wedge v = y)) \\(\forall x: x=u)(\forall y: y=v)$$

This block consists of three parts:

Check if there's a short path (length 0 or 1), then "quit".
Check if there is an intermediate z.
Rename the variables to recurse.

Since $(\forall z \phi)\psi$ is short for $\forall z (\phi\rightarrow\psi)$  the formula $QB(x,y)\exists x\neq x$ is only satisfiable if $\neg(x = y \vee  x E y)$ is false, i.e. there is a path of length $1$ or $0$ between $x$ and $y$.

If your input has size $n$, you only need $1+\log_2 n$ recursion levels, i.e.
$QB(x,y)^{1+\log_2 n}\exists x\neq x$ tests whether $x$ and $y$ are in the same connected component.

This example is taken from: Expressibility and parallel complexity (Immerman,1989)


Confused between bandwidth and frequency I am new to Computer Science and started learning about computer networking very recently. I know that bandwidth means how many bits can be sent through the channel in 1 second. However, recently I came across another definition of bandwidth which says it is the range of frequency where the signal is received.

How to think intuitively of this? Frequency is the number of cycles per second. What is the relation between frequency and bandwidth?

Please note that I am a lay man. Kindly elaborate.

"Bandwidth" has several different meanings. Among others, it can refer to either a frequency range or to data rate in bits/second. You have to use the context to figure out which is meant.

These two notions of bandwidth are not directly related, but a signal with a wider frequency range (i.e., higher signal bandwidth) can usually transmit data at a higher rate (i.e., has higher data bandwidth). However, the relation also depends on how much noise is present.


Terminology for property of recursion definitions I have a question about generally accepted terminology (and whether it exists at all).

Some recursive algorithms on hierarchical data structures (trees) have the property that they are expressed as a function which does a single recursive function call on each of its children, and that this call takes no parameters other than the child node.

Example in Python:

def sum_of_values(node):
    result = node.value
    for child in node.children:
        result += sum_of_values(child)
    return result

Other algorithms do not have this property, and fundamentally cannot have this property.

Consider, for example, a mechanism for pretty-printing an AST, which has the property that we want the first child of any node to be displayed on a single line, but all the other nodes on their own line.

Also sketched in Python, leaving out many details (e.g. indentation):

def pretty_print(node, single_line_mode=False):
    if single_line_mode:
        return "(" + " ".join([pretty_print(child, True) for child in node.children]) + ")"

    result = "("
    if len(node.children) >= 1:
        result += pretty_print(node.children[0], True)

    for child in node.children[1:]:
        result += "\n" + pretty_print(child, False)

    result += ")"
    return result

The key point of the above is: The recursive call contains more information than simply the fact that some work must be done recursively. This information flows from the structure higher up in the tree (in this case: whether the some node in the path of presently printed node to the root of the tree is the first child of its parent).

If we were to rewrite the above by replacing the boolean parameter with 2 functions, our algorithm is no longer expressed in terms of a single recursive function call for each on each of the children.

So we can see a distinction: algorithms in which we can do calculations for constituent parts of a composite data structure independently from the data structure of which they are a part, and those for which this is not possible.

Is there an accepted terminology for this distinction?

Edit to add:

In the context of parallel computing, recursive definitions of the first kind (no additional parameters in the recursive call) are automatically Embarrassingly Parallel

This sounds to me like a Catamorphism, specifically, a Tree Fold. If you're familiar with the foldr list function of functional programming (I believe Python has this too), this is also a catamorphism.

In general, the categories functions are divided into like this are called recursion schemes. The classic introduction to them is Bananas, Lenses, Envelopes and Barbed Wire. If you're familiar with Haskell, the modern translation guide might help.

Some more information is provided in the Origami Programming paper.


What is the name for the complexity class $O(n^{1+\epsilon})$ Sometimes problems can be solved in $O(n^c)$ time for any $c > 1$, but not for $c=1$. Typically this is written as $O(n^{1 + \epsilon})$, since $\epsilon$ is understood to be some small positive constant. I want to know the terminology for describing this complexity class.

For example, I would call a $\Theta(n)$ algorithm "linear". I would call a $\Theta(n^2)$ algorithms "quadratic". I would call a $\Theta(n \cdot log^c(n))$ algorithm "nearly linear". (Note that nearly linear is better than $O(n^{1+\epsilon})$.)

What do I call algorithms that are in $O(n^{1+\epsilon})$?

The term I've seen in use is superlinear, as in "Are there super-linear time complexity lower bounds for any natural problem in NP?"


Is this definition of a "complete graph" correct? Is it correct to say that:

"A complete graph is a graph in which each vertex is connected to all other vertices in the graph"

That's how I always thought about it, the official definition is different (I know that).

I'm not sure what "official definition" you have in mind but your definition of a complete graph is correct: it implies that every pair of distinct vertices are connected by an edge.

At least, it does assuming that by "connected", you mean "has an edge to". It's best to avoid using the word in that way, since "connected" in graph theory refers to the existence of paths that might be longer than a single edge.


Why not just use FSTs for combining syntactic and semantic analysis? I've just found the finite state transducer.

Since the FST processes two tapes: one for input, one for output,

shouldn't it be possible to use FST to "pack together" some compiler stages, such as Syntactic Analysis and Semantic Analysis.

The FST could take in tokens and output semantically analysed code.

How useful this would be depends on the level of the Chomsky hierarchy at which the transducer operates:

Regular languages:

A Finite State Automaton (FSA) is represented by its transitions (e.g. via a diagram or a list of triples) and the corresponding transducer can be seen as adding an output to each of the transitions.

Hence, the output is at the same 'granularity' as the input alphabet, which may not always be what's desired for associating semantics with syntax.

The issue is not so much with the `redundant (epsilon) outputs' as the possible need to make semantic decisions at the level of sequences of syntactic elements, modeled in regular languages by a (necessarily fairly messy) nested transducer scheme.

Context-free grammars

More usefully than for regular languages, it is possible to use syntax-directed translation which can be seen as a `transducing' scheme associating a semantic output with a grammatical production.


In a single cycle datapath, do 'decode' and 'operand fetch' occur simultaneously? After instruction has been fetched, does it go to control unit and register file at the same time or one after the other?
For example if the control unit and register read both have 80ps delay, and we're calculating the total delay for a cycle, would we take their delay as 80ps(if they occur simultaneously) or if they happen one after the other so in that case delay of decode and operand fetch would be 160ps. Which one is correct?

Figured it out. The control unit and register file are accessed one after the other. So the total delay would be 160ps.


Which CNF boolean formulas blow up exponentially at conversion to DNF? If I'm correct, some boolean formulas in CNF require exponential size when being  converted to an equivalent DNF version (and vice versa).

But what is an example of such a formula (and is there a general way to capture their structure - if the first question is too easy, and I'm just too stupid to see it)?

In this post, the parity function is discussed as an example of a function which blows up exponentially when converted to both CNF and DNF from a non-NF version: Formulas for which any equivalent CNF formula has exponential length

But what about just CNF <=> DNF? And how frequent are these "bad" formulas? (Very rare, I'd suspect, but can it be proved?)

The classical example is
$$(x_1 \lor y_1) \land (x_2 \lor y_2) \land \cdots \land (x_n \lor y_n)$$
which blows up to $2^n$ terms when converted to a DNF.

Most functions have CNF and DNF complexity very large – $\Theta(2^n/n)$ if I remember correctly – and so for random functions there is no blow-up for trivial reasons.

Miltersen, Radhakrishnan and Wegener construct a monotone function which has an exponential gap.


Graph "coloring" problem minimal number, each edge has a colored end (there is the possibility that the answer to my question is "Traveling Salesman, dude!". If that is the case, Please just say so and I'll try it again on my own using Traveling Salesman. We have not covered that in the lecture yet.)

again I am facing homework and thus, would appreciate it, if you did not(!) give me the solution, but helped me to get there on my own.

I've got an exercise to solve and I think, I'm pretty close, but I seem to can't get there.

I've got a graph and have to color the vertices such that the following conditions are met:

-there are two colors (a,b)

-each edge has precisely ONE a-colored vertex

-the number of a-colored vertices is minimal

I've tried to reduce the problem to 2-coloring. BUT:
I don't know how to deal with the condition that the number of a-colored vertices has to be minimal.
I am pretty sure that I can reduce it to a coloring problem, because I also need to show NP-completeness.

Can anyone push me into the right direction?

A valid coloring exists iff the graph is bipartite. In that case, you can divide it into its connected components. Suppose that the $i$th connected component has $x_i$ vertices on one side, and $y_i$ on the other side. Which side would you color $a$?


Is A times B of NP-complete languages A and B necessarily NP-hard? If both $A$ and $B$ are NP-complete languages, would $A \times B$ be necessarily NP-hard? Here, $A \times B = \{\langle u,v \rangle \mid u\in A, v\in B\}$.

So my colleague's answer was no, it's not necessarily NP-hard because you can verify in polynomial time that $u \in A$ and the same for $v \in B$, but you see this is not the case I said, and when I tried to explain why this is wrong, I mumbled and stumbled because I suddenly came to realize that I don't really comprehend the concept to its full depth!

Any way I said if $\langle u,v \rangle$ was not NP-hard to decide, then also would the language $A$ for instance, because you can look at $A\times A$ as a reduction from $A$.

My question is, if I'm right what's my colleague's error and how to explain it, and if I'm wrong which I guess I'm not (this far I do know), then what's wrong about my theory?

Yes, the problem remains NP-hard. Reducing to $A\times A$ doesn't exactly solve the problem, since you want to reduce to $A\times B$.

However, you can proceed as follows: since $B$ is NP-hard, then $B\neq \emptyset$. Thus, there exists $w\in B$. Fix such $w$. We now show that $A\le_p A\times B$: given input $u$, the reduction outputs $\langle u,w \rangle$.

Clearly this can be done in polynomial time, since $w$ is fixed.

Now, since $w\in B$, then $u\in A\iff \langle u,w \rangle\in A\times B$, and we're done.

As for your question "where is my colleague wrong": you can indeed verify in polynomial time whether $\langle u,v \rangle\in A\times B$ if you are given witnesses for the membership of $u\in A$ and for $v\in B$. This shows that $A\times B\in NP$, but it has nothing to do with hardness.

Intuitively, membership in NP is an upper bound on the complexity, whereas NP-hardness is a lower bound.


What are the underlying mechanisms allowing us to unsend an email? I am currently studying Computer Networking, and I was reading about the different types of Application Layer Protocols. In the book I am reading (Computer Networking: A Top-down Approach) it is mentioned that: "Once the client
sends a message into its socket interface, the message is out of the client’s hands and is
“in the hands” of TCP."

For the sake of example, I thought of the option we have of cancelling the emission of an email?
Is this functionality simply implemented via a time-window of seconds before emission or is their an actual procedure I do not know of ?

Do please correct my assumptions as I am afraid I might be off topic on several points

Thank you in advance.

The e-mail system has no way of manipulating already sent e-mails, no.

The only services I've seen which allow you to "unsend" an e-mail simply delay the e-mail being sent for a user-determined amount of time and then allow you to cancel the send before it happens.

Alternatively, I've seen some services allow you to "unsend" e-mails if the recipient is using the same e-mail client as the sender, as both sides are controlled by the same service. Although, once again, this is handled by the service provider, not by the e-mail system itself.


Context free Grammar and regular set I read a question and I don't understand it, is the set consisting of: production rules of Grammars that are CFGs, itself a regular set? The only thing I know is that the type 3 is under the type 2 in CNF.

A context-free grammar is just a string such as "$A\to 0A0\mid 1A1\mid 0\mid 1$".  Forget for the moment that such a string happens to define a language (in this case, the set of all odd-length binary palindromes) and focus on the fact that it's a string over some alphabet.

Now, let $L$ be the set of strings that are regular grammars.  A set of strings is a language.  The question is asking if $L$ is a regular language.


How can you convert the depth of a boolean circuit to its size? I know that the depth of a circuit is the maximal length from an input gate to the output gate of the circuit and its size is its number of gates.
Is there a formula that you can go from depth to size and can someone explain the steps?

First of all, there are several types of (Boolean) circuits:

Circuits with unbounded fan-in. These are circuits with AND, OR, and NOT gates, where the AND and OR gates can have arbitrarily many inputs.
Circuits with bounded fan-in. These are circuits with AND, OR, and NOT gates, where the AND and OR gates have exactly two inputs.
Formulas, which are circuits with bounded fan-in and fan-out. You can think of formulas either as expressions using the operators binary AND, binary OR, and unary NOT, or as circuits with AND, OR, and NOT gates, where the AND and OR gates have exactly two inputs, and the output of each gate is used only once.

(There are even more types of circuits. For example, we could vary the set of gates. But such circuits are less commonly encountered.)
For circuits with unbounded fan-in, not much can be said about the relation between depth and side, since there are depth 1 circuits of arbitrary size.
For circuits with bounded fan-in, we can say that a circuit of depth $d$ has size at most roughly $2^d$. It also has size at least roughly $d$. Both of these are tight: a circuit whose shape is a depth $d$ complete binary tree and whose gates are AND computes the AND of $2^d$ inputs in depth $d$ and size roughly $2^d$, and in contrast, you can construct a "path" (a tree where the left child of every internal node is a leaf) which computes the AND of $d$ inputs in size and depth both roughly $d$.
For formulas you cannot improve on these relations, but you can there is another important property: a formula of size $s$ can always be converted to a formula of size $s^{O(1)}$ and depth $O(\log s)$, an operation we call balancing. It is conjectured that the same cannot be said for circuits (this is one interpretation of the $\mathsf{NC^1}$ vs $\mathsf{P}$ question), though every circuit of size $s$ can be converted to depth $s/\log s$.


Variations of Greedy Algorithm What is the definition of an "orthogonal greedy algorithm"?

What is the definition of a "relaxed greedy algorithms"?

Can you give an example to illustrate how these notions differ from ordinary greedy algorithms?

Wikipedia's article on greedy algorithms says:

  There are a few variations to the greedy algorithm:

  Pure greedy algorithms
  Orthogonal greedy algorithms
  Relaxed greedy algorithms

Wikipedia does not explain further or provide any examples, so it's not clear what the Wikipedia article is referring to.

I have no clue what these various types are. You might want to ask the Wikipedia author who added these types, Wleizero. I can add to the list other types, such as double greedy algorithms, randomized greedy algorithms, reverse delete algorithms, and probably many more.

There are several frameworks for greedy algorithms which might interest you, for example priority algorithms studied by Allan Borodin and his coauthors. However, a laundry list of algorithms does not make a classification. I suggest you just ignore this list of types.


Encoding order relations in CNF I want convert timetable scheduling problems to SAT problems. Suppose there are $t$ time slots and $c$ classes. I will define $t\times c$ variables $x_{ij}$, which is true iff class $j$ takes place in time slot $i$. My problem is: suppose there is a constraint that class $a$ takes place after class $b$. How to encode that efficiently in CNF?

Variable $a_i$ set means class $a$ is in timeslot $i$, with a similar encoding for class $b$.  Higher values of $i$ means later time slots.  If class $a$ must occur before class b then you need clauses to declare that exactly one of $a_i$ or $b_{i+1}$, $b_{i+2}$ ... is set.  You need one such declaration for each $a_i$ possibility.  E.g.

ExactlyOne($a_1, b_2, b_3, b_4, ...$)

ExactlyOne($a_2, b_3, b_4, b_5, ...$)

ExactlyOne($a_3, b_4, b_5, b_6, ...$)

which is efficiently encoded using commander variable encoding as described in Efficient CNF Encoding for Selecting 1 to N Objects.  The scheme requires $O(n)$ clause growth, unlike the naive encoding method which requires $O(n^2)$ clause growth.


Why do i have to show that a problem L $ \in $ NP before i start a polynomial reduction? i want to do a polynomial reduction from the Independent-Set-Problem which is NP-complete to the AUCTION-Problem, to show that AUCTION $\in$ NP-complete,
but why do i always have to show first, that our problem(in this case AUCTION) $ \in $ NP?

Because a problem L is NP-complete if and only if:

L is in NP
L is NP-hard: every problem A in NP can be polynomially reduced to L.

So to show that L is NP-complete, you have to demonstrate both the properties.


Round Robin Scheduling I understand that a big advantage of round robin scheduling over non-preemptive schedulers is that it dramatically improves average response times. By limiting each task to a certain amount of time, the operating system can ensure that it can cycle through all ready tasks, giving each one a chance to run, and the length of the quantum and the number of processes in the run queue.

How do time slice duration and context switching affect each other in a round robin scheduling algorithm?

You're confusing three aspects of scheduling that can be chosen independently: preemptivity, ordering strategy, and time slice duration.

Preemptive vs non-preemptive determines when a context switch may happen. With a non-preemptive scheduler, a task¹ keeps executing until it voluntarily yields the processor back to the operating system², and at this point the operating system may schedule another task. With a preemptive scheduler, the operating system interrupts tasks whenever it wants — interrupting a task is called preemption. In practice, preemption happens when a hardware interrupt is triggered, and one of these interrupts is a timer interrupt that the operating system programs in order to limit how long a task will execute without interruption.

Round-robin is a scheduling strategy (also called scheduling discipline), i.e. a way to decide which task gets scheduled once the current task yields control to the operating system. Most scheduling strategies, including round-robin, make sense whether yielding is voluntary (non-preemptive scheduling) or forced (preemptive scheduling).

Round-robin is a simple strategy where the scheduler maintains a queue of tasks. On a context switch, the task that just stopped goes to the back of the queue, and the task at the front of the queue is resumed. In other words, the next task to execute is the one that has been stopped for the longest time. This strategy is fair³ in the sense that every task gets to execute eventually (no task is starved, waiting forever for CPU time): no task can prevent another task from executing (except in a non-preemptive setting, by never yielding).

Exercise: suppose that tasks can create other tasks. The new task has to be added to the scheduler's queue. Where do you put it?

This description above only considers ready tasks, i.e. tasks that have something to do. If a task is blocked, i.e if it can't do anything because it's waiting for an external event, then the task is removed from the scheduler's queue until it becomes unblocked because that event happened. Tasks become blocked because they're waiting for I/O — either communication with another task or communication with a peripheral.

Where do you put a task when it becomes unblocked? Even if you try to keep a “pure” round-robin scheme, there are several choices. A simple choice is to put the unblocked task at the back of the queue. This choice preserves the fairness property of round-robin. Another choice is to keep all the tasks in the queue, even the blocked ones, but skip over blocked ones when scheduling. This also preserves fairness.

However, schedulers usually deviate from a simple round-robin when it comes to I/O, because round-robin is bad for latency. Scheduling is often a compromise between throughput (getting as much work done as possible in total) and latency (responding to specific events quickly). Throughput is what matters for computational tasks, but I/O tasks often need low latency. If the CPU needs to read data from a peripheral, or to display the next frame of a video, or to send a signal to the brakes because the brake pedal was pressed, then a fast response is needed, and waiting for the task's next turn through a queue may not be acceptable. In practice, schedulers are often round-robin at the core, but with modifications to schedule tasks earlier when they're involved in I/O, in order to reduce latency.

So far I've discussed when preemption occurs and which task gets scheduled next. Time slice duration is another aspect of the scheduling strategy. Time slice duration is another example of a compromise between latency and throughput. Context switching has a cost. If the system performs a lot of context switches, the time spent doing context switches instead of useful work is wasted. To maximize throughput, there must be as few context switches as possible, meaning long time slices. On the other hand, a long time slice means high latency. Scheduling tasks immediately on I/O solves part of the latency aspect, but only part. For example, a video player needs CPU time to prepare for the next frame, even if it doesn't receive many I/O events. Complex schedulers tend to classify tasks as I/O-bound or CPU-bound. CPU-bound tasks get long time slices, but infrequently. I/O-bound get frequent but short time slices. Hardware events can always interrupt a time slice, which makes the interrupted task eligible for a longer time slice later or for an earlier re-schedule. The design space is very large. If you're interested in that, I recommend reading the literature around the Linux kernel in places like LWN, which has several different scheduling strategies (you'd pick a different one for an interactive device, for a networked server or for a number cruncher), with people actively working at improving them and writing up their findings.

¹  or thread. In this context, task and thread are synonymous.
²  In this context, operating system and kernel are synonymous.
³  Note that this is a technical sense of the word “fairness”, which ignores the fact that some tasks may need more time than others. There are many more complex notions of fairness which I won't go into in this answer.


how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$ how proof ${\ \ NPC \ \ \bigcap \ \  CO-NPC   \ne   \varnothing }$  then
${NP = P ?   }$

I don't think you're likely to find any such proof.  Given our current level of knowledge, as far as we know it is possible that $\textsf{P} \ne \textsf{NP}$ but $\textsf{NP} = \textsf{co-NP}$ (we cannot prove otherwise).  If that were true, then we'd have $\textsf{NPC} = \textsf{co-NPC}$ (and thus $\textsf{NPC} \cap \textsf{co-NPC} \ne \emptyset$)  yet $\textsf{P} \ne \textsf{NP}$.

See, e.g., Is the open question NP=co-NP the same as P=NP? and If NP $\neq$ Co-NP then is P $\neq$ NP.


Greedy algorithm for subset sum on powers of 2 I have some $n$ numbers which are powers of $2$, say $a_1,a_2,a_3,\ldots,a_n$ which are not necessarily all distinct. I have option to give them any sign. I have to find if I can make their sum after that equal to num.
I have following algorithm which I am sure will work, by a lot of arguments and verification, but I am not able to prove it:

We sort the array.
Initialize another variable temp to $0$.
We traverse from highest element to lowest element.
If temp>num then subtract $a_i$, else add $a_i$. If in the end temp=num then it's possible to assign signs such that we can make num out the array, otherwise it is not possible.

How to prove that the algorithm works?

You can prove the algorithm using induction. In order to prove by induction, your main statement would be: Let $s_n$ be the (correct) sign of $a_n$ (if it exists), then the algorithm trying to find $s^*_1,\dots,s^*_{n-1}$ such $\sum_{i=1}^{n-1} s^*_ia_i=num-s_na_n$ is correct (by induction assumption). Then, we only need to show that the algorithm chooses $s^*_n=s_n$ and then we would get $\sum_{i=1}^n s^*_ia_i=num-s_na_n+s^*_na_n=num$ as required.
Now the tricky part comes: how can we prove that the $s^*_n$ the algorithm chooses is indeed correct? We want to split this part into two cases:

$num\ge0$, and assume towards contradiction $s_n\neq 1$, i.e only $s_n=-1$ gives a valid solution (there may be multiple solutions, so beware of saying there is only one such $s_n$). Then we need to have $\sum_{i=1}^{n-1}s_ia_i = num+a_n$. Since we are dealing with only powers of $2$, and $a_n$ is the highest value, then there must be some values whose sum (when summed with the appropriate sign) is precisely $a_n$ (and this is because $a_n$ is also a power of 2, if you want a complete proof to this statement, think about the numbers as binary numbers with only one "1" in them and the rest are "0"s), now we can "flip" the sign of those values, and we would get $\sum_{i=1}^{n-1}=num-a_n$ (since their sum is $a_n$, the effect of flipping their sign is like subtructing $2a_n$) and then by choosing $s_n=+1$ we get $\sum_{i=1}^n s_ia_i=num$, in contradiction to our assumption.
$num < 0$, we get that $s^*_n=-1$, and by flipping all of the signs as well as the sign of $num$ we get $s^*_n=1$ for $num>0$, and notice this is the same as the first case.


Programming Symbols : Instance/Instantiation Is there a generally accepted symbol for indicating instantiation. That is indicating an object is an instance of a class.

My first guess is to use a left arrow with a double or triple line but this seems more like a functional programming symbol, based upon what I've seen of Haskell.

Wikipedia has no examples and a quick google for psuedocode mostly turns up simple functional or procedural algorithms. Object Orientated examples don't seem to feature or do not use any specific symbol.

In most contexts, objects are values and classes are types, so I would simply use the colon, representing the "has type" relation:

$Object : Class$

That said, this depends on your context, and whether $:$ carries some other meaning. You could also use $\in$, since you can identify a class with the set of objects that are instances of that class.


transformation of constraint satisfaction to SAT How can any Constraint satisfaction problem be converted to an instance of Satisfiability? I have a CSP and i know its NP hard to solve it, but i would like to convert to an instance of k-SAT, but im not sure of any algorithm for transformation

I'm not sure what you mean by CSP, but suppose that you mean the following: there are $n$ binary variables and $m$ constraints. Each constraint is associated with a $k$-tuple of (distinct) variables, for some $k$ depending on the constraint, along with a subset of $\{0,1\}^k$ which is the allowed assignments for the $k$-tuple of variables.

For example, graph coloring, or rather, whether a given graph $G$ can be $\chi$-colored, can be viewed as a CSP. If there are $n$ vertices (we identify the vertex set with $\{1,\ldots,n\}$) then we have $n$ groups $x_1,\ldots,x_n$ of $\lceil \log_2 \chi \rceil$ variables. For each $i \in \{1,\ldots,n\}$ there is a constraint on each group $x_i$ stating that the assignment for $x_i$ is the binary encoding of a number in the range $\{0,\ldots,\chi-1\}$. For any two connected vertices $(i,j)$ there is a constraint on both groups $x_i,x_j$ stating that $x_i \neq x_j$. This CSP is satisfiable iff $G$ is $\chi$-colorable.

In order to convert such a binary CSP to a SAT instance, we replace each constraint with the corresponding CNF. Continuing the example above, if $\chi = 2$ then for any $i,j$ there is a constraint $x_i \neq x_j$ which we realize as
$$(x_i \lor \lnot x_j) \land (\lnot x_i \lor x_j). $$
The resulting CNF is satisfiable iff the CSP is. You can use the standard reduction to convert this CNF to a 3CNF if you wish.

We can also handle CSPs which are not binary, i.e., in which the variables are not binary but rather have some finite domain. The idea is similar to how I described coloring as a CSP above, and left to the reader.


A Question about what it means to Compare two Vectors Please consider the following question:
Given an integer m by n matrix A and an integer m-vector b, the 0-1 integer programming problem asks whether there exists an integer n-vector x with elements in the set ${ 0, 1 }$ such that $Ax \leq b$. Prove that 0-1 integer programming is
NP-complete.

Am I correct that $Ax$ is a vector, $b$ is a vector and $Ax \leq b$ is true iff every element of $Ax$ is less than or equal to its corresponding element of $b$?

Thanks,
Bob

Yes, element-wise comparison is the usual convention for these constraint problems.


How do cycles of non-consuming transitions in NFAs influence their halting properties? I am in a class that is going over NFAs. The way they are described is a set of states, one of which is the start state, zero or more are accept states, and one or more transitions between them, which consume a symbol of the language or a lambda transition which does not consume a symbol from the string.

One thing that was mentioned is that languages defined by NFAs are regular, and thus can be parsed in constant time (since strings are finite). We then went through the basic pathfinding sort of algorithm where we try paths until we find one that consumes the entire string and if one path completely consumes the string and ends in an accept state - hurray.

Now, if there is a non-consuming transition from one state to itself, or another non-consuming loop in the NFA, that algorithm wouldn't halt.

Are those sorts of loops explicitly forbidden? Is halting not a required property of NFAs? Where is the disconnect in my understanding?

No, the $\lambda$-loops you talk about are not forbidden.  But they do mean one has to be careful.

The actual way to determine if an NFA accepts its input is as follows.  Note that this takes linear time in the length of the input, not constant time as you say in the question.  First, for each state $q$ of the automaton, use a graph reachability algorithm to compute the set of states $\Lambda(q)$ that can be reached from $q$ using only $\lambda$-transitions. For a fixed automaton, with a fixed number of states and fixed transition function, this can be done in constant time. Note that $q\in\Lambda(q)$ for every $q$, since you can reach $q$ from itself by doing some number of $\lambda$-transitions: specifically, that number is zero.  This means that $\lambda$-transitions from a state to itself are completely harmless.

To determine whether the automaton accepts its input, we just keep track of the set of states that the automaton "might" be in after reading each successive character of the input.  Initially, it could be in any state in $\Lambda(q_0)$.  If, after reading some characters, it could be in any state in $S\subseteq Q$ then, when it reads character $a$, it could be in any state in $\Lambda\Big(\bigcup_{s\in Q}\delta(s,a)\Big)$. It accepts if, at the end of the computation, the set of states it might be in includes at least one accepting state.  Note that, at any time, the set of states the automaton could be in is bounded by the fixed constant $|Q|$ so all the manipulations needed on the set of possible states can be done in constant time per character the machine reads, independent of the length of the input.


Find Mapping Node in a Graph Given two large directed graphs (may have loops and lonely nodes) A and B. They are structurally similar.

If we give a node in Graph A, how to find the corresponding one in Graph B?

Finally, we need to find all the node mappings.

Of course, there can be more than one possible mapping. We need to find the similarity (ranking) percentage.

How to design such an algorithm?

The graphs are Control-flow Graphs (Call Graph) extracted from program binaries. However, due to compiler difference (optimization, inline, etc.), the graphs can be a little different.

UPDATE:

To be more clear, as shown in the figure below, we also need to find the matching like B and B',B1' ("->" means a node match):

A -> A'

B -> (B' , B1')

C -> C'

D -> D'

E -> E'

F -> F'

As this is not a sub-graph matching, I cannot find good library APIs or algorithms.

You want to solve the problem of graph isomorphism (GI). GI is not known to be in P or NP-complete; that is, we do not know any efficient algorithms.

Many algorithms have been proposed for GI. None applies to all graphs and is always fast, but you may be able to find one that is sufficiently fast in your application.

In 2015, Babai proposed a quasi-polynomial algorithm for GI [1]. As far as I know, peer-reviewed is not yet completed; I also do not know if it is practically feasible. If correct, it is the most "efficient" algorithm known in terms of Landau-style complexity.

Graph Isomorphism in Quasipolynomial Time by L. Babai (2015) [retraction note]


How to show that a turtle graphic language is not regular? I have to prove with the pumping lemma that $L$ is not regular or to give a regular expression for that.

Let $L$ be all combinations of commands such that in the complete drawn result no line is drawn above another. At the starting point the pen is down.

The turtle graphic is created by the following commands:

u - pen up
d - pen down
g - go
l - move 10° left
r - move 10° right

I think think that the language is not regular because I think there is an expression that crosses a line for a big enough $n \in \mathbb N$.

Question: How can I find an expression that helps me to prove that this language is not regular to use the pumping lemma?

And if the language is regular, what technique should I use to find a regular expression?

The program $g^nr^9gr^9g^mr^9gr^9g$ crosses a line iff $n \geq m$.


Why is Hamming Weight (in the CRC context) independent from the data? I'm designing a communication protocol for 24 to 52 bits (typically 32 bits) data including the CRC-8 for error detection. I'm trying to select the best polynomial for this kind of application.

In the paper Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks Koopman, et. al. gives a very nice method to select a CRC polynomial depending on the needs of the application. The paper proposes that if Hamming Distance of two or more polynomials are equal, select the minimum Hamming Weight for a given bit length and error bits. Also Koopman kindly makes all these calculations and information publicly available in his site: http://users.ece.cmu.edu/~koopman/crc/index.html

As he also suggests "Don’t blindly trust what you hear on this topic", I've also verified his results for some of the 8-bit CRC polynomials using my own software. But here is what I failed to understand:

In the paper 32-Bit Cyclic Redundancy Codes for Internet Applications he defines the Hamming Weight as

  A weight $W_i$ is the number of occurrences of a combination of $i$ error bits, including bit errors perturbing the CRC value, that would be undetected by a given polynomial for a given data word length.

Also, he explains why the Hamming Weight is independent from the data as follows:

  Consider the fact that a data corruption is undetectable if and only if it transforms one codeword (some payload with its valid FCS value) into a different valid codeword.  But because CRCs are linear, this means that the faulty bits that have  been  flipped  from  the  original  codeword  have  to themselves form a valid codeword. (In other words, the bits flipped in the message payload have to be compensated for by bits flipped in the FCS field, and the only way this can happen is if the entire set of bits flipped is itself a valid codeword.) This means that the actual data in a message payload is irrelevant in computing error detection abilities, which simplifies things greatly.

I also tried to calculate the Hamming Weight for different data and indeed obtained the same results. But I don't understand why this is the case. A rigorous proof or any different insights are greatly appreciated.

Edit: The example for Hamming weight given in the paper:

Suppose we have a codeword of length 12144 bits. So we have

$$ \pmatrix{12144 \\ 4} = \frac{12144!}{12140! ~ 4!} = 906 \times 10^{12} $$

possible bit errors. Hamming Weight is the number of undetected 4 bits error out of all possible 4 bits errors. So it is calculated for 802.3 CRC polynomial to be $W_4 = 223059$. This means $223059$ of $906 \times 10^{12}$ errors go undetected and this number does not change with the used codeword.

Let us call a data vector of some fixed length together with its CRC a codeword. Since CRC is a linear code, the set of codewords is closed under XOR (this is the definition of linear code).

Let $x$ be a codeword, and suppose that $y$ is a noisy version of $x$ which is also a codeword. Since CRC is linear, $x \oplus y$ is also a codeword. If $D$ is the minimum Hamming weight of a non-zero vector in the code, then the Hamming weight of $x \oplus y$ is at least $D$, that is, $y$ differs from $x$ in at least $D$ positions. This shows that at least $D$ errors need to occur in order for the errors to go undetected.

Conversely, let $w$ be a codeword of Hamming weight $D$. Then $y = x \oplus w$ is another codeword which differs from $x$ in $D$ positions. That is, $D$ errors (in appropriate locations) are enough for an error to go undetected starting from $x$. Note that $x$ here is completely arbitrary. This is why the minimum number of errors is independent of the data.


How do you prove these string/number radix encoding/decoding algorithms work? A while back I learned of these great algorithms:
function parseInt(value, code) {
  let x = 0
  let i = 0
  while (i < value.length) {
    const a = value[i]
    x = x * code.length + code.indexOf(a)
    i++
  }
  return x
}

function toString(value, code) {
  const radix = code.length
  let result = ''

  do {
    const digit = value % radix
    result = code[digit] + result
    value = Math.floor(value / radix)
  } while (value)

  return result
}

which allow you to convert toString any (albeit 32-bit) number to a string using a custom "alphabet" or "code", and do the reverse and parse a corresponding string to int.
console.log(parseInt('dj', 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// 123
console.log(toString(123, 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// dj
console.log(parseInt('a', 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// 0
console.log(toString(0, 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// a

How do you prove that these algorithms actually do the trick? What does the proof look like from base principles? Tangent/bonus: How would you ever go about figuring this out from scratch? To me this is pure magic and I would never have been able to figure this out "from scratch". I would like to know what I could've done to figure this out using mathematical techniques/principles.

First, you need to figure out what it is you want to prove. Here, I'd say we want to prove that
toString(parseInt(x, code),code) = x
and
parseInt(toString(x, code),code) = x
It's pretty obvious that trying to prove this is going to fail if:

we overflow the result in parseInt, because then parseInt isn't surjective
the input in parseInt contains characters that aren't in the code

So, our proof has to include the assumption that both are not the case.
The first proof is probably easier than the second. We can do induction on the length of `value':
toString(parseInt(x, code),code) = x
Given an arbitrary code which contains all characters in x
If x.length == 0:

x == ''
parseInt(x, code) returns 0
toString(0, code) returns ''  <- actually it returns 'a' so the proof breaks here, but you can do the same if you assume length 1

If x.length > 1

our induction hypothesis: for all prefixes y of x toString(parseInt(y, code),code) = y
parseInt(x, code) = parseInt(x[:-1], code) * code.length + code.indexOf(x[-1])   (I am using python syntax here to say everything but the last element, and the last element. This in and of itself would have to be proved I guess but it would be very easy if the algorithm was written recursively instead of iteratively)
toString(a * code.length + b, code) = code[b] + toString(a, code)  (again, this would be straightforward if the algorithm was recursive, but it should be convincing enough that this is the case here)
that means toString(parseInt(x,code),code) = toString(parseInt(x[:-1], code) * code.length + code.indexOf(x[-1]), code) = code[code.indexOf(x[-1])] + toString(parseInt(x[:-1], code), code) = (using induction hypothesis) x[-1] + x[:-1] which breaks our proof because toString has a bug and inverts the string, as far as I can tell.

Assuming the line result = code[digit] + result actually read result = result + code[digit] like I think it should:

toString(a * code.length + b, code) = toString(a, code) + code[b]  (again, this would be straightforward if the algorithm was recursive, but it should be convincing enough that this is the case here)
that means toString(parseInt(x,code),code) = toString(parseInt(x[:-1], code) * code.length + code.indexOf(x[-1]), code) = toString(parseInt(x[:-1], code), code) + code[code.indexOf(x[-1])] = (using induction hypothesis) x[:-1] + x[-1] = x

QED.
The other direction is similar, you can again use induction as long as you take care that your induction hypothesis is "for all y < x: parseInt(toString(y, code),code) = y".


What is the worst case running time for an algorithm that combines insertionsort and mergesort? Suppose that we have an algorithm "combination" that uses insertionsort for $n < 100$ and mergesort for $n \geq 100$. Is the worst case running time of "combination" then $n^2$ or $n\log n$?

I was thinking that it's simply $n^2$, since the algorithm "combination" allows inputs larger than 100, in which case the worst case running time is $n^2$.

In fact, the running time of mergesort for large $n$ doesn't depend on what happens for small $n$. Recall the recurrence for mergesort:

$$ T(n) = 2T(n/2) + O(n), \qquad T(1) = O(1). $$

This recurrence holds even if you run insertion sort for $n < 100$, since the running time of insertion sort on at most 100 elements can be swallowed in the big O constants. Even if you use exhaustive search on all $n!$ permutations for $n < 100$, mergesort will still run in time $O(n\log n)$; the only change is that the big O constant would be rather huge.


Is there a Context-free grammar for this language? Is there a Context-free grammar for the following language:

$L=\{ x\#1^m|x \in \{0,1\}^* \text{ and the $m^{\text{th}}$ char in $x$ is 1} \}$

If so what is it? Because i couldn't find any. I also tried to prove there isn't (by the Pumping lemma for context-free languages), but it's given that a Context-free grammar does exist and I found an error in my "proof".

So what would be the grammar?

Here's the big picture of my proof:

Let's choose $m=n_0$ and take the word $w=0^{n_0}1\#1^{n_0+1}$ (so that $x$ is what's on the left side of $\#$) .

According to the lemma, $w$ can be written as $uvxyz$ and some conditions hold...

$|vxy| \leq n_0$

therefor, $vxy$ include only zeros ($0$'s).

Now let's choose k=2 and pump it up:

we get: $w_2=uv^2xy^2z$

which means, the number of $0$'s is now:

$n_0 + |v| + |y| \geq n_0 + 1$

(since $|vy| \geq 1$) .

Hence, the $m$th number (the $n_0$th in our case) is not $1$. It's actually $0$.

Hence, $w_2$ doesn't belong to $L$. Contradiction.

Hence, $L$ isn't Context-free.

I think i know where's my mistake in the proof:

$vxy$ isn't necessarily only $0$'s. It could have the last $n_0-1$ zero's and a $1$.

Here is a PDA for this language. While reading $x$, the whole of $x$ is pushed onto the stack. After encountering $\#$, the PDA pops some non-deterministic amount of symbols, then verifies that the top symbol is $1$, and pops $m$ symbols. It acceptes if the stack is empty.

Variant: instead of popping a part of $x$, while reading $x$ the PDA non-deterministically stops pushing symbols into the stack; it only does so after reading a $1$.

As for a CFG for this language, here is the idea:
$$
\begin{align*}
&S \to \Sigma^{m-1} 1 T 1^m \\
&T \to \Sigma^* \#
\end{align*}
$$

I'll let you construct an actual grammar based on this idea.


Floating point bitwise comparator. If f1 and f2 are floating point numbers with the following properties can we always say f1 > f2? Recall floating-point representation:
Suppose $f$ is a floating-point number then we can express f as,
If $f$ is normal:
$$(-1)^{s}\cdot2^{e-127}(1 + \sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k})$$
If $f$ is denormal/subnormal: $(e = 0)$
$$(-1)^{s}\cdot2^{-126}(0 + \sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k})$$
where

$s$ is the sign of $f$.
$e$ is the stored exponent of $f$. This means $e-127$ is the effective exponent of $f$.
$b_k$ is the $k$-th bit of $f$ where $b_0$ is the LSB and $b_{22}$ is the MSB.

Let $f_1$ be a floating-point number with constants $s_1, e_1,$ and $b_{1k}$.
Let $f_2$ be a floating-point number with constants $s_2, e_2,$ and $b_{2k}$.
I'm trying to find out if the following statement is true: $e_1 > e_2 > 0$ and $s_1 = s_1$ then $f_1 > f_2$.
My initial strategy was to subtract $f_2$ from $f_1$ and show that it must be strictly greater than $0$.
What I have so far.
$
\begin{align*}
f_1-f_2 &= 2^{e_1-127}(1 + \sum\limits_{k=1}^{23} b_{1,23-k}\cdot 2^{-k}) - 2^{e_2-127}(1 + \sum\limits_{k=1}^{23} b_{2,23-k}\cdot 2^{-k})\\
&= 2^{-127}(2^{e_1}(1 + \sum\limits_{k=1}^{23} b_{1,23-k}\cdot 2^{-k}) - 2^{e_2}(1 + \sum\limits_{k=1}^{23} b_{2,23-k}\cdot 2^{-k})) \\
&= 2^{-127}(2^{e_1} + \sum\limits_{k=1}^{23} b_{1,23-k}\cdot 2^{e_1-k} - 2^{e_2} - \sum\limits_{k=1}^{23} b_{2,23-k}\cdot 2^{e_2-k})\\
&=2^{-127}(2^{e_1} - 2^{e_2} + \sum\limits_{k=1}^{23} b_{1,23-k}\cdot 2^{e_1-k} - \sum\limits_{k=1}^{23} b_{2,23-k}\cdot 2^{e_2-k})\\
&=2^{-127}(2^{e_1} - 2^{e_2} + \sum\limits_{k=1}^{23}(b_{1,23-k}\cdot 2^{e_1-k}-b_{2,23-k}\cdot 2^{e_2-k}))
\end{align*}
$
Now since $e_1 > e_2 \iff e_1-e_2 > 0 \iff 2^{e_1}-2^{e_2} > 1$ we have that:
$
\begin{align*}
f_1-f_2 & > 2^{-127}(1 + \sum\limits_{k=1}^{23}(b_{1,23-k}\cdot 2^{e_1-k}-b_{2,23-k}\cdot 2^{e_2-k}))
\end{align*}
$
In order for the above to always be greater than zero I require that $\sum\limits_{k=1}^{23}(b_{1,23-k}\cdot 2^{e_1-k}-b_{2,23-k}\cdot 2^{e_2-k}) > -1$.
However, I don't know how to formally show this. Any help/hints are much appreciated as inequalities are not my strong suit.

If we study the expression for a floating point number, $$(-1)^{s}\cdot2^{e-127}(1 + \sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k}),$$
and pay attention to the sum $\sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k}$, we note that
$$0 \leq \sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k} \leq \sum\limits_{k=1}^{23} 2^{-k} < \sum\limits_{k=1}^\infty 2^{-k} = 1,$$
where the last equality is formed by evaluating the geometric series. Thus we find that
$$2^{e-127} \leq2^{e-127}(1 + \sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k}) < 2^{e-127}\cdot 2$$
Thus if $s = 0$ and $e_1 > e_2$ we find that $f_2 < 2^{e_2 - 127} \cdot 2 \leq 2^{e_1 - 127} \leq f_1$.
Note that if $s = 1$ and $e_1 > e_2$, the signs are reversed and we actually have $f_2 > f_1$. But always $|f_1| > |f_2|$.

The extended result of the above is that if we ignore the effects of denormal numbers, NaNs, infinities and say that $-0 < 0$, we have
$$f_1 < f_2 \iff n_1 < n_2,$$
where $n_1, n_2$ are the bit patterns of $f_1, f_2$ interpreted as $w$-bit two's complement integers.


Data structure for efficient searching, when insertions and removals are only one-sided I need a data structure for storing a number $n$ of elements, each of whom is associated with some different time $t_i$. $n$ varies and while it has a theoretical upper limit, this is many orders of magnitude larger than what is typically used.

Through my application I can ensure that:

Inserted elements are always newer than all existing elements, i.e., if an element associated with a time $\check{t}$ is inserted, then $\check{t}>t_i ∀ i ∈ {1,…,n}$. Elements are inserted one by one.
Only the oldest elements are removed, i.e., if element $j$ is removed, then $t_j < t_i ~∀ i ∈ \lbrace 1,…,n \rbrace \setminus \lbrace j \rbrace$. Removals happen mostly one by one, but there is no direct harm if an element’s removal is delayed, as long as the fraction of spuriously stored elements remains smaller than 1.
Apart from inserting and removing, the only thing I need to do is find the two neighbouring elements for some given time $\tilde{t}$ with $\min\limits_i t_i < \tilde{t} < \max\limits_{i} t_i$. With other words I need to find the two elements $j$ and $k$ such that $t_j<\tilde{t}<t_k$ and $∄ l ∈ \{1,…,n\}: t_j<t_l<t_k$.

My criteria for the data structure are:

Finding elements as described above should be as quick as possible.
Inserting and removing should be quick.
The data structure is comparably simple to implement.

As long as we are not talking about a small runtime offset, each criterion has priority over the next.

My research so far has yielded that the answer is likely some kind of self-balancing search tree, but I failed to find any information which of them is best for the case of one-sided inserting or deleting, and it will probably cost me a considerable time to find out myself.
Also, I only found incomplete information about how well the trees self-organise and how quickly (e.g., AVL trees self-organise more rigidly than red-black trees), let alone how this is affected by one-sided inserting or deleting.

Store the elements as a sequence, sorted by increasing timestamp.  Use binary search to find the location where $\tilde{t}$ would occur if it were in the array; then you can easily find the two neighboring elements.  Finding the two neighboring elements can be done in $O(\lg n)$ time.

You'll also need to be able to append to the end of the sequence and delete from the beginning.  Thus, basically you need a queue.

There are standard constructions for a queue.  For instance, you can store them in an array, with amortized $O(1)$-time insert and delete operations.  Basically, you have an array for the elements of the sequence, and a start index (for the beginning of the sequence) and an end index (for the end of the sequence).  To delete from the beginning, increment the start index.  To add to the end, increment the end index; if this runs past the end of the existing array, allocate a new array of double the size and copy into the new array.

Alternatively: you can store the elements in a balanced binary tree.  This will achieve worst-case $O(\lg n)$-time for all operations.


Finding triples that satisfy given constraints in $O (n \log n) $ time Given a string comprised solely of the characters $\text{a, b, c}$ we want to know the number of different $(i, j, k)$ triples such that $0 \leq i,j, k < n \text{ (here n denotes the length of the string)}$ satisfying the following two conditios :

  $\bullet \text{ }s[i] = "a", s[j] ="b" \text{ and } s[k] = "c"$

  $\bullet \text{ } (j + 1)^2 = (i+1)(k + 1) $

  We consider such two tuples, $(i, j, k)$ and $(x, y, z)$ to be different only of $i \neq x$ or $j \neq y$ or $k \neq z$.

  Example case and solution :
  The string $"ccaccbbbaccccca"$ with $n = 15$.
  There are two triplets that satisfy the given constraints, namely $(2, 5, 11)$ and $(8, 5, 3)$.

  The second solution shows that $i$ is not necessarily less than $k$.

I know this is a programming question, but I'm more inclined to look for a mathematical approach that I currently seem to be missing. Since $n$ could be as large as $5 \cdot 10^5$ brute force is not feasible.

I've attempted coming by the solution by noticing that in order for $\sqrt{(i + 1)(k + 1) } = (j +1 ) \in \mathbb{N}$, $k +1$ should be of the form $(i + 1) \cdot \alpha^2$ or of the form $\frac{\alpha^2}{i + 1}$.

Hence, we would have to iterate and test in order to find the $
\alpha$ values that would satisfy our conditions. Later on, I found out by inspecting the process that the latter form covers all the solutions, multiple times, so I would only need to look for answers by using the second form.

This still led to a temporal complexity of $O(\sqrt{n} \cdot \sum_{k=1}^{n}\sqrt{k})$.

I've been at this for too many hours and I have no idea how to proceed. How would you solve this?
I'm guessing $O(n)$ isn't possible but $O(n \log n)$ should probably do the trick.

Let us shift all of your indices by $1$. The condition on the indices then becomes $j^2 = ik$. The number of factorizations of $j^2$ into $i \cdot k$ is at most $d(j)^2$, where $d(j)$ is the number of divisors of $j$.  Therefore the total number of potential triples $(i,j,k)$ is at most
$$
\sum_{j=1}^n d(j)^2 = O(n\log^3 n).
$$
(For the estimate, see this question on Mathoverflow.) Note that the actual number of triples can also be bounded by $\sum_{j=1}^n d(j^2)$, which could be smaller (and it could be yet smaller even than this sum).

This means, at the very least, that if you know $n$ in advance, then you can make a list of $\tilde{O}(n)$ triples, and solve the problem in time $\tilde{O}(n)$. Using a sieve of Eratosthenes, you can likely also calculate the triples in $\tilde{O}(n)$; it might be worthwhile to store all primes at most $500,000$ ahead of time.


Identify similar functions I was wondering if there is any technique in order to recognize similar functions behaviour. In particular, suppose that I implement two functions $f$ and $g$ in a certain programming language $P$ and for each input $i$, $f(i) = g(i)$. Moreover, the two functions $f$ and $g$ could be implemented in a completely different way, e.g. different algorithms that solve the same problem.

In my opinion, clone detection could be useful, but I cannot compare both tokens or ASTs since the implementations are completely different. A semantic comparison could be a possible solution, but are there other techniques that I can use?

The problem is not decidable (by reduction from the Halting problem), so there is no perfect algorithm that always terminates and always gives the correct answer.  Therefore, you'll need to make some tradeoffs.  That will depend on the specifics of your particular application, so it's hard to recommend a particular technique without knowing how you plan to use it.


Why doesn't $O(1)+O(2)+\cdots+O(n)$ have an interpretation? In CLRS (on pages 49-50), what is the meaning of the following statement:

  $\Sigma_{i=1}^{n} O(i)$ is only a single anonymous function (of $i$), but is not the same as $O(1)+O(2)+\cdots+O(n)$, which doesn't really have an interpretation."

Since $1+2+\dots+n =O(n^2)$, it is tempting to suggest that $O(1)+O(2)+\dots+O(n) = O(n^2)$ ... but this is not in fact valid.  The reason is that there might a different constant for each term in the sum.

An example

Let me give an example.  Consider the sums $S(1) = 1^2$, $S(2) = 1^2 + 2^2$, $S(3) = 1^2 + 2^2 + 3^2$, $S(4) = 1^2 + 2^2 + 3^2 + 4^2$, and so on.  Note that $1^2 \in O(1)$, $2^2 \in O(2)$, $3^2 \in O(3)$, $4^2 \in O(4)$, and so on for each term in the sum.  Therefore, it would be reasonable to write $S(j)=1^2 + \dots + j^2$ in the form $S(j) = O(1) + \dots + O(j)$.  So can we conclude that $S(j) = O(j^2)$?  Nope.  In fact, $S(n) = n(n+1)(2n+1)/6$, so $S(n) = \Theta(n^3)$.

If that doesn't help, let's try the following more precise mathematical development:

A formalization

Recall that the interpretation of, say, $O(n^2)$ is that it is a set of non-negative functions $f(n)$ (namely, the set of functions $f(n)$ such that there exists constants $c \ge 0, d\ge 0$ such that $f(n) \le c \cdot n^2$ for all $n\ge d$).

The closest we can come to an interpretation of $O(1) + O(2) + \dots + O(n)$ is that it is the set of functions of the form $f_1(n) + f_2(n) + \dots + f_n(n)$ such that $f_1(n) \in O(1)$, $f_2(n) \in O(2)$, ..., $f_n(n) \in O(n)$.

But now the constants for each $f_i$ can be different.  Thus, each $f_i$ is a non-negative function $f_i$ such that there exist constants $c_i\ge 0,d_i \ge 0$ with $f_i(n) \le c_i \cdot i$ for all $n \ge d_i$.

Now, given this, what can we say about $g(n) = f_1(n) + f_2(n) + \dots + f_n(n)$?  Not much useful.  We know that there exists a constant $d=\max(d_1,d_2,\dots,d_n)$ such that $g(n) \le c_1 \cdot 1 + c_2 \cdot 2 + \dots + c_n \cdot n$ for all $n\ge d$.  Now what can we say about this sum?  Well, the answer is that we can't say anything at all.  It could be arbitrarily large.  It is tempting to let $c=\max(c_1,c_2,\dots,c_n)$ and say that $g(n) \le c \cdot (1+2+\dots+n) \le c \cdot n^2 = O(n^2)$... but this is not actually correct, since we need a single constant value of $c$ that works for all $n$, and the value $\max(c_1,c_2,\dots,c_n)$ is a function of $n$, not a constant.

So there might not be any constant $c$ such that $g(n) \le c \cdot (1+2+\dots+n)$; there might not be any constant $c$ such that $g(n) \le c \cdot n^2$.  There is no guarantee that $g(n) \in O(n^2)$.

For more reading

See https://math.stackexchange.com/q/86076/14578 and Sums of Landau terms revisited for other questions that deal with this general issue.


Ternary Search Recurrence Relation I am trying to work out the recurrence relation for Ternary Search. This is what I came up with:

C(n) = C(n/3) + 2

However, I talked to my professor and he said it's not correct. He says that we need to take all of their cases into account. This part confuses me a little bit, can you please clear it for me?

Thank you.

Hint: Recall what you are actually doing in ternary search - you basically partition the list into 2 parts, on of roughly $n/3$ elements, and the other of $2n/3$ elements.

So, on a bad day (worst case) you do $2n/3$ recursive calls.

Then the recurrence relation is $$T(n) = T(2n/3) + c $$

I'll cheat a bit here and use the master theorem to jump to the conclusion that $T(n) \in \Theta(log\ n)$


Reducing recursive languages I need a clarification related to the following situation.

Consider a Turing machine $T_1$ that halts for every input. In other words $J_1 = L(T_1) \subseteq \Sigma^*$ is recursive. Suppose we are given a function $f:\Sigma^* \mapsto \Sigma^*$ and a language $J_2 \in \Sigma^*$ such that $$ x \in J_2 \iff f(x) \in J_1.$$

I would assume this readily implies $J_2$ is recursive as well since one can create a Turing machine $T_2$ that on given input $x$ evaluates $y = f(x)$ and simulates $T_2$ on the given input $y.$ Clearly $L(T_2) = J_2.$

What now confuses me is the following.

  Are there any restrictions on $f$ for this ''reduction'' to work?

What is the usual approach here? Is $f$ assumed to be given as a black box that always evaluates $f(x)?$ If so could someone explain the motivation behind this, because it appears to me that it could as well be that $f(x)$ cannot be computed effectively and hence $T_2$ cannot be constructed in a "feasible" way.

As for the motivation for the question, I would like to show that given $f:\Sigma^* \mapsto \Sigma^*$ and a recursive language $L,$ the language $f^{-1}(L)$ is recursive as well.

Reductions are about translating one problem to another. In our case, we reduce the question "$x \in J_2$" to the question "$f(x) \in J_1$". Naturally, for this to make any sense $f$ has to be computable (otherwise we can reduce anything to anything). But it is also important to pay attention to the totality of $f$.

We normally require that $f$ be total because we do not want to be in a position when the reduction itself never ends. In this case, if $f$ is computable and total, and $J_1$ is computable, then $J_2 = f^{-1}(J_1)$ is computable as well.

Allowing $f$ to be partial might make sense when we are interested in semi-deciding whether $x \in J_2$ because then we might as well allow $f(x)$ to diverge when $x \not\in J_2$. But this is not usualy done.


Line-search does not guarantee convergence so how to use it? Line-search/backtracking in gradient descent methods essentially boils down to picking the current estimate $\theta_n$ (which depends on the stepsize $\gamma$ and the prior estimate $\theta_{n-1}$) by performing line-search and finding the appropiate $\gamma$.

This search depends on a 'sufficient descent' criterion.

It can happen that the sufficient descent criterion simply is not going to be satisfied for any reasonable $\gamma$. That is, you are at a part in your search for the optimal point where no matter how small a step-size you take, you are not getting sufficient descent.

Here, line-search would get stuck in an infinite loop (or, a near-infinite loop: the sufficient descent criterion might be satisfied eventually due to numerical errors)

So, how should this be fixed? One option is to omit line-search completely: fixing $\gamma$ to be a constant, you will eventually converge if $\gamma$ is small enough.

A second option is to do line-search for an optimal $\gamma$, but only for a small amount of time (say, 20 iterations). If you haven't found a optimal $\gamma$ by then, then just take any fixed step and hope you get back towards convergence.

What do people do?

First of all, if we have a descent direction, we can always find a step size $\tau$ that is arbitrary small, such that "the sufficient descent criterion" is satisfied (see the Wikipedia article 'Backtracking line search'). This essentially rules out the infinite loop issue.
For example, consider Armijo condition as "the sufficient descent criterion", which is
$$
f(\bar{x}+\tau d) \leq f(\bar{x})+\gamma \tau\langle\nabla f(\bar{x}), d\rangle
$$
for $\gamma \in (0,1)$ and where $d$ satisfies $\langle\nabla f(\bar{x}), d\rangle < 0$.
If the function is twice differentiable, we can consider its Taylor expansion around the current iterate $x_k$ and show that as $\tau \to 0$, the Armijo condition is satisfied. However the step size could be arbitrarily small, when we consider the backtracking algorithm. To prevent this, we impose additional constraints on the step size, that prevent $\tau$ from being too small, while preserving the guarantee that such a step size still exists. For further details, you can check the Wikipedia article above.


Simple proof for NP-completeness of Edge Dominating Set In a graph, an edge dominating set is a subset D of the edges such that any edge in the graph is either in D, or shares an endpoint with an edge in D.
The Minimum Edge Dominating Set problem is to find an edge dominating set
of minimum cardinality. The decision version of this problem is known to be NP-complete, but I would like to inquire whether a relatively simple proof of this fact is known.

The only proof I found in the literature  is in the paper that first tackled this problem, by Gavril and Yannakakis. However, the above proof makes use of the fact that Vertex Cover is NP-complete for planar cubic graphs, and the fact that bipartite graphs of degree d can be d-edge-colored. I would prefer a simpler proof, that would only make use of facts typically known to undergraduates who took an algorithms course.

I assume that you only want to show the minimum edge dominating set problem is NP-complete for the general graph (i.e., you don't care about what properties the constructed graph has).

In case you missed it, there is an arguably simpler reduction from 3-SAT in the same paper (see Theorem 2). The reduction assumes no further "specialist" knowledge. You can make the presentation even slightly easier by skipping verification of bipartiteness and boundedness of the maximum degree of the resulting graph.


TM that finds the middle of an input string in O(n) time Is it possible to find a TM with O(n) complexity that finds the middle of an input string?
Or at least to prove that it cannot be done?

I can use a two-taped TM if it helps.

With a two tape TM it is not difficult:

Move to the right on the input tape. Every second step write something to the secondary tape. Once you reach a blank on the input tape (i.e. the end of the input), start moving to the left on the input tape. Each step delete a symbol from the secondary tape. You have reached the middle if the second tape is empty.


Estimating P in Amdahl's Law theoretically and in practice In parallel computing, Amdahl's law is mainly used to predict the theoretical maximum speedup for program processing using multiple processors. If we denote the speed up by S then Amdahl’s law is given by the formula:

S=1/((1-P)+(P/N)

where P is the proportion of a system or program that can be made parallel, and 1-P is the proportion that remains serial. My question is: how can we compute or estimate P for a given program?

More specifically, my question has two parts:

How can we compute P theoretically?
How can we compute P in practice?

reference: https://www.techopedia.com/definition/17035/amdahls-law

Amdahl divided a program in two parts, serial and parallel, and assumed each processor to have same compute ability. This concept has been further refined by Hill and Marty Amdahl's law in multi-core era, in other words it is not necessary that every processor should have same the compute ability and Cassidy Beyond Amdahl's Law: An Objective Function That Links Multiprocessor Performance Gains to Delay and Energy, in other words why divide in only two parts.

After a brief overview of Amdahl's law, I answer the question how to measure the serial (1-P) and parallel (P) parts of a program.

Static instrumentation: Put a function that gives the current time like gettimeofday in Linux at the start of the program, the point where you create threads and points where you join threads and if necessary (if your program does a lot of post processing) at the end of program. Take differences and you will have the P value. Use the single threaded program. If you want to have more precision in measurement use the rdtscp instruction on Intel processors Excellent blog by Dr. John McCalpin.
Dynamic instrumentation: It is possible to do the above even when you don't have the source code to do static instrumentation. You can use library preloading (LD_PRELOAD) or the Intel Pin tool Introduction to Pin using examples or similar dynamic binary instrumentation tools like Dynamorio, Valgrind and Linux perf Tutorial by Brendan gregg. All of them are established frameworks, completely free, with multiple research tools using them.


How to find subset of vectors whose sum has certain characteristics Let's say you have list of $n$ vectors with entries from $\{0,1,x\}$ and $x$ is > $n$:

$$
\begin{align*}
L_0 &= [1,0,x] \\
L_1 &= [1,1,1] \\
L_2 &= [1,0,0] \\
L_3 &= [x,1,0] \\
L_4 &= [1,x,0]
\end{align*}
$$

I want to find all combinations of $m$ vectors (subsets of vectors from this list) whose elementwise sum in this combination will have exactly $m$ occurrences of $x$.  Is there an algorithm to do this in less than $O(m^n)$ time?

In my example, if $m=2$, the only valid combination is $L_0 + L_4 = [1+1, 0+x, x+0] = [2, x, x]$.  If $m=1$, valid answer is [$L_0$, $L_3$, $L_4$].

Key is: are there's any way to solve this problem without iterating over all $m^n$ combinations.

This might sound like an interview question, but in fact it is a task that I reduced my problem to.

The question has changed.  I'll answer the updated question.  Here are three candidate algorithms; the first is faster than $O(m^n)$ time, and the second might be faster as well for some parameter values.  I will assume that the vectors are from $\mathbb{R}^d$, i.e., $d$-dimensional vectors (in  your example $d=3$).

Try all subsets

There are exactly ${n \choose m}$ subsets of $m$ vectors.  You can try each, compute what its sum is, and count how many $x$'s it has.  The running time will be $O(nd \cdot {n \choose m})$, and can be optimized to run in time $O(d \cdot {n \choose m})$.  Note that ${n \choose m} \le 2^n$ and can be significantly smaller than $m^n$, so if we ignore the dependence on $d$, this is faster than your $O(m^n)$ time to beat.

Try all target vectors

Alternatively, we can try all possibilities for which $m$ locations (coordinates) in the sum contain a $x$.  There are ${d \choose m}$ such possibilities.  For each, we will try to find a subset of the input list whose sum has a $x$ in those special locations (coordinates), and no $x$ in any other location (coordinate).  We'll temporarily ignore the requirement to have a subset of size exactly $m$.

Note that any valid solution must use only vectors that whose special coordinates all have entries from $\{0,x\}$ (in particular, no special coordinate can contain a $1$).  (Any vector with a $1$ in any special coordinate can't be included in any valid combination; if it were included, the sum in that coordinate would be either $\ge x+1$ or $\le n$, according to whether we include any other vector with a $x$ in that coordinate or not.)

So, let's focus only on those $m$ coordinates, and ignore (throw away) all the others.  In this way each $d$-vector is reduced to a $m$-vector.  Then, we look for a subset of the input vectors that sums to the $m$-vector $[x,x,\dots,x]$.  This is a multi-dimensional subset-sum problem.  This particular subset-sum problem has a special form: it turns out to be an instance of the  exact cover problem, and can be solved with standard algorithms for exact cover.  The running time will be exponential in $m$.  So, we'll solve the exact cover problem in $m$ dimensions, and then check each solution to see whether it is a valid solution to the original problem.

We repeat this ${d \choose m}$ times (once for each subset of $m$ coordinates).  The running time to solve each instance of the $m$-dimensional exact cover problem is exponential in $m$, and we must solve ${d \choose m}$ of them, so the running time will be something in the vicinity of $O({d \choose m} \cdot 2^m)$.

Alternatively, given a target vector (a set of $m$ special coordinates), we could use integer linear programming to search for a subset of $m$ of the input vectors that sum to $[x,x,\dots,x]$ in those $m$ coordinates.  This will again take time exponential in $m$, in the worst case, for each target vector, though in practice it might be faster.  One nice thing about integer linear programming is that it lets you directly express the constraint that the subset must be of size $m$.  Also, it may be fairly easy to implement this approach using an off-the-shelf ILP solver.

This algorithmic approach may be better or worse than the other schemes, depending on the values of $m,d$.  If $m$ is very small or very close to $d$, this approach may be an improvement on the others.

Dynamic programming

There is a dynamic-programming algorithm whose running time is $O(nd  \cdot 3^d)$.  Basically, we have a table that keeps track of which $d$-dimensional vectors can be expressed as a sum of some subset of the input vectors.

Given an entry of a vector, we'll classify into one of three categories: $0$ (meaning the entry is $0$), $☹$  (meaning the entry is not $0$ and not $x$), and $x$ (meaning the entry is $x$).  These have the obvious addition rules, e.g., $☹ + x = ☹$, $☹ + ☹ = ☹$, and so on.  Thus, each vector mapped to a template where its entries are classified in this way; a template is a value $t \in \{0,☹,x\}^d$.  A template stands for one or more vectors.

Now, for each template $t \in \{0,☹,x\}^d$, the table keeps track of whether any vector that matches the template $t$ can be reached by summing any subset of the input vectors.  This table will have at most $3^d$ entries, since there are at most $3^d$ possible templates.  You can fill in the entries of the table using dynamic programming in $O(nd \cdot 3^d)$ time.  Finally, we check the table to see whether the template $[x,x,\dots,x]$ is expressible as a sum of input vectors.  YAs described, this tells you whether any valid combination exists; you can augment this algorithm to keep track of all valid combinations.

This might be workable if $d$ is not too large; otherwise, it will be highly inefficient.  It has the benefit of being not too difficult to implement, but it is probably strictly worse than the prior algorithm in asymptotic efficiency.

Integer linear programming

Finally, it is possible to encode your problem directly as an instance of ILP.  I suggest you introduce zero-or-one variables $X_1,\dots,X_n$, with the intent that $X_i=1$ means input vector $v_i$ is included in the combination.  Also, define $w = \sum_i X_i v_i$, and introduce zero-or-one variables $Y_{j,0},Y_{j,1},Y_{j,x},Y_{j,2x}$ for $j=1,\dots,d$, with intended meaning as follows:

$Y_{j,0}=1$ means that $w_j$ is zero.
$Y_{j,1}=1$ means that $w_j$ is not divisible by $x$.
$Y_{j,x}=1$ means that $w_j$ is $x$.
$Y_{j,2x}=1$ means that $w_j$ is a multiple of $x$ that is strictly larger than $x$ (i.e., $2x$ or $3x$ or ...).

I'll show how to enforce consistency of these variables in a moment using linear inequalities.  Once we've done that, all that remains is to require that $X_1 +\dots + X_n=m$ (a combination contains exactly $m$ of the input vectors) and $Y_{1,x}+\dots+Y_{d,x}=m$ (exactly $m$ of the coordinates sum to $x$) and then test whether the entire system of inequalities is feasible, and if so, report all solutions.  That can be done using an off-the-shelf ILP solver.

To enforce the consistency of the $X$'s and $Y$'s, we add the following linear inequalities:

$Y_{j,0}+Y_{j,1}+Y_{j,x}+Y_{j,2x}=1$ for each $j$ (exactly one of those four cases must be true).
$X_i \le 1-Y_{j,0}$ for each $i,j$ such that $v_{i,j}>0$ (something that sums to zero can't have any nonzero terms in the sum).
$\sum_{v_{i,j}>0} X_i \ge 1-Y_{j,0}$ for each $j$ (if it doesn't sum to zero, at least one of the terms in the sum is nonzero).
$\sum_{v_{i,j}=1} X_i \ge Y_{j,1}$ for each $j$ (something that sums to a non-multiple of $x$ must have at least one term that is a $1$).
$X_i \le Y_{j,1}$ for each $i,j$ such that $v_{i,j}=1$ (if the sum has a term that is a $1$, then it sums to a non-multiple of $x$, since $x>n$).
$\sum_{v_{i,j}=x} X_i \ge Y_{j,x}$ (anything that sums to $x$ must have at least one term that is an $x$).
$\sum_{v_{i,j}=1} X_i \le 1-Y_{j,x}$ (anything that sums to $x$ cannot have any terms that are a $1$).
$\sum_{v_{i,j}=x} X_i \ge 2Y_{j,2x}$ (anything that sums to a multiple of $x$ larger than $x$ must have at least two terms that are an $x$).
$\sum_{v_{i,j}=1} X_i \le 1-Y_{j,2x}$ (anything that sums to a multiple of $x$ larger than $x$ cannot have any terms that are a $1$).

Hardness

Your problem is NP-hard.  Consider the special case of your problem where all entries are in $\{0,x\}$ (no input vector contains a $1$), where $m=d$, and where there are at least $m$ copies of the all-zeros vector in the input list.  This special case is equivalent to exact cover, which is NP-hard.  If a special case of your problem is NP-hard, then your problem is certainly NP-hard.  So, we shouldn't expect an efficient algorithm for your problem.   See What is the definition of P, NP, NP-complete and NP-hard?, What are common techniques for reducing problems to each other?, and Dealing with intractability: NP-complete problems for some reference material on those subjects, or grab a good algorithms textbook.


What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA? I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking or rewriting, that is you can only move right and read the string in the order it is presented.

To simulate a PDA however I am not sure what restrictions we could apply. I was thinking allowing backtracking but no rewriting on the tape may make a Turing machine with equivalent power to a PDA but I am not sure if that is a correct statement or how I would prove the equivalence of the two.

The basic idea is simple. Just make a Turing machine behave like a DFA or PDA. There are multiple ways.

How to make Turing machines have the same power as DFAs?

Here is a straightforward way as said in the question. We will not allow them to write on the tape. We will only allow them to read the input in one direction. In that way, they literally become DFAs.
In fact, we do not have to regulate how they read the input. We can simply use read-only Turing machines, which are equivalent to DFAs in power.

How to make Turing machines have the same power as PDAs?

Let us consider Turing machines with two tapes. One read-only tape with the input, which can only be read sequentially. Another tape that will be treated as a stack. Now you can see they are literally PDAs.
Suppose we are interested in simulating each PDA individually. The existence of such a TM is proven here.

There are many type of PDAs, such as deterministic or nondeterministic, accepting by final states or empty stack, even various generalized version. It should not be too difficult to see how they can be simulated by Turing machines.

"Allowing backtracking but no rewriting on the tape may make a Turing machine with equivalent power to a PDA." No, it does not. As mentioned above, read-only Turing machines are equivalent to DFAs in power. Here is the explanation from Wikipedia. The proof involves building a table which lists the result of backtracking with the control in any given state; at the start of the computation, this is simply the result of trying to move past the left endmarker in that state. On each rightward move, the table can be updated using the old table values and the character that was in the previous cell. Since the original head-control had some fixed number of states, and there is a fixed number of states in the tape alphabet, the table has fixed size, and can therefore be computed by another finite state machine. This machine, however, will never need to backtrack, and hence is a DFA.


Calculate probabilty to escape the maze I am trying to solve the problem to calculate probability to escape the maze and stuck at one use case. Here is the problem statement

The Frog is in an two-dimensional maze represented as a table.
The maze has the following characteristics:

Each cell can be free or can contain an obstacle, an exit, or a
mine.
Any two cells in the table considered adjacent if they share a
side.
The maze is surrounded by a solid wall made of obstacles.
Some pairs of free cells are connected by a bidirectional tunnel.

When the frog is in any cell, he can randomly and with equal probability choose to move into one of the adjacent cells that don't contain an obstacle in it. If this cell contains a mine, the mine explodes and the frog dies. If this cell contains an exit, then the frog escapes the maze.

When the frog lands on a cell with an entrance to a tunnel, he is immediately transported through the tunnel and is thrown into the cell at the other end of the tunnel. Thereafter, he won't fall again, and will now randomly move to one of the adjacent cells again. (He could possibly fall in the same tunnel later.)

It's possible for the frog to get stuck in the maze in the case when the cell in which he was thrown into from a tunnel is surrounded by obstacles on all sides.

So I get input as

The first line contains three space-separated integers n, m and k
denoting the dimensions of the maze and the number of bidirectional tunnels.

The next n lines describe the maze. The i'th line contains a string of length m denoting the i'th row of the maze.
The meaning of each character is as follows:

# denotes an obstacle.
A denotes a free cell where the frog is initially in.
* denotes a cell with a mine.
% denotes a cell with an exit.
O denotes a free cell (which may contain an entrance to a tunnel).

The next k lines describe the tunnels. The i'th line contains four space-separated integers i1,j1, i2, j2. Here (i1,j1) and (i2, j2) denote the coordinates of both entrances of the tunnel. (i,j) denotes the row and column number, respectively.

So for 1st use case input is

3 6 1
###*OO
O#OA%O
###*OO
2 3 2 1

Answer for this is 0.25. Total possible path could be frog gets stuck (1,1) cell + can die two times (2 mines) + Exit. So probability is 1/4

But for below use case am not able to deduce the correct probability.

7 7 2
O**%**O
OOOOOOO
OOO*OOO
**OA###
OOOO#OO
O*OO#O%
OOOO#OO
1 1 7 7
6 4 6 6

Answer should be 0.13344359
my answer is 0.2

I wrote a DFS to calculate all the end state a frog could be. In this case 2 exit + 8 mines + 0 stuck.

prob = Double.valueOf(maze.exit.size())/Double.valueOf(maze.exit.size()+maze.mines.size()+maze.stuck.size());

private static void dfs(Vertices v, Maze m, Vertices[][] edgeTo) {
        m.setMark(v.x, v.y, true);

        if(!m.neighbours(v).isEmpty()) {
            for (Vertices w : m.neighbours(v)) {
                if (w!=null) {
                    edgeTo[w.x][w.y] = v;
                    if(!m.marked(w.x, w.y)) {
                        dfs(w, m, edgeTo);
                    }
                    if(w.state.equals("%")) {
                        m.addExit(w);
                    } else if(w.state.equals("*")) {
                        m.addMines(w);
                    }
                }
            }
        } else if(!v.state.equals("*") && !v.state.equals("%")) {
            m.addStuck(v);
        }
    }

can someone help to explain the correct probability in this use case?

First of all, note that you should use pseudo-code in your question to make it readable by anyone.

You cannot treat this problem by just listing possible ends and give them equal probability. Consider this trivial case with no tunnel:

%AO*

the frog does not have a total 50 % to escape. On first move it has 50 % to go left to exit and 50 % to go right. But if it goes right it has 50 % to die on the mine and 50 % to come back on initial cell. Finally you build the series:

to exit $\sum_n \frac{1}{2^{2n+1}} = 2/3$
to die  $\sum_n \frac{1}{2^{2n+2}} = 1/3$

Of course finding the series expression can be very complicated on hard mazes. So how to solve this problem ? You can for example use a dynamic programming solution.

The sub-problem is having the probabilities for the frog to be on any cell after the $k^{th}$ move, what are the probabilities after the $(k+1)^{th}$ move ? These probabilities also contain exit and death.

So let's take again the small example %AO*, indexing the cells 1 to 4 from left to right.

at $k=0$, the frog is on cell 2 so $P(2) = 100 \%$,
at $k=1$, the frog moves left or right, so $P(exit) = 50\%$, $P(3)=50\%$,
at $k=2$, $P(exit) = 50 \%$, $P(2) = 25 \%$, $P(dead)=25\%$

ans so on, until $P(exit) + P(dead)$ is sufficiently close to 100 % for the precision you need.

Due to tunnels or even from start position, there may be some cells unable to reach a mine, an exit or any of them (as your first example). You should first investigate this, any cell that cannot reach an exit shoud be considered as a mine. And a cell that cannot reach a mine but can reach an exit should be considered as an exit. This will prevent any infinite loop and save some time.


When retrieving values from a hash table with linear probing, how do we know if the wanted value had not been shifted? So, after a collision, a piece of information gets stored in the next bucket. When retrieving the value later with a key, how do we know it has not been shifted due to a collision and that we are in fact receiving the wrong value?

With linear probing, the appropriate bucket stores both the value and the literal key. So when retrieving, you start in the bucket determined by the hash code and check if the key is the same. If it's not, you move to the next one and check again, and repeat until you find what you're looking for.


Definition of “c-competitive” algorithm What is the definition of a "c-competitive" algorithm? For example what does it mean, if we say that there is a 2-competitive algorithm for packet routing?

You are given algorithm $ALG$ for optimization problem $\mathcal{P}$ and and cost function $\mathcal C$.

You can define cost of optimal algorithm $OPT$ as:

$C(OPT(I))=\min_{O\in F(I)}\mathcal C(I,O)$, where $I$ is valid input, $F$ is a feasible solution on input $I$ and $O$ is the output associated with that feasible solution.
Then you can define cost of c-competitive algorithm as:

$\mathcal C(ALG(I))\le c\cdot \mathcal C(OPT(I)) + \alpha$,

Where $\alpha$ arbitrary is constant, if $\alpha = 0$ then we are talking about strictly c-competitive algorithm


How can one tell when will the state of the circuit components change? The system clock is needed to synchronize all components on the motherboard, which means they all do their work only if the clock is high; never when it's low. And because the clock speed is set above the longest time any signal needs to propagate through any circuit on the board, this system is preventing signals from arriving before other signals are ready and thus keeps everything safe and synchronized. The CPU clock has the same purpose, but is only used on the chip itself. Because the CPU needs to perform more operations per time than the motherboard, the CPU clock is much higher. And because we don't want to have another oscillator (e.g. because they also would need to be synchronized), the CPU just takes the system clock and multiplies it by a number, which is either fixed or unlocked (black edition models).

\bib{38243}{misc}{
    title={What are system clock and CPU clock; and what are their functions?},
    author={Benjoyo (https://cs.stackexchange.com/users/27547/benjoyo)},
    note={URL: https://cs.stackexchange.com/q/38243 (version: 2015-02-11)},
    eprint={https://cs.stackexchange.com/q/38243},
    organization={Computer Science Stack Exchange}
}

This answer states that the clock components change state only when the signal is high. Why is it so?

It is not necessarily true, this is only one possible way of achieving synchronization. One could arbitrarily decide that it happens when the signal is low, or when the signal goes from low to high (rising edge), or high to low (falling edge), or even both. This wikipedia page contains more information.


Usefulness of consensus number What information and usefulness does knowing the consensus number of a shared object give me?

You probably cannot do much better than quote the abstract of Herlihy's original paper:

  A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes. The problem of constructing a wait-free implementation of one data object from another lies at the heart of much recent work in concurrent algorithms, concurrent data structures, and multiprocessor architectures. First, we introduce a simple and general technique, based on reduction to a consensus protocol, for proving statements of the form, “there is no wait-free implementation of X by Y.” We derive a hierarchy of objects such that no object at one level has a wait-free implementation in terms of objects at lower levels. In particular, we show that atomic read/write registers, which have been the focus of much recent attention, are at the bottom of the hierarchy: they cannot be used to construct wait-free implementations of many simple and familiar data types. Moreover, classical synchronization primitives such as test&set and fetch&add, while more powerful than read and write, are also computationally weak, as are the standard message-passing primitives. Second, nevertheless, we show that there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object.


Solving Recurrence Relation (quicksort ) I know quicksort to have a runtime of $\mathcal{O}(n \log_2 n)$

However trying to solve for it I get something different and I am not sure why that is.

Ok, so solving recurrence relations can be done several different ways.

The recurrence relation for quicksort is:

$$T(n) = 2 T(\frac{n}{2}) + \mathcal{O}(n)$$

Reinserting a few times we get:

$$T(n) = 2 \left[ 2 T(\frac{n}{4}) + \mathcal{O}(\frac{n}{2}) \right] + \mathcal{O}(n)$$

$$T(n) = 2 \left[ 2  \left[ 2 T(\frac{n}{8}) + \mathcal{O}(\frac{n}{4}) \right] + \mathcal{O}(\frac{n}{2}) \right] + \mathcal{O}(n)$$

$$...$$

Which can be generalised to:

$$T(n) = 2^kT(\frac{n}{2^k})+\sum_{i=0}^{k-1} \mathcal{O}(\frac{n}{2^i})$$

Now the sum can be solved like this:

$$\sum_{i=0}^{k-1} \mathcal{O}\left(\frac{n}{2^i}\right) = \sum_{i=0}^{k-1} \mathcal{O}\left(n\left(\frac{1}{2}\right)^i\right) = \frac{n -n\left( \frac{1}{2}\right)^{k-1}}{1 - \frac{1}{2}}$$

$$\lim_{k \to \infty} \frac{n -n\left( \frac{1}{2}\right)^{k-1}}{1 - \frac{1}{2}}  = \frac{n}{1 - \frac{1}{2}} = 2n$$

So the recurrence can be simplified accordingly:

$$T(n) = 2^kT(\frac{n}{2^k})+2n$$

Assuming $T(1) = C$ we get $$T(n) = 2^{\log_2 n}T(\frac{n}{2^{\log_2 n}})+2n = n C + 2n$$

And $ n C + 2n \not \in \mathcal{O}(n \log_2 n)$

Can somebody explain my error to me?

Your mistake is $2\mathcal{O}(n/2) = \mathcal{O}(n/2)$. More generally, in order not to be confused, it is much better to replace $\mathcal{O}(n)$ with $An$ for some constant $A$, which can be taken as $1$ without loss of generality. Then we have
$$
\begin{align*}
T(n) &\leq 2T\left(\frac{n}{2}\right) + n \\
&\leq 4T\left(\frac{n}{4}\right) + 2 \frac{n}{2} + n \\
&\leq 8T\left(\frac{n}{8}\right) + 4 \frac{n}{4} + 2 \frac{n}{2} + n \\
&\leq \dots
\end{align*}
$$
More generally, we get
$$
T(n) \leq 2^k T\left(\frac{n}{2^k}\right) + kn.
$$
Assuming $n = 2^k$ and $T(1) = C$, this gives
$$
T(n) \leq 2^kC + k2^k = \mathcal{O}(n\log n).
$$
You can get a lower bound in exactly the same way.


How to uniquely encode a vector of non-increasing positive integers Given a vector of positive integers $A=[a_1, \cdots, a_n]$, where $\sum_{1 \leq i \leq n}a_i = n(n-1)$ and $a_i \geq a_j$ iff $i \geq j$, I am interested in encoding the vector, maintaining the following conditions,

The result of encoding is unique, i.e. the encoding of two different vectors cannot be the same.
The result of encoding has the same order as the dot-product of A with  the vector $[1, \cdots, n]$, i.e., $A \cdot [1, \cdots, n] > A' \cdot [1, \cdots, n] \Rightarrow e(A)>e(A')$.

I was wondering if such encoding exists. I tried a couple of options such as $e(A)=A \cdot [2^1, \cdots, 2^n]$, but it did not work. I am not sure if considering an irrational number such as Euler's instead of 2 would work, i.e. $e(A)=A \cdot [e^1, \cdots, e^n]$.

P.S. Of course, one way is using prime numbers, but this way is computationally very expensive and I want to avoid that. So, I prefer a way that does not involve calculating prime numbers and such computationally-intensive values.

Define $[b_1,\dots,b_n]$ by $b_i = a_i - a_{i-1}$ for $i>1$ and $b_1 = a_1-1$.  Then $[b_1,\dots,b_n]$ is a sequence of non-negative integers.

Pick any unique encoding of such sequences, call it $e^*$, with the property that the output of $e^*([b_1,\dots,b_n])$ is an integer in the range $0..M-1$ for some $M$.

Finally, define an encoding $e$ as follows:

$$e([a_1,\dots,a_n]) = M \times [a_1,\dots,a_n] \cdot [1,2,\dots,n] + e^*([b_1,\dots,b_n])$$

where $[b_1,\dots,b_n]$ is defined as above.  Then the encoding $e$ satisfies both of your conditions.  Encodings are unique (this follows from the uniqueness property of $e^*$).  Also it satisfies the ordering property (this follows since $0 \le e^*(\cdots) < M$).


What is the effect of having a transition in an epsilon-NFA upon "$\epsilon$,0"? When a transition between two states is achieved via any of the symbols $\epsilon,0$, how does the $\epsilon$ effect the transition between the two states?

Does it simply mean that the $0$ is ignored, since it is technically in both states at the same time?

I suggest you review the definition of epsilon-NFA, especially the definition of when an epsilon-NFA accepts a word.

To answer your question, no, the $0$ is not ignored. Consider an epsilon-NFA with two states, the initial state $q_0$ and the accepting state $q_1$, connected by two edges labeled $\epsilon$ and $0$. This epsilon-NFA accepts the words $\epsilon$ and $0$. If you remove the edge labeled $0$, the epsilon-NFA will accept only $\epsilon$.