There can be more than one ciphertext that maps back to the same plaintext. In mathematical terms, the encryption algorithm must be injective so that you can recover the plaintext for the ciphertext, but this does not prevent the ciphertext from encoding more information than the plaintext.

As a concrete example, consider modes of block cipher operation such as CBC, CTR or OFB. All these modes involve an IV (initialization vector) in addition to the plaintext, the block cipher algorithm and its key. (For CTR, the IV is called a nonce, but it plays a similar role.) The encryption function is deterministic for a given IV. The IV, on the other hand, may be chosen randomly (for CTR, it must be chosen randomly). Thus, unless the protocol specifies a deterministic method of choosing the IV (such as an agreed-upon constant), the IV is sent alongside the ciphertext. In fact, the output of the encryption software often consists of the IV followed by the cipher text stricto sensu. The IV itself is sent in plaintext; it does not (must not) contain any confidential information.

As another example, consider the PKCS1.5 mode (“padding scheme”) of RSA (defined in PKCS#1 version 1.5 — see p.22–25 of PKCS#1 v2.1). Simplifying a bit, this mode consists of concatenating a random string with the message, then applying the exponentiation operation. The ciphertext is $(P \mathbin\Vert M)^e \mod{n}$ where $\Vert$ is concatenation, $M$ is the message and $P$ is a padding string most of whose bits are random. To recover the message from the ciphertext $C$, apply the raw decryption operation $C^d \mod{n}$ and break up $C$ into padding (which is discarded) and message.


$k$-SUM can be solved more quickly as follows.

For even $k$: Compute a sorted list $S$ of all sums of $k/2$ input elements.  Check whether $S$ contains both some number $x$ and its negation $-x$.  The algorithm runs in $O(n^{k/2}\log n)$ time.
For odd $k$: Compute the sorted list $S$ of all sums of $(k-1)/2$ input elements.  For each input element $a$, check whether $S$ contains both $x$ and $-a-x$, for some number $x$.  (The second step is essentially the $O(n^2)$-time algorithm for 3SUM.)  The algorithm runs in $O(n^{(k+1)/2})$ time.

Both algorithms are optimal (except possibly for the log factor when $k$ is even and bigger than $2$) for any constant $k$ in a certain weak but natural restriction of the linear decision tree model of computation.  For more details, see:

Nir Ailon and Bernard Chazelle.  Lower bounds for linear degeneracy testing.  JACM 2005.
Jeff Erickson.  Lower bounds for linear satisfiability problems.  CJTCS 1999.


When you read data from a given memory address, the memory manager checks if there is a copy in the cache. If yes (cache hit), the copy is read into the register. If no (cache miss), the cache is first updated with a row of memory from RAM; then the data can be read into the register.

Conversely, when you write to a memory address, the data is just written to the cache, making room if required. Later, when the cache line must be freed or is explicitly flushed, the row of memory is copied to RAM.

If you perform successive reads and writes to the same address, it can very well arise that all changes are made in the cache and the RAM left untouched. From the processor's point of view, the presence of the cache is transparent. It just reads from and writes to memory addresses, and the memory manager optimizes the transfers.

Note that you don't "create" data in memory. When a program is loaded, some RAM space is assigned to it and reserved (possibly also initialized), and the addresses of the variables are "mapped" onto that space. Then the program is allowed to write to or read from these addresses.

In modern, multicore CPUs, cache management is much more complicated because several concurrent reads/writes to the same memory addresses can occur. The MMU must ensure that all caches and RAM remain coherent and "synchronize" their content.

The stack and the heap have a range of memory addresses allocated, and they are handled through the cache like ordinary program space. The stack is an essential resource during program execution and it is extremely frequently accessed. It is important that it be cached as well.


Are objects appropriate for modeling the real world?

Object-oriented programming languages are designed to support programming.  Whether they "properly" model the real world is beside the point and not the primary goal.  So, when you ask "why haven't [these requirements] been included?", it's likely because those weren't considered relevant or necessary to the goal of supporting programming.
It's like saying "A hammer is no good for driving in a screw; why haven't the requirements of driving screws been included in the design of a hammer?"  Well, that's not what hammers are designed for.
Of course you could invent your own language that follows different principles.  You'd presumably end up with something that looks different.  I'm not sure you'd ever finish such a project; I suspect there would always be some aspect of the real world that isn't incorporated in the language, and at some point you'd have to accept imperfect fidelity to the real world.  In any case, that would be a different project, with different design goals, so it's no surprise that it might lead to a different result.


Network Flow - Minimum flow in a network

Imagine you have the following graph (in red are the minimum capacities):

The $(s,t)$-path with the lowest flow demand needs $1$ unit of flow, but the minimum flow is $4$. And the $(s,t)$-path with minimum sums of capacities has a sum of $2$, so this also doesn't work.


Proving the (in)tractability of this Nth prime recurrence

The following paper shows that PRIMES is in P (it also won a Gödel award in 2006):

http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

By setting the solution of the Nth prime minimization procedure to the AKS PRIMES algorithm (modulo a subtraction), we may effectively get a tractable solution to the recurrence relation (if you can prove that the prime gap is given by the recurrence relation).

Source codes can be found on the internet. I am not pointing to them here because I did not check them personally.

As is however, we may still have the upper bound of $\sqrt{n}$ for checking all numbers...


efficient cumulative all over combinations of boolean vector elements

You can do this without computing the logical AND's at all: you can enumerate all subsets that consist entirely of "true" and enumerate all subsets that contain at least 1 "false".

First, enumerate all subsets of length $k$ with all "true".

Then, enumerate all subsets of length $k$ that contain the first occurrence of "false" in the vector.

Then, enumerate all subsets of length $k$ that contain the second occurrence of "false" but not the first.

Etc...


A simple approach is to use the sum of hashes, e.g.,

$$\begin{align*}
\text{combine}(X) &= \sum_{x \in X} H(x)\\
\text{separate}(y,x) &= s - H(x)
\end{align*}$$

where $H(\cdot)$ is some good hash function.  To make the result suitable as a hash, I recommend that you hash the output of combine one more time before using it as a hash value.

More generally, you can use any commutative hash function.  See, e.g., https://crypto.stackexchange.com/q/6497/351 and https://crypto.stackexchange.com/q/11420/351 and https://crypto.stackexchange.com/q/54544/351 and Which fingerprinting/hashing algorithms support compounding?.

Another approach is to use a Merkle hash tree.  Store the list of children in a Merkle hash tree, one mini Merkle hash tree per node of your tree (i.e., a binary tree whose leaves are the children of the node, and where each internal node is augmented with the hash of the values in its two children, and the value in the root of hte Merkle tree is the hash of that node of your tree).  This allows $O(\lg n)$ updates rather than $O(1)$ updates, but that might be good enough.


If SAT is in coNP then NP=coNP, which is believed to be false. However, coSAT, the language of unsatisfiable CNFs, is coNP-complete.


Importance of Frequency vs CAS Latency in memory performance

The presented timing for first word assumes the row is currently open (i.e., is only CAS latency, in nanoseconds). For random accesses, RAS latency is added; if another row in the bank is still active, PRECHARGE latency (to write back the active row before opening the desired row) is added. RAS and PRECHARGE latencies are typically proportional to CAS latency.

Given that cache misses add both cache probing delay and various delays in the on-chip network (including queuing delay) and at the memory controller (e.g., scheduling delay), the delay of the DRAM chip itself are a little less significant. (Adding buffering to support larger capacity, e.g., load-reduced DIMMs, further increases latency.)

(There are additional constraints on DRAM activity, so some access patterns may be unexpectedly slow compared to the simple model of PRECHARGE, RAS, CAS.)

Frequency controls peak bandwidth, which is more important for some workloads. Frequency also determines the occupancy of a DRAM data channel, so a higher frequency DRAM can satisfy more requests per second as long as they are "well-behaved" (only accessing different rows in the same bank will be slow), reducing queuing delays.


Infeasible linear programming reduce errors to find solution

One approach: replace each inequality $a_1 x_1 + \dots + a_n x_n \le b$ by $a_1 x_1 + \dots + a_n x_n \le b + t$, replace each inequality $a_1 x_1 + \dots + a_n x_n \ge b$ by $a_1 x_1 + \dots + a_n x_n \ge b - t$ (using the same $t$ for all of them), and then minimize $t$.


Does an example exist where it can be shown OPT-IP < OPT-LP easily?

Here is an example of "LP Relaxation of Maximum Coverage Problem".

Let $G$ be the complete graph with four vertices, $\{v_1,v_2,v_3,v_4\}$. That is, $G$ has six edges. Let $S_i$ be the set of edges that is not incident to $v_i$. More specifically,
$S_1=\{\{v_1, v_2\},\{v_1, v_3\},\{v_1, v_4\}\}$.
$S_2=\{\{v_1, v_2\},\{v_2, v_3\},\{v_2, v_4\}\}$.
$S_3=\{\{v_1, v_3\},\{v_2, v_3\},\{v_3, v_4\}\}$.
$S_4=\{\{v_1, v_4\},\{v_2, v_4\},\{v_3, v_4\}\}$.

The maximum coverage problem is given the above 4 sets, select at most 2 of these sets such that the maximum number of elements are covered. The answer is to select any two sets, which will cover 5 elements. For example, if we select $S_1$ and $S_2$, then all edges are covered except edge $\{v_1,v_2\}$.

If we relax this integer linear programming problem to its corresponding general linear programming problem as done here, we can select "half" of each set. Then each element is "covered" exactly once in total! For example, $\{v_1,v_2\}$ is covered by "half" of $S_3$ and "half" of $S_4$. So we are able to "cover" 6 elements, which are more than 5 elements.

As you should be able to see by now, the idea of this example is quite easy to understand and to generalize.

Problem to ponder (This is not an exercise.)
Is 5/6 the worst ratio we can get given any 4 sets?


The difference between min and max heap is in the invariant holding before and after any insertion or deletion.
Namely in a max heap the keys of the son's of a node are always smaller then the node itself (i.e. biggest key is root). In a min-heap the son's keys are always bigger (i.e. smallest key is root).

When inserting a new node with key x you insert it in the first empty leaf of the structure (usually the leftmost leaf). this will probably invalidate the invariant, therefore we need now to adjust the heap. just compare the newly inserted node's key with its parent recursively and swap them if the heap invariant doesn't hold.
Repeat the adjusting step until the father is smaller/bigger than it's son [minheap/maxheap].
The complexity of an insertion is log(n) because the heap always has a height of log(n) and the adjusting part of the insertion (which is also the most expensive) starts from a leaf (the node we just inserted) and brings it (in the worst case) to the root.

for more material see: https://en.wikipedia.org/wiki/Min-max_heap


Why is average waiting time is the same for FIFO and LIFO

Maybe an example will help, consider lets say for 3 minutes we add 2 tasks each minute, and we process 1 task a minute. With a FIFO queue the timeline will be:

t(0): 'a' and 'b' added: [a, b] - 'a' processed after waiting $0$ - [b]
t(1): 'c' and 'd' added: [b, c, d] - 'b' processed after waiting $1$ - [c, d]
t(2): 'e' and 'f' added: [c, d, e, f] - 'c' processed after waiting $1$ - [d, e, f]
t(3): [d, e, f] - 'd' processed after waiting $2$ - [e, f]
t(4): [e, f] - 'e' processed after waiting $2$ - [f]
t(5): [f] - 'f' processed after waiting $3$ - []

Average wait time: $(0 + 1 + 1 + 2 + 2 + 3) / 6 = 1.5$, longest wait time: $3$

Then consider a LIFO stack:

t(0): 'a' and 'b' added: [a, b] - 'b' processed after waiting $0$ - [a]
t(1): 'c' and 'd' added: [a, c, d] - 'd' processed after waiting $0$ - [a, c]
t(2): 'e' and 'f' added: [a, c, e, f] - 'f' processed after waiting $0$ - [a, c, e]
t(3): [a, c, e] - 'e' processed after waiting $1$ - [a, c]
t(4): [a, c] - 'c' processed after waiting $3$ - [a]
t(5): [a] - 'a' processed after waiting $5$ - []

Average wait time: $(0 + 0 + 0 + 1 + 3 + 5) / 6 = 1.5$, longest wait time: $5$


How do Kruskal's and Prim's algorithms compare to each other?

A tree in a graph is a connected acyclic subgraph. A spanning tree in a graph of order $n$ is a connected acyclic subgraph of order $n$ or equivalently a connected acyclic subgraph with $n-1$ edges.
Prim's algorithm consists of building a spanning tree by adding edges (and corresponding vertices), always keeping the connected and acyclic property, until the tree contains all vertices. The complexity of the algorithm is detailled here: it is $O(|E|\log |V|)$ with binary heaps, and $O(|E| + |V|\log |V|)$ (which is slightly better in general case) with Fibonacci heaps, a complicated data structure.
Kruskal's algorithm consists of building the spanning tree by adding edges always keeping the acyclic property, until there are $|V|-1$ edges. Its complexity is detailled there. It is $O(|E|\log|V|)$, but if the edges can be easily sorted, you can reach $O(|E|\alpha(|V|))$ with improved union-find data structure ($\alpha(x)$ is in practice very small, that is $\leq 4$ even if $x$ is the number of particles in the universe).
Both of them are greedy algorithms, but the property you keep invariant is not the same.


Difference between normal-order and applicative-order evaluation

What research have you done to answer that question? I just plugged it
as it is in Google, and got as second answer (the first may be as
good, I did not check) a reference to a section of a bible on your
topic: Hal Abelson's, Jerry Sussman's and Julie Sussman's Structure
and Interpretation of Computer Programs (MIT Press, 1984; ISBN
0-262-01077-1), aka the wizard book. The reference is to the section
"Normal Order and Applicative Order".

It states:

  Scheme is an applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed.

and adds that the latter is called lazy evaluation.

So you have your definitions wrong, and taking one for the other:

applicative order evaluates subexpressions  when, i.e. just before,
the procedure is applied.
normal order passes subexpressions as they are, without evaluation,
and proceeds with the evaluation only when the corresponding formal
parameter is actually to be itself evaluated. (there is a further
twist to it regarding environment issues ... but we better forget
that at this point).

Furthermore, you do not properly understand the call mechanism which
involves two things:

the parameter passing mechanism, which include proper processing of
actual arguments to the call, depending on the evaluation rule;
the "replacement" of the call to the function by the body of the
function (without the header).

In the case of applicative order evaluation of ( test 0 (p) ), you are
supposed to evaluate the argument subxpressions first. These are 0
and (p).

evaluation of a literal value like 0 yield that value.
the second argument however is a procedure call to a parameter-less
procedure called p. It has no parameter, so that we have no worry
about evaluation order. Then, in order to pursue evaluation, we
have to replace the call by the body of the procedure which follows
the list of arguments, and then evaluate that body. The body of
procedure p, as defined by the declaration (define (p) (p) ),
is (p), so that we are left with the evaluation of what we were
just trying to evaluate. In order words, the evaluation process is
caught in a loop, and will not terminate.

... and you never get to actually finish the call to the function test,
since evaluation of its arguments does not terminate. Your program
does not terminate.

This risk of non termination, even when the guilty argument will never
be used in the call, is one of the reasons to use instead normal
order evaluation, which may be a bit harder to implement, but may have
better termination properties.

Under normal order evaluation, you do not touch the argument
sub-expressions. What you do is replace the call ( test 0 (p) ) by
the body of the function test, i.e. (if (= x 0) 0 y), where the
names of the (formal) arguments x and y are replaced by the
corresponding actual arguments 0 and (p) (up to environment, or
renaming issues, that are important but would complicate the
explanation here, and are the main difference between the original Lisp and
the Scheme language).

Hence you replace the evaluation of ( test 0 (p) ) by the evaluation
of (if (= 0 0) 0 (p)).

Now the function if is a primitive function that usually always
evaluate its first argument, but evaluates its last 2 arguments in
normal order, evaluating only the useful one, depending on whether the
first evaluates to false or true (actually NIL or #f for
false, or some other value for true, in the case of Scheme - if my
memory does not fail me). Since (= 0 0) evaluates to true,
evaluation of the conditional amount to evaluating the yet unevaluated
second argument, which is 0, which unsurprisingly (except in old
Fortran) evaluates to 0.

Deep breath.


What is the connection between data structures and data types?

I agree with your definition of abstract data type.  (A domain of values, together with some operations on that domain.)

I typically use the term data structure to refer to implementation techniques for data types.  Examples of data structures are things like balanced binary trees and hashtables.

For example consider the data type set of integers, with operations like union, intersection, is_member?, and insert_member.

You could implement the data type with at least three different data structures, each of which has advantages and disadvantages.  For example, you could implement your set using a balanced binary tree (like a red-black tree, for example).  Each node in the tree represents a member of the set, insertion and membership tests take $O(\log n)$.  Or, if your sets are over a finite (and relatively small) universe of items you could implement it with a bit array.  This is an array of $U$ bits (where $U$ is the size of the universe.) Inserting element $i$ just means setting the $i$th bit, testing for membership just means testing the $i$th bit.  But now intersection (respectively union) requires you to take the binary-and (respectively or) of $U$ bits, which kind of stinks when you have sets with just a few elements in them.  Similarly with hash table implementations, insertion and testing are nice (on average), but intersection and union can be somewhat more complicated to do efficiently.


Why does a polytime hitting set generator derandomize RP?

The point is that instead of checking what happens for all possible random strings, you can reduce the search to the output of the generator.
Let $M(x,r)$ be some RP machine for a language $L$, i.e. if $x\in L$ at least two thirds of the $r$'s lead to acceptance, and if $x\notin L$ there is no $r$ for which $M(x,r)$ accepts. Now, Given input $x$, construct a circuit $C_x(r)=M(x,r)$ and execute the generator $G\left(p(|x|),|C_x|\right)$, where $p(n)$ is the number of random bits used by $M$ on a length $n$ input. This yields a set $R$ of polynomially many strings, now simply check whether or not $C_x(r)$ accepts at least one element from $R$. This doesn't straightforwardly generalizes to BPP since in that case it might be the case that $x\notin L$ but $C_x(r)$ accepts some strings from $R$.


Prove the following problem is NL-complete

Let $G'$ be the graph with self-loops added to every vertex. Take $n$ copies $G'_1,G'_2,\ldots,G'_n$ (without the edges) and connect $x \in G'_i$ to $y \in G'_{i+1}$ if $(x,y) \in G'$. The shortest path between $s \in G'_1$ and $t \in G'_n$, if any exists, is now of length exactly $n-1$.


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.


How to write Context Free Grammar with numerical restrictions

First off, your grammar isn't quite right, since there's no way to eliminate $S$; every production with $S$ on the LHS produces a string including $S$, so your grammar generates no (finite) strings at all.

To capture the "greater than or equal to 1" requirement, you should have a rule that produces the smallest permissible string; to handle the $m$ case, this would mean you need a production yielding $00011$. To handle the $n$ case, on the other hand, you'd need a production yielding $01$. Together, this implies that $0001101$ is the smallest string in your language. With the base cases out of the way, you can add other productions to build on this base case.

For your case, you have have a context-free language which is the concatenation of two other context-free languages. If you can make a grammar for the two constituent languages, it's easy to make a grammar for your language:

$$S \rightarrow S_1S_2$$

Grammars for the other are easy, too, and you had the right idea:

$$S_1 \rightarrow 00011 \mid 000S_111$$

and

$$S_2 \rightarrow 01 \mid 0S_21$$


Disk scheduling has an additional physical constraint.  Accelerating and moving the disk head takes times in the msec range.  Wikipedia says average seek times are around 10 msec (to move halfway across the radius of the disk) and the time to move just to the adjacent track is about .5 msec.  Thus an algorithm like FIFO might be reasonable for process scheduling because it would deliver about the same compute throughput as any other scheduling algorithm, but FIFO would be a disaster for disk scheduling.

You are not correct that the primary objective of either disk scheduling or process scheduling is "to reduce monopolies".  In real time process scheduling, for example, the primary objective is to make sure that processes with lower priority never run when there is a higher priority process available.

There are things that are worse than monopolies on workstations too.  If you are time sharing between some number of processes that are consuming so much VM that you are thrashing then no-one is getting any service, and you are better off being less fair (swapping out processes until the ones that are left can get some CPU service and hopefully finish.)

Finally, most real operating systems try to give priority to "interactive" processes.  But you can't figure out which processes are interactive until you've seen them running.  So you use an algorithm like Corbato's Multi-level feedback queue.

Edit: I forgot to mention  that disk scheduling algorithms are often variants of the elevator scheduling algorithm.  This moves the disk head in one direction, doing requests in the order that they lie on the disk.  The objective in the elevator algorithm is to maximize throughput while putting a bound on unfairness.


Moving an edge in a weighted tree to maximize longest path length

Hints:

When you remove an edge from the graph, you split it into two trees.

Given a tree, can you find the longest path in that tree?  (It's not hard.)

Given two trees, can you find which edge to add to make the longest path in the resulting graph as long as possible?  (Hint: first find the longest path in each of the two trees.  Then..)

This is your exercise, so I'll let you take it from here.  That should give you plenty to work with.


Why can't we detect infinite loops in the busy beaver problem?

The state of a TM includes its tape contents. Since the tape is infinite, the number of different tape contents we may encounter is infinite as well. So a TM is not required to repeat a state in order to never halt.

As a very simple example, consider the TM that will in each step write a character on the tape and move to the right. -- It will never halt but also never repeat a state.


Can $f$ be not computable even if $L$ is decidable?

If $L$ is decidable then you can use it's decider to compute $f$:
for the first symbol of $f(s)$ run the decider on the input $s\#x$ for any $x\in A$. For one of them, the decider will answer YES--this is the first letter in $f(s)$.

Continue doing this (e.g., for the second letter, decide if $s\#\#x \in L$, etc.), and reveal $f(s)$ letter-by-letter until the time where the decider answers NO for all $x\in A$, which means you reached the end of $f(s)$.

So if $L$ is decidable, $f$ is computable. Conversely, if $f$ is not computable, it can't be that $L$ is decidable.


Data structure for efficient group lookup

If the groups are static, your data structure is perfectly reasonable.
You can also consider the Union-Find data structure.  Find is the getGroupOf operation.  It is quite fast, and also allows you to modify the data structure by merging groups and adding a new item in its own group.


Do formulas involving fewer repetitions of variables give higher numerical precision?

First, I want to say that it is not the case in general that an algorithm that minimizes the number of uses of the inputs is more accurate, at least for IEEE 754 floating point.  For example, compensated summation.

On the other hand, it's certainly the case that interval arithmetic can greatly benefit from knowing when two inputs are identical.  As a trivial example, if $X$ is an interval variable, then logically $X - X = 0$ but of course the subtraction algorithm (usually) doesn't know whether it's inputs are logically identical, and so it must assume the worst-case $$X - X = [X^{lo} - X^{hi},X^{hi} - X^{lo}]$$

This is roughly what's going on here and almost certainly view SICP is taking.  If you use naive interval arithmetic operations, repeated uses of a variable will be treated independently, and so it won't be possible to cancel out error and the worst-case must be assumed.  Using the formulas from the interval arithmetic Wikipedia page and assuming $R_1$ and $R_2$ are represented by intervals that are strictly positive, you can simply calculate:
$$\frac{1}{\frac{1}{R_1}+\frac{1}{R_2}} = \left[\frac{1}{\frac{1}{R_1^{lo}}+\frac{1}{R_2^{lo}}},\frac{1}{\frac{1}{R_1^{hi}}+\frac{1}{R_2^{hi}}}\right]$$
while
$$\frac{R_1 R_2}{R_1 + R_2} = \left[\frac{R_1^{lo}R_2^{lo}}{R_1^{hi}+R_2^{hi}},\frac{R_1^{hi}R_2^{hi}}{R_1^{lo}+R_2^{lo}}\right]$$

It's clear that $$\frac{R_1^{lo}R_2^{lo}}{R_1^{hi}+R_2^{hi}} \leq \frac{R_1^{lo}R_2^{lo}}{R_1^{lo}+R_2^{lo}}$$ and symmetrically for the upper bounds, so the latter formula has a looser interval.


I don't know the lecture you are referring to, but I do know the topic.

In this case "lower bound" is meant in an existential sense.
That is, for every sufficiently large $n$, there exists a graph $G$ on $n$ nodes such that the number of minimum cuts in $G$ is $\binom{n}{2}$. In particular $G$ is a cycle on $n$ nodes.

The easiest way to see why this definition of lower bound is interesting is to think of upper bounds first.
It is possible to show that the number of minimum cuts in any graph with $n$ nodes is at most $\binom{n}{2}$. Then one natural question is whether this upper bound is tight or whether it can be improved.

Your lower bound answers the above question: it is not possible to prove any upper bound smaller than $\binom{n}{2}$ since there is always at least one graph on $n$ nodes for which there are at least $\binom{n}{2}$ minimum cuts.

Note that, in this sense, the lower bound of $n-1$ that you can obtain by considering a star is a worse lower bound than the one you obtain by considering a cycle.

To summarize: an existential lower bound of $f(n)$ means that, in general, there can be no better upper bound than $f(n)$. Often times you'll find that lower bounds are expressed using asymptotic notation. A lower bound of $\Omega(f(n))$ means that there can be no upper bound better than $c f(n)$ for some constant $c>0$.


Are genetic algorithms special instances of random search done in an unexpectedly short run-time?

I guess the easiest  way to reason it (this is after thinking about what user:vzn said

  a genetic algorithm exploits the gradient in the fitness function due
  to crossbreeding. if there is no gradient to exploit, it is indeed
  roughly the same as a random search over the search space.

, um that the chromsomes which embedd some sort of a possible solution has a higher chance of being a solution than a randomly generated chromosome.On mutation and crossbreeding it up its chance of being closer to the answer.I do not know random variable theory or stochastic calculus(if it is ver used in such a thing) to prove it but it's feels pretty intuitive now.

ANd if you think carefully about what the fitness function does probabilistically, because it takes the best fits, the best fits have a higher chance of being crossbred and mutated into a better solution than an unfit solution.

As for a random search based searching , it really doesn't this narrowing down part to give an answer in most cases as compared to a GA.


Relativized world where $LogCFL^A=PSPACE^A$

Maybe it is easier to look at the problem from the other side: ... the German wikipedia article on NP claims that $LogCFL\neq PSPACE$ would be known, ...

It is know: $CFL \subset DSPACE(O(\log^2 n))$ was shown in [ 1 ] and "generalized" in [ 2 ] (whatever that means, I don't have full text access to those articles). This algorithm takes superpolynomial time, i.e. it is different from the CYK algorithm taught in Hopcroft and Ullman (and not even mentioned there, despite contrary claims). It directly follows that $LogCFL\subset DSPACE(O(\log^2 n))$ and hence $LogCFL \neq PSPACE$.

  But if this should be known indeed, then I wonder whether it also applies to $AC^1$, ...

The English wikipedia article on complexity classes claims that $NC\neq PSPACE$ would be known. Since $AC^1\subset NC$, this would mean that it also applies to $AC^1$. This separation can be deduced from $NC^k\subset DSPACE(O(\log^k n))$, see for example Lemma 5.4 A circuit of depth $D$ can be simulated in $O(D)$ space or slides 25-28 of this ppt. So it is well known indeed.

  But does this resolve the initial question whether there is a relativization barrier?

Who cares!

1
Lewis, P.M. II, R. E. Stearns, and J. Hartmanis. "Memory Bounds for the Recognition of Context-Free and Context Sensitive Languages." IEEE Conference Record on 1965 Symposium on Switching Circuit Theory and Logical Design.

2
Stephen A. Cook, Path systems and language recognition, Proceedings of the second annual ACM symposium on Theory of computing, p.70-72, May 04-06, 1970, Northampton, Massachusetts, United States


How to find a local minimum of a complete binary tree?

As the tree is finite and the labels are real numbers, we are assured that there is a least element in the set of labels (this question from math.SE has a proof of this simple property). In this case as all the labels are distinct, it is okay that we require the local minima to be strictly less than their neighbours. If they were, then we would have to relax this condition to "less or equal to", otherwise there may not be a solution. Nonetheless we know that there is at least one local minimum to find.

If the tree is rooted (i.e. we have a notion of a parent-child relation) we can solve the problem marginally cheaper. If the tree is unrooted, then asymptotically we can do as well, but we will likely perform more actual probes.

First we'll deal with the rooted case.

As the tree is a (complete) binary tree, each vertex has at most three neighbours, its parent and two siblings (with the root of course having no parent), so a vertex is a local minimum if its label is less than the labels of its two children and parent. Hence we can determine if a vertex is a local minimum or not with at most four probes (in fact as we will traverse the tree in an ordered fashion, we will need at most three in the rooted case).

To actually find a local minimum, we can traverse the tree, starting with the root as the current vertex, in the following fashion:

Probe the current vertex's label, and the labels of its two children.
If the current label is the smallest, halt and report that the current vertex is a local minimum.
Else set the current vertex to the child with the smallest label, and return to step 1.

As we start from the root, we never need to worry about the parent's label - the root has no parent, and if our current vertex has a parent, then we must have discounted it in the previous iteration. Note that in step 2 it's not strictly required that we choose the smallest label, any that is smaller than the current is sufficient1, picking the smallest just gives a definite choice (again because we have distinct labels).

As we select one vertex out of the two children, our traversal picks out a path from the root to (at furthest) a leaf, thus as we have a binary tree of depth $d < \log n + 1 $ (as it's a complete binary tree with $n = 2^{d}-1$ vertices), we perform at most $3d \in O(\log n)$ probes.

In the unrooted case, we don't have such a convenient starting point, however we still have the tree structure (even if the algorithm doesn't know it). We can use the following algorithm:

Pick any vertex to be the initial current vertex.
Probe the label of the current vertex and all of its neighbours.
If the current vertex has the lowest label, halt and report it as a local minimum.
Else, select the neighbour with the lowest label as the new current vertex and return to step 2.

At each iteration we only perform at most 4 probes, so the question is how many iterations can there be? The key is to observe that we can never backtrack (we know that were we came from had a bigger label), so we must follow a simple path in the graph, but as the graph is actually a complete binary tree, the longest simple path has length $2d$. Thus even in the unrooted case we perform at most $8d \in O(\log n)$ probes.

For correctness we look at the second algorithm (the rooted case is clearly just a special case of the unrooted).

The fact that the algorithm can never backtrack also guarantees termination, as the graph is finite. Now we need only demonstrate that the vertex $v$ we terminate at is in fact a local minimum. Assume for contradiction that it is not, then it has some neighbour $u$ that has a label with a lower value. We have three cases: (1) $u$ is the previous vertex in the path which the algorithm has followed, in which case when the algorithm was at $u$, it would not have selected $v$ as the next vertex; (2) $u$ is appears in the path, but more than one iteration earlier, in this case the graph is not a tree; and (3) $u$ is not in the path the algorithm followed, but then the algorithm would select $u$ as the next vertex in step 4, and the algorithm would not have terminated at $v$. Thus $v$ must be a local minimum.

Another way to see this is to simply observe that the sequence of labels of the vertices selected by the algorithm is monotonically decreasing. From this both the termination and correctness follows immediately.

Footnote:

The property that allows this is that every subtree has a local minimum - again, every finite set which has a total ordering has a least element. Thus by induction, when we extend the subtree with a new root and a sibling-subtree, we have three cases: (1) the new root is smaller than both its children, so the algorithm would terminate the new root; (2) the new root is smaller than one child but not the other, then the algorithm will not choose the larger root and must take the smallest by definition; or (3) both children are smaller, but in this case, as noted, each subtree has at least one local minimum, so we may select either.


Find number of awesome substring of a given binary string

Could you please explain exactly where you were stuck? Anyway, I'll choose some parts of the solution which were not described by author and shed light on them.

You can assume that $T=\sqrt{n}$ in the solution. The main idea can be formulated as follows:

For any positive integers $m, n$ such that $m \le n$ either $m \le \sqrt{n}$ or $\frac{n}{m} < \sqrt{n}$.

This is applied to all substrings where $m$ is the number of ones. It means that we can divide all substrings into two disjoint sets: where the length divided by number of ones is small (set $k= \frac{len}{m}$, then $k \leq \frac{n}{m} < \sqrt{n}$), or the number of ones is small ($m \leq \sqrt{n}$). Then we compute sizes of each set separately. When we apply such idea, we hope that each of these subtasks can be solved faster than a big one.

For the first set, I find the idea of computing $t[i]=i-k\cdot{}pref[i]$ well-explained.

For the second set, if we fix $l$, we can break segments of $r$'s into segments $[r_m, r_{m+1})$ for which the number of ones in substring $s_l \ldots{} s_r$ equals $m$. We consider only $m\leq \sqrt{n}$, and for each $m$ the number of suitable $r$'s can be found in $O(1)$. Note: the set of such $r$'s forms an arithmetic progression with a common difference $m$.

And, if we iterate over $l$ in descending order, we can also make a "structure" for recomputing these segments in $O(1)$.


Covering the unit square by smaller squares of variable sizes

I'd suggest a 2-dimensional k-d tree storing one point for each corner of each rectangle returned.  A quadtree or 2-dimensional interval tree might also work.  More generally, you might consider a 2-dimensional binary space partitioning tree, where you partition based on one of the edges of one of the squares returned (extended horizontally or vertically out to infinity in both directions).

How would you partition, in a binary space partitioning tree?  Each square gives you two horizontal lines and two vertical lines (obtained by extending each edge of the square out to the full unit square).  For instance, imagine sorting all of those vertical lines from left-to-right, and picking the median line, and using that to partition.  Continue splitting recursively.  This gives you a nested tree of regions.  Then, associate each square with the lowest (deepest) node/region that fully contains it.  When you are picking a split for a particular region of space, you use all of the lines that fall within that region (from all squares that have any overlap with that region).


A horn clause is a disjunction with at most one positive literal, e.g.

\begin{align}
\lnot X_1 \lor \lnot X_2 \lor \ldots \lor \lnot X_n \lor Y
\end{align}

The implication $X \rightarrow Y$ can be written as disjunction $\lnot X \lor Y$ (proof by truth table). If $X = \lnot X_1 \lor \lnot X_2 \lor \ldots \lor \lnot X_n $, then $\lnot X$ is equivalent to $X_1 \land X_2 \land \ldots \land X_n$ (De Morgan's law). Therefore, the above clause is logically equivalent to

\begin{align}
(X_1 \land X_2 \land \ldots X_n) \rightarrow Y
\end{align}

A Prolog program basically is a (large) list of horn clauses. A Prolog clause (called rule) is of the form
head :- tail.,
which in logic notation is $head \leftarrow tail$. Therfore, any horn clause

\begin{align}
\lnot X_1 \lor \lnot X_2 \lor \ldots \lor \lnot X_n \lor Y
\end{align}

is written in Prolog notation as Y :- X1, X2, X3, ..., Xn.

A horn clause containing no positive literal , e.g. $\lnot X_1 \lor \lnot X_2 \lor \ldots \lor \lnot X_n$ can be rewritten as $(X_1 \land X_2 \land \ldots X_n) \rightarrow \bot$, which is :- X1, X2, X3, ..., Xn. in Prolog notation.

Regarding your examples:

"John is beautiful and rich", is a CNF, and each clause contains at most one positive literal, hence it can be written in Prolog as beautiful(john). and rich(john).
$\forall X \ \exists Y \ \operatorname{Loves}(X,Y)$

That nested extential quantifier can be eleminated by Skolemization, which is introducing a new function for the extential quantifier inside the universal quantifier: $\forall X \ \operatorname{Loves}(X,p(x))$, which in Prolog notation is loves(X,p(X)).


Two functions which can create any computable function by composing?

If such functions existed, they would constitute a computable enumeration of all computable functions, which is impossible for the following reason. Suppose you had a computable enumeration $f_i$ of all computable functions. The function $g\colon i \mapsto f_i(i) + 1$ is then computable, but by definition $g \neq f_i$ for all $i$.


I'm not convinced the approach translates well. In particular, the last statement would become something like "the square root of the number of boxes [...]" and that doesn't work out well. A more traditional way to approach this is:

The inner loop has complexity $\Theta(i\sqrt{j}))$. This loop is executed for $1\leq j \leq i$ (middle loop) which gives a complexity of

$\Sigma_{j=1}^i i\sqrt{j}=i\Sigma_{j=1}^i \sqrt{j}$

Evaluating $\Sigma_{j=1}^i \sqrt{j}$ is tricky. There is no closed-form formula, but we can obtain an approximation by changing the sum to an integral. Note that

$\int_0^i x^{1/2}=\frac{2}{3}i^{3/2}$

is a lower bound, while

$\int_1^{i+1} x^{1/2}=\frac{2}{3}{i+1}^{3/2}-\frac{3}{2}$

is an upper bound. We may conclude that

$\Sigma_{j=1}^i \sqrt{j}=\Theta(i^{3/2})$.

Hence the middle loop has complexity $\Theta(i^{5/2})$. For the outer loop, we have to evaluate

$\Sigma_{i=1}^n i^{5/2}$

for which there is once again no closed-form formula. By applying the same integral technique, we find that the complexity is

$\Theta(n^{7/2})$.

However, finding a closed-form formula for the exact complexity (without asymptotic notation) is impossible.


How does the OS handle multiple stacks in its physical memory?

The point you make at the very end of your question is the right one.
No modern computer has a stack. In hardware terms it turns out to be superfluous, wasteful and useless.
A stack is superfluous because one can easily perform the operations “write a value”, “retrieve the last value written”, and so on by having a pointer to a memory location. “Push” can be implemented by advancing the pointer and writing to the location it points to; “pop” by reading the pointed-to location and undoing the advance of the pointer. (On Intel architectures the pointer is a register called SP, and “advancing” decrements SP before writing to memory). This emulation of a stack requires no hardware at all - only memory, which exists already.
A hardware stack is wasteful because it requires special mechanisms over above the “read at location”, “write at location” which we already have because we have RAM. (Some early or embedded microprocessor architectures have gone the other way, having a very few levels of stack on-chip).
A hardware stack is useless because fashionable computer languages such as C cannot function with a stack in the strict sense - they need to access not just the last pushed value (such as a return address) but values pushed earlier on, which can be the arguments to a subroutine, for example.
Returning therefore to your main question: among the memory assigned to a process there is an area of memory which the process will use for its stack. Its stack pointer will point into that area. Switching from one process to another involves saving the whole state of the old process including the stack pointer and loading the whole state of the new process including the stack pointer. Because there is no special stack as such, on process termination everything is simply forgotten: nothing else needs to be done.


Algorithm for producing array of objects according to the given distribution

Do you need to guarantee that, in every sample, 50% of the objects are red, 30% are green and 20% are blue? If so, just make your array consist of $0.5\,N$ red objects chosen uniformly at random, followed by $0.3\,N$ green and $0.2\,N$ blue. You'll need to deal with the rounding error if $N$ isn't divisible by $10$.  You can always shuffle the array if it's not desirable to have it sorted by colour.

If you only need to guarantee that the proportions of the colours are correct in the long-run, Apass.Jack's solution will do the job.  If $N$ is very large, then each array generation is "the long-run" and will be close to the correct proportions (but not guaranteed to be exact).


Why does the converse of the clock condition imply that any two concurrent events occur at the same time?

Assume the clock condition AND its converse: $$C(a)\lt C(b) \Rightarrow a \rightarrow b \tag{*}\label{*}$$
Next, take note that $\neg(a \rightarrow b)$ implies either $b \rightarrow a$ or $a \nrightarrow b$ (i.e. if '$a$ does NOT happen before $b$' then either '$b$ happens before $a$' or they are concurrent events).
Now, since the implication $\eqref{*}$ is (assumed) true, its contrapositive must also be true:
$$\neg(a \rightarrow b) \Rightarrow C(a)\geq C(b)$$
Applying our negation rule, we find either $b \rightarrow a \Rightarrow C(a)\geq C(b)$ (which reduces to the clock condition) or $$a \nrightarrow b \Rightarrow C(a)\geq C(b)$$
Lamport is only interested in the latter case: "...we cannot expect the converse condition to
hold as well, since that would imply that any two $\mathbf{concurrent}$ events must occur at the same time."
To show this, remember Lamport said when $a,b$ are concurrent then both $a \nrightarrow b$ and $b \nrightarrow a$ so $$b \nrightarrow a \Rightarrow C(b)\geq C(a)$$
The last two equations imply if $a$ and $b$ are concurrent, $C(a)=C(b)$.
To derive the contradiction, take any two events $a, b$ concurrent but on separate processes. Then their clock numbers must be the same. Now if there is another concurrent event before or after $a$ (on the same process), then it too must have the same clock number as $b$ and therefore $a$. But that contradicts the clock condition (e.g. see condition C1 in the paper).


Mathematically calculating time complexity

If we ignore effects of overflow and assume we can square x as often as we like in constant time, then the first example clearly either stops immediately if n ≥ 2, or runs forever if n < 2.

In the second example, at each iteration i is multiplied either by 2 or by 3. Therefore after k iterations, $2^k ≤ i ≤ 3^k$. The number of iterations until i ≥ n is between $log_2 (n)$ and $log_3(n)$ which is in each case $O (log(n))$.

On the other hand, I'm currently working on an algorithm where I don't have the slightest idea how to calculate the runtime, although measurements show that it takes experimentally about $600 n^{1/2}$ nanoseconds for values from $10^{12}$ to $10^{19}$ - with huge variations. A proof for $O(n^{1/2})$ is mathematically beyond me.

In the end, this question is like asking "how can I prove mathematical theorems". Some are easy, some are hard, most get easier with practice. There is no "list of possible tricks". The most helpful thing is that when you are concerned with big-O notation you don't need precise results. A constant factor makes no difference.


Differences between programming model and programming paradigm?

A programming model is implied by the system architecture. If your system architecture is a register machine, your programming model will consist of machine code operations on registers. If your architecture is a stack machine, your programming model will consist of stack operations. A Von Neumann architecture and a Harvard architecture will have other programming models. Self modifying code p.e. wil be possible in a Von Neumann architecture but not in a Harvard architecture.

A programming paradigm is more highlevel: it is the way a problem is modelled (imperative or declarative, Object oriented, functional, logic,...). A single paradigm language supports one of these. Multiparadigm languages are more a sort of Swiss armyknive which take elements out of more paradigms.

Every architecture (and corresponding model) will have his own set of machine code instructions. This machine code language itself will follow the imperative paradigm (do this , do that, read register A, add the value to register B,... or put a value on top af the stack, put another value on top of the stack, add the two values on top..., etc...)

(At least I never saw a non-imperative hardware processor)

A high level language (of whatever paradigm) will be compiled or interpreted to this machine code.

About parallelism: If we consider interconnected processors it will be clear that the way they interconnect will be part of the programming model. An old INMOS transputer p.e. connects with four other transputers. The machine code wil have instructions to communicate with the naburing transputers.

But also on recent systems the way to provide mutual exclusion will have to be resolved on low level. On a one processor system we will have to put the interrupts on and off when leaving or entering the critical section. On a multiprocessor system we will need a monoatomic 'test and set' instruction. This is part of the programming model.

Parallel computing paradigms are high level models to use parallelism. Think on languages who have threaded objects, or use semaphores and monitors as language elements.

When we program on different operating systems, different API's will be used. (or even if we program on the same system but we use an other library - a graphics library p.e.). This will change our programming model. the low level code will be different, but if there is a good abstraction (sort of code once, compile anywhere) this will be invisible in the high level language. If not, you will have to make small changes in your code. But since you will use the same high level language, there will be no change of paradigm.


Short version: it doesn't know. There's no way to tell.

If 1111 represents -7, then you have a sign-magnitude representation, where the first bit is the sign and the rest of the bits are the magnitude. In this case, arithmetic is somewhat complicated, since an unsigned add and a signed add use different logic. So you'd probably have a SADD and a UADD opcode, and if you choose the wrong one you get nonsensical results.

More often, though, 1111 represents -1, in what's called a two's-complement representation. In this case, the ALU simply doesn't care if the numbers are signed or unsigned! For example, let's take the operation of 1110 + 0001. In signed arithmetic, this means "-2 + 1", and the result should be -1 (1111). In unsigned arithmetic, this means "14 + 1", and the result should be 15 (1111). So the ALU doesn't know whether you want a signed or an unsigned result, and it doesn't care. It just does the addition as if it were unsigned, and if you want to treat that as a signed integer afterward, that's up to you.

EDIT: As Ruslan and Daniel Schepler quite rightly point out in the comments, some operands still need separate signed and unsigned versions, even on a two's-complement machine. Addition, subtraction, multiplication, equality, and such all work fine without knowing if the numbers are signed or not. But division and any greater-than/less-than comparisons have to have separate versions.

EDIT EDIT: There are some other representations too, like one's-complement, but these are basically never used any more so you shouldn't have to worry about them.


Boyce-Codd Normal Form vs. 3rd Normal Form

Because they are two different concepts.

A schema satisfies 3NF iff for every functional dependency in the relation such as X -> A, X is a key or A is prime (part of the key).

A schema satisfies BCNF iff for every functional dependency in the relation such as
X -> A, X is a key.

You can clearly see from these definitions that every BCNF must also satisfy 3NF. However, precisely for the reason that to achieve BCNF you may need some extra splitting on the relations, it could be impossible to preserve all the FDs.

I'll give you an example: say you have a relation

R(A, B, C, D, E)

With FDs:

ABCD -> E
E -> BCD

This relation is in 3NF since E depends on the key and BCD is prime; however, since BCNF doesn't have the prime clause, the relation fails BCNF due to E -> BCD.

On the other hand, when you break down the relation to meet BCNF

R1(E, B, C, D), R2(A, E)

the FD ABCD -> E is lost because of the over-splitting we had to do.


They are not trying to cheat you. You need to read the text of Example 12.12, following the formula.  It says:

  A denumerable model of $\Gamma_d$ will consist of a denumerable set $X$ with an equivalence relation in which any two elements $a$ and $b$ that are not isolated, that is, that are such that each is equivalent to something other than itself, are equivalent to each other.

Thus $x$ and $y$ in your example must be equivalent in the model, and the picture is not an accurate representation of what $\Gamma_d$ captures.


What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$

For matching number of a and c you need to do something like this:

$$
S \rightarrow AB \\
A \rightarrow aAcc \\
A \rightarrow C \\
C \rightarrow bC | λ \\
B \rightarrow dB | λ
$$

You need to produce them in one rule to be sure the ratio is kept.


Is the empty string and some words of even length are elements of this set?

Yes, since "the first, the middle, and the last characters of $w$ are identical" is not really well defined here (so there might be ambiguities like is $\epsilon\in L$?)

Probably it wont really matter for the question if you assume $\epsilon\in L$ or $\epsilon \notin L$ (other than some small change in the PDA or CFG) But if you really want to make sure everything is ok, then write (in the answer for the question) that there are ambiguities and this is how you interpeted them.


Is there a simple example of sets such that $A \leq_T B$ but not $A \leq_m B$?

For example sets $H = \{x \, | $ Turing machine with index $x$ halts on input $x\}$ and $\overline{H} = \{x \, | $ Turing machine with index $x$ doesn't halt on input $x\}$.

Because if $\overline{H} \leq_m H$, then $\overline{H}$ would be recursively enumerable and therefore $H$ would be recursive, which is contradiction.

On the other hand $\overline{H} \leq_T H$, because there is Turing machine with oracle $H$ recognizing $\overline{H}$. This machine for input $x$ just checks $x \in H$ and negates the answer.


Here is the probable interpretation:

  for every $j \neq i$ in $\{0,\ldots,n-1\}$:

    code

should be interpreted as:

  for every $j$ in $\{0,\ldots,n-1\}$:

    if $j \neq i$:

      code

This is similar to the way this kind of statement is interpreted in mathematical text.

It is also possible that the roles of $i$ and $j$ should be switched — this should be clear from context, and it's an ambiguity that also exists in mathematical texts.

As mentioned in Evil's answer, if neither $i$ nor $j$ has been defined, then the interpretation is probably

  for every $i,j$ in $\{0,\ldots,n-1\}$:

    if $i \neq j$:

      code


Formal definition of loss surface of multi-layered networks

In the empirical risk minimization framework, we let $w$ denote the weights of the neural network (which we are trying to learn) and define $L(w)$ to be the total loss (across the entire training set) if you use weights $w$.  Then, the optimization problem is to find $w$ that minimizes $L(w)$.

This is the function that the quote is talking about.

"Loss surface" refers to the graph of this function.  $L$ is multidimensional so we obtain a graph in some high-dimensional space.


Can Edge Belong to a cycle if it is part of multiple BFS products

As Yuval pointed out, there is some ambiguity of the original exercise as the enqueueing order of the neighbors of a node is not stipulated by the definition of a breadth-first-search (BFS).
Proposition 1: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. If $e$ is a part of a cycle, then there is a BFS of $G$ that produces a BFS tree that does not contain $e$. (If $e$ is not part of any cycle, then it is a bridge of $G$ and, hence, appears on every spanning tree.)
Since this proposition is, apparently, clear to the OP, no formal proof will be given here.
If we stick to this (indeterministic) version of BFS, the answer to the exercise should be choice 1, "it does not belong to any cycle".

Let us add some context so that that exercise becomes more interesting.
Suppose that for every node, the order of its children to be enqueued in a BFS is fixed beforehand. Now, it can happen that an edge that is part of a cycle can be part of the spanning tree produced from each of $n$ BFS runs. For example, graph $G_1$ with $C_0=[1,3]$, $C_1=[0,2]$, $C_2=[1,3]$, $C_3=[2,0]$, where $C_i$ is the list of neighbors of node $i$ in the enqueueing order. The following lists shows the edge $\overline{1,2}$ is always part of the BFS tree produced.

The BFS starting from node 0 produces the tree with edges $\overline{0, 1}$, $\overline{0,3}$, $\overline{1,2}$.
The BFS starting from node 1 produces the tree with edges $\overline{1, 0}$, $\overline{1,2}$, $\overline{0,3}$.
The BFS starting from node 2 produces the tree with edges $\overline{2, 1}$, $\overline{2,3}$, $\overline{1,0}$.
The BFS starting from node 3 produces the tree with edges $\overline{3, 2}$, $\overline{3,0}$, $\overline{2,1}$.

We have the following proposition.
Proposition 2: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. Suppose we have selected an enqueueing order for the neighbors of each node.   If a BFS of $G$ will always include $e$, then $e$ is either not part of any cycle or $e$ is a part of cycle of even length.
Proof. For the sake of contradiction, suppose that there is a cycle of odd length that contains $e$ and every cycle that contains $e$ is of odd length.
Consider $\mathcal C$, one of the shortest cycles that contains $e$. Since the length of $\mathcal C$ is odd, we can select $v_0$, a node of $\mathcal C$ that is "opposite" to $e$, i.e, the cycle is $v_0, v_1, \cdots, v_k, v_{k+1},\cdots, v_{2k-1}, v_{2k}, v_0$ for some $k$ and $v_i$'s, where $\overline{v_k,v_{k+1}}$ is edge $e$.  Since any cycle containing $e$ must be longer than $\mathcal C$, we have,
$$\text{distance}(v_0, v_{k}) = \text{distance}(v_0, v_{k+1}) = k.$$

Let us run BFS from node $v_0$. Let tree $T$ be the BFS tree produced. We claim $T$ does not contain $e$. Otherwise, suppose $T$ does contain $e$. WLOG, suppose $v_k$ is nearer to $v_0$ than $v_{k+1}$. Since $T$ is a shortest-path tree from $v_0$, we have
$$\text{distance}(v_0, v_{k+1}) = \text{distance}(v_0, v_{k}) + \text{distance}(v_k, v_{k+1})=\text{distance}(v_0, v_{k}) + 1,$$
which contradicts previous equality. This contradiction shows that $T$ does not contain $e$. That, however, contradicts the given condition that every BFS tree contains $e$. $\ \checkmark$

With respect to proposition 2, the answer to the exercise should be choice 3, "$e$ might belong to a cycle but if it belongs to an odd-length cycle, then it must belong to an even-length cycle.", if the context, i.e. the way in which BFS is supposed to run, implies that the enqueueing order of neighbors of a node is fixed before all runs.


Asymmetric Transition Probability Matrix with uniform stationary distribution

Take the matrix $A$ such that for every $i$, we have:

$A_{i,i} =0.5$
$A_{i,i+1}=0.5$ (for $i=n$, set $A_{n,0}=0.5$)

Then it is not symmetric, but has a uniform stationary distribution.


why does relabel take O(VE) time total for unit capacity flow networks?

The $O(VE)$ result actually holds in general, not just for unit edge capacity, hence it has nothing to do with edge capacity being 1.
This result is proven in Exercise 26.4-3 of CLRS, and thus the $O(V^3)$ quoted in the question is not tight.


Traverse Matrix in Reverse Diagonal strips

Straight lines are defined by linear equations. Assuming arrays indexed from zero, as in C, you want the lines $x-y=c$ for $c=2,\,1,\,0,\,-1,\,-2$. This gives something like

for c := 2 to -2 step -1
    for x := 0 to 2
        y := x-c
        if 0<=y<=2
            print A[x,y]


What is complexity of checking whether a natural number is a perfect square?

For a given number $n$, binary searching for the square root $\sqrt n$ solves this problem in time $O(\log n)$.


Rewriting gates such as XOR into three basic gates?

Hint:  $a \oplus b = \neg \big( (a \land b) \lor (\neg a \land \neg b)\big)$  (you can't have both true and you can't have both false).  Using De Morgan's, you should be able to break up the negation and the main $\lor$.


What is inapproximability of NP-hard problems?

Optimization problems come in two flavors: minimization and maximization. For definiteness, in this answer we consider minimization problems; for maximization problems the situation is completely analogous.

Generally speaking, when we say that a minimization problem $\Pi$ is $c$-hard to approximate, we mean the following:

  If there is a polynomial time approximation algorithm for $\Pi$ whose approximation ratio is better than $c$ then [something bad happens].

Usually the "something bad" is $\mathsf{P} = \mathsf{NP}$, but sometimes we can only prove that, say $\mathsf{NP} \subseteq \mathsf{DTime}(n^{\log \log n})$ (that is, SAT can be solved in time $O(n^{
\log \log n})$). Since we believe that the "something bad" is wrong, it follows that probably no polynomial time approximation algorithm for $\Pi$ has an approximation ratio better than $c$.

Why this form of result? If $\mathsf{P} = \mathsf{NP}$, then all NP optimization problems (that is, all optimization problems whose decision version is in NP) can be solved in polynomial time. Therefore in order to prove that a certain problem cannot be approximated well we need to make some complexity assumption such as $\mathsf{P} \neq \mathsf{NP}$.

The best one can hope for is to prove that is an NP-hard to approximate $\Pi$ better than $c$. What this means is that for each $\epsilon > 0$ there is a polynomial reduction $A$ from SAT to $\Pi$ with the following properties:

If the input formula $\varphi$ is satisfiable than the optimal value of $A(\varphi)$ is at most $x$, for some value $x$ which the reduction explicitly calculates (in polynomial time).
If $\varphi$ is not satisfiable than the optimal value of $A(\varphi)$ is more than $(c+\epsilon)x$.

In particular, any polynomial time $(c+\epsilon)$-approximation algorithm would be able to distinguish the two cases, and thus to solve SAT in polynomial time.

Technically, what we have described is known as a promise problem: decide whether an instance of $\Pi$ has value at most $x$ or more than $(c+\epsilon)x$; or stated differently, find the optimal value of an instance of $\Pi$ (or at least distinguish the two cases) under the promise that the optimal value is either at most $x$ or more than $(c+\epsilon)x$.

In some cases we are able to prove that a certain problem $\Pi$ is $c$-hard to approximate, and also show that a polynomial time $c$-approximation algorithm exists. In this case we say that the inapproximability threshold of $\Pi$ is $c$. For example, Håstad shows that the threshold of inapproximability for 3SAT is $7/8$.

Our definition above of $c$-inapproximability states that in polynomial time it is impossible to approximate a certain problem better than $c$, but allows an approximation ratio of $c$. Sometimes we also want to disallow an approximation ratio of $c$. The terminology doesn't reflect this fine point, and formal statements of theorems have to be consulted.

Finally, $(1+\epsilon)$-inapproximability means that (under some complexity assumptions) it is impossible (in polynomial time) to approximate the problem to within $1+\epsilon$ for some $\epsilon > 0$ (in terms of our notation above, the problem is $1$-hard to approximate). We also say that the problem is APX-hard.

Logarithmic inapproximability means that it is impossible to approximate the problem to within $O(\log n)$, where $n$ is some natural parameter inherent in the problem, usually the number of vertices in the input graph.


Since this is CS and not Stackoverflow, I'm going to assume that you're asking a question about numeric analysis, and (to keep things simple) IEEE-754 floating point in particular. In that case, the answer to your question partly depends on what you mean by "easier", and partly on the details of the system.

No modern CPUs that I'm aware of have an instruction built in which does exactly what you'd expect either for either the $e^x$ operation (which henceforth we will call exp, its usual name in C) or $2^x$ (exp2). They are both implemented using library functions.

As is the case with all numeric methods for transcendental operations, there are a few special cases to consider:

exp(NaN) = NaN
exp(+Inf) = +Inf
exp(-Inf) = 0

However, there is another thing that makes the problem slightly less complicated: the useful domain is quite small. For binary32, exp(x) underflows if $x < -104$ or so, and overflows if $x > 88.7$ or so. Unusually for transcendental operations, we can also ignore the subnormal case, since exp(x) is indistinguishable from 1.0 if x is subnormal. All of the above is also true for exp2, except that the domain is slightly different.

Your intuition is right in that most implementations compute $e^x = 2^{x/\ln 2}$. However, the cost of that multiplication by $\frac{1}{\ln 2}$ is trivial compared to the rest of computing exp2. A typical method uses a precomputed table with $K$ elements:

$$\hbox{exp2}(x) = 2^n \times T[j] \times P(y)$$

where $n$ is the integer part of $x$, the table $T$ contains values of $2^{j/K}$ for all $j$ in the range $[0,K)$, and $P$ is some polynomial approximation to $2^x$ (quartic is sufficient for binary32) in the range $[0,\frac{1}{K})$. The $2^n$ part is cheap, since it's just manipulating the exponent. $T$ is a lookup table. So $P$ is likely to be the expensive part of the operation.

I should point out for completeness that Intel x86 FPUs include an instruction called f2xm1, which computes $2^x-1$ for $x$ in the range $[-1,1]$. However, on a modern CPU, this is a fairly expensive and non-pipelined instruction, and you are highly discouraged from using it. As the Intel Optimization Reference Manual Section 3.8.5 rightly notes:

  Although x87 supports transcendental instructions, software library
  implementation of transcendental function can be faster in many cases.

Edit: It's been pointed out in the comments that I should explain some of the new terminology used in IEEE 754-2008. Some of the language has changed since 1985 and 1987, and most people are far more familiar with the old jargon.

The terms "binary32" and "binary64" are the new names for 32-bit and 64-bit binary floating-point numbers, which the old standard called "single" and "double" respectively.

The term "subnormal number" replaces the previous term "denormal number" or "denormalized number".


Is it possible to reconstruct graph if we have given matrix of shortest pairs

I would suggest the following approach.

Maintain a data structure $H$ of $(i,j, g(i,j))$ triples so that you can efficiently find and remove a triple $(i,j,w)$ that minimises $w$.

Maintain a partition $P$ of nodes $V = \{1,2,\dotsc,N\}$.

Maintain a tree $T$.

We will maintain the invariant that $T$ contains some edges of the tree that we are trying to reconstruct, each part $X \in P$ is some subtree that we have not reconstructed yet. Eventually, $T$ will be the tree and $P$ will consist of singleton sets.

Initially, $P = \{V\}$ and $T = \emptyset$.

Apply the following operation repeatedly until $H$ is empty:

In $H$, find and remove a triple $(i,j,w)$ that minimises $w$.
See if $i$ and $j$ are in the same part of $P$. If not, discard this triple and try again.
Now we have a pair $(i,j)$ and a part $X \in P$ such that $i\in X$, $j \in X$. We now know that $\{i,j\}$ has to be an edge in the subtree induced by $X$.
Add $\{i,j\}$ to $T$.
For all nodes $v \in X$, see if $v$ is closer to $i$ or $j$. Based on this information, refine the partition $P$ by replacing $X$ with $X_i$ and $X_j$, where $X_i \subseteq X$ contains the nodes that are closer to $i$, and $X_j$ similarly.

If I am not mistaken, the time complexity is roughly as follows, assuming appropriate data structures:

We extract $O(N^2)$ triples.
Only $O(N)$ triples will result in something added to $T$. These are the triples that require nontrivial work.
For nontrivial triples, the operation that dominates is splitting. There we will need to check in the worst case $O(N)$ nodes.
So overall the running time is something like $O(N^2) + O(N) O(N) = O(N^2)$.
On top of this we pay whatever time we used to construct $H$. A simple solution is to just sort the triples $(i,j,w)$ by $w$. The cost depends on what kind of $w$ values you might have, but it isn't much worse than $O(N^2)$.


Number of pairs of indexes of two arrays such that one element is greater than the other

When $A = B$, this is the same as counting the number of inversions, which can be accomplished in $O(n\log n)$ time using a divide-and-conquer algorithm, and in $O(n\sqrt{\log n})$ time using more sophisticated techniques (see Counting Inversions, Offline Orthogonal Range Counting, and Related Problems by Chan and Pătraşcu).

In the other direction, here is how to solve a similar but not identical problem.

Given $A,B$, let us construct the following array:
$$
C := A[1],B[1],A[2],B[2],\ldots,A[n],B[n].
$$
An inversion in this array is one of the follows:

A pair $A[i] > A[j]$ for $i < j$.
A pair $B[i] > B[j]$ for $i < j$.
A pair $A[i] > B[j]$ for $i < j$.
A pair $B[i] > A[j]$ for $i < j$.
A pair $A[i] > B[i]$.

Therefore you can deduce the number of $i < j$ such that either $A[i] > B[j]$ or $B[i] > A[j]$ given the number of inversions in each of $A,B,C$, augmented by the number of indices $i$ such that $A[i] > B[i]$. This yields a simple $O(n\log n)$ algorithm and a more complicated $O(n\sqrt{\log n})$ algorithm, as described above.


Big O and program calls with varied input sizes

Actually, since you did not specify what q does beyond calling p, there is too little information to know anything about the time complexity of q, except that it is $\Omega(m)$ since it must execute at least $m$ calls to p, whatever else it does.

Let's look at a special case which is probably what you were thinking of. Suppose that q looks like this:

data := preprocess(input);
for i = 0 to m -1 do
    data := p(data);
end

That is, p potentially has access to all the internal data of q. This is the most general case. Where this program is not general is that in the loop, it does nothing but call p.

The running time of this program is $Q = A + \left( \sum_{i=0}^{m-1} P(S_i) \right) + O(m)$ where

$A$ is the time taken to run the preprocessing step;
$P(s)$ is the maximum time taken by p to process data of size $s$;
$S_i$ is the size of data when the $i$th step starts.

The assumption on the running time of p is that $P(s) = O(s)$. That is, there exists $n_0$ and $a$ such that if $s \ge n_0$ then $P(s) \le a \, s$. This gives us a bound for the running time when $s$ is large. When $s$ is small, we can simply use the maximum running time of p for small sizes: there are only a finite number of sizes that are smaller than $n_0$. Let $\hat P = \max\{P(0), P(1), \ldots, P(n_0-1)\}$.

Then, expanding the definition of $O(m)$ in the equation for $Q$ above, we get that there exist $m_0$ and $b$ such that for $m \ge m_0$,
$$ \begin{align}
  Q &\le A + \left( \sum_{i=0}^{m-1} P(S_i) \right) + b m
     \le A + \left( \sum_{i=0}^{m-1} \max \{\hat P, a\, S_i\} \right) + b m \\
    &\le A + \left( \sum_{i=0}^{m-1} (\hat P + a\, S_i) \right) + b m
     \le A + a \left( \sum_{i=0}^{m-1} S_i \right) + (b + \hat P) m \\
    &\le A + a \left( \max\nolimits_{i=0}^{m-1} S_i \right) m + (b + \hat P) m
\end{align} $$

Notice how the constant $\hat P$ resulting from the small cases of running the subprogram has been absorbed into the multiplicative constant for the calling program. This is a general phenomenon: when studying the complexity of algorithms, the performance of subtasks on small inputs is irrelevant for obtaining a first bound on the complexity of the whole task. It can be relevant to prove better bounds (sometimes, the inequalities above are too crude).

We aren't quite there yet: the component $\max\nolimits_{i=0}^{m-1} S_i$ remains unevaluated. The behavior of this component depends on what p does. For example, if p is a program that duplicates its input, say

return arg ++ arg

where ++ is the string concatenation operator and string concatenation takes $\Theta(n)$ where $n$ is the length of the string, then $S_i = S_0 2^i$ and all the analysis above tells us is that $Q$ grows exponentially with $m$ — which is the case.

If we additionally assume that p does not change the size of the data and that the preprocessing step is linear in the size of the input, then $S_i$ does not depend on $i$ and is $O(n)$ (i.e. $S_i \le S n$ for large enough $n$), and we have (for sufficiently large $n$ and $m$):
$$
  Q \le a' n + S n m + (b + \hat P) m
$$
For sufficiently large $n$ and $m$, the dominant term is $S n m$: the time complexity of Q is $O(m n)$.

Note again that the reason why it took a lot of additional assumptions to prove that Q runs in $O(m n)$ is not the running time of p on smaller inputs, it's because for all we knew p could receive some very large inputs.


What are transitive successor and transitive predecessor in the graph?

If you ask Google with "transitive successor" (including the double quotes) you get several book
references, and access to some pages (which I cannot read right now,
because of a local problem). Considering that successor is a
relation between the nodes of the directed graph, "transitive
successor" should naturally be its transitive closure. One book is
apparently using the term "direct successor" to be precise and avoid
confusion with "transitive successor" which could occur when using
"successor" alone.


Bit operations; Treating a number like an array

The answer depends on the programming language and, to some extent, on the CPU. For any practical purpose, though, extracting the $k$th bit is an $O(1)$ operation even on a "big integer" stored on several machine words, since in order to extract the $k$th bit, you can use the following algorithm:

Determine which word the $k$th bit is in, and which bit in the word.
Extract the appropriate bit from the appropriate word.

In practice it is a reasonable assumption to make that indices of bits fit into a machine word, and so all of these operations are $O(1)$.


the convention for declaring arrays in pseudocode

Pseudocode is not a formal language. Declare your arrays however you want, as long as it's obvious what you mean. Including the full limits (as you have in both your array examples) is good, since it means the reader isn't worrying about whether you start your indices at 0 or 1.


You can compute a topological ordering of the vertices in linear time.


Can every regular expression be written as sum of products?

I think you have to be more careful in the inductive steps, but it seems you basically have the argumentation ready. According to me proper induction would be

  If $R_1$ and $R_2$ can be written as sum of products, then so can
  $R_1\cdot R_2$, $R_1+R_2$ and $R_1^*$.

The proof could be completed as:

If $R_1$ and $R_2$ can be represented as sum of products as $R_1 = R_{11} + R_{12} + ... + R_{1n}$ and $R_2 = R_{21} + R_{22} + ... + R_{2m}$, then:

$R = R_1\cdot R_2$ will be equivalent to ($R_{11}\cdot R_{21} + R_{11}\cdot R_{22} + ... + R_{11}\cdot R_{2m}) + ... (R_{1n}\cdot R_{21} + R_{1n}\cdot R_{22} + ... + R_{1n}\cdot R_{2m})$, by the distributivity of concatenation over union, which is in the required form.
$R = R_1 + R_2$, then $R$ is already a sum of products.
$R = R1^{*}$ can be reduced to sum of products by repeated application of the law: $(R_1 + R_2)^* = (R_1^*\cdot R_2^*)^*$ and distributivity of concatenation over union.

Hence we can write each regular expression as sum of products.

This is called the disjunctive normal form of regular expressions.


What is the definition of a $\Pi_1$-sentence?

Since Peano arithmetic is a first-order theory, all quantifiers are first-order, so it's a $\Pi_1^0$ sentence. The article probably contains examples supporting this interpretation.


How is density of a substance in grams per cubic centimeter a discrete attribute?

The book is wrong.  Density is continuous.  It could be any real number.  You are quite right.


Determinant computation is equivalent to matrix powering

It states that matrix powering is computationaly equivalent to computation.
From another angle, Coppersmith–Winograd algorithm for matrix multiplication has complexity $\mathcal O(n^{2.373})$ and the same complexity is for determinant computation by fast multiplication.
The result comes from Triangularization and inversion via fast multiplication by James R. Bunch and John E. Hopcroft


Mapping spherical coordinates onto faces of an icosahedron

The approach in your comment certainly works, and is probably your best bet.
If you think of the Platonic solid centred at the origin, then the coordinates of a a point located at the centre of each face is equal (up to normalisation) to those of a vector normal to the face. So you can, in principle, take a point on the sphere, search all the faces and find the face/normal whose dot product with the coordinates of the point is greatest.
This is surprisingly efficient on modern hardware, because it can use vector instructions effectively.
Do be careful about the fact that the Earth is not spherical. I don't know how these cartographic map projections deal with this (it may not matter with paper maps), but I imagine you would use the normal to the ellipsoid rather than the coordinates of the point on the ellipsoid.
Interestingly, mapping a normal vector to an octahedron is a particularly interesting case because an octahedron can be unfolded into a square. This is such an important problem that there are even survey papers on the topic.


The trick to reducing any NP problem to SAT is 1) writing a subroutine that checks the polynomially-sized certificate, 2) converting that routine to a circuit, and 3) flattening the circuit to CNF using the usual methods.

For example, to convert integer factorization to SAT, you would write a routine that multiplies two $n$-bit multipliers producing a 2$n$-bit result.  Convert the routine to a circuit, then convert the circuit to CNF.  Then add simple declarative CNF clauses that force the $2n$ output variables of the circuit to match the bits of the integer that you want to factor.  The resulting CNF instance will be satisfiable only if a bit pattern for the two $n$-bit numbers exists that when multiplied together produces the 2$n$-bit number you want factored.  (If you want trivial solutions excluded then you also need to add two extra CNF clauses that demand the most significant $n$-1 bits of each multiplier are not all zero.)

Subset sum is a bit more intricate.  You need to write $n$ routines, each of which returns a particular one of the $n$ integers of the problem set or zero depending on the setting of a parameter bit.  These routines feed input into another routine you wrote that sums all $n$ of its inputs and outputs the result.  Convert all this into a circuit whose inputs are the parameter bits and whose outputs are the result of the addition routine.  Convert the circuit to CNF.  Add declarative CNF clauses that force the output variables of the adder routine to match the bits of $k$, the number a solution must sum to.  The resulting CNF instance will be satisfiable only if there exists a bit pattern of the parameter bits selecting a subset of the problem set that sums up to $k$.


Why is my trivial reasoning for $PSPACE = PH$ wrong?

Alternating polynomial time allows for an unbounded number of alternations. In contrast, every level of the polynomial hierarchy only allows for a fixed number of alternations. Therefore your argument only shows that $\mathsf{PH} \subseteq \mathsf{AP}=\mathsf{PSPACE}$.


Suppose that we arrange the numbers $0,\ldots,n-1$ in an oriented cycle. The number which follows $i$ is $i+1$ for $i \neq n-1$, and $0$ for $i=n-1$. We can combine both cases by saying that the number following $i$ is $i+1 \bmod{n}$.


Why does left recursion have to be eliminated?

I am assuming that you are talking about context free grammars.

There is no difference between the two grammars. They are a different representation of the same set.

What do you mean by a problem?

Left recursion is a problem for LL(k) parsers, but they can handle right recursion. LL(k) parsers are preferred because of they use less stack space and they tend to be faster (not always though).


Decidability of factoring algebraic equations

Interesting question. Factorization of functions, including factorization of polynomials is in fact a classical problem throughout history of mathematics.

For the sake of contradiction, assume that $$x^2 + y^3 - e^{z} = f(x)*g(y)*h(y,z)$$

For the sake of simplicity, assume that $f, g, h$ are continuously differentiable inside $D$, the place where we are interested.

Now treating $y$ and $z$ as constant, take partial derivative with respect to $x$. (Aha, you might say, why didn't I think of that?!)

$$2x = f'(x)*g(y)*h(y,z)$$

Since $2x$ is not constant, $f'(x)$ cannot be constant 0. Shrinking $D$ if necessary to make sure $f'(x)$ is never 0, we have $$2x/f'(x) = g(y)*h(y,z)$$
That means, both $2x/f'(x)$ and $g(y)*h(y,z)$ are constant functions since the former is constant w.r.t. to $y$ and $z$ and the latter is constant w.r.t. to $x$. So we will have
$$ -e^z=\frac{\partial(x^2+y^3-e^z)}{\partial z} = \frac{\partial(f(x)*g(y)*h(y,z)}{\partial z}=\frac{\partial(f(x)*\text{(some constant)})}{\partial z}=0$$
which cannot be true.

The above reasoning should give you a pretty good idea that particular factorization cannot hold nicely because of too many independences between the variables in the factorization. In fact, we can show that no such $f,g,h$ exist without assuming continuity of any of $f, g, h$, as long as it is required that equality holds for a small 3D space. Note that 2D space will not be enough since we can have, letting $x=0$, $$0 + y^3-e^z=1*1*(y^3-e^z)$$

It will require some work to formulate the more general questions of decidability of function factorizations clearly enough so that it might be able to have a clear answer. It looks like if many dependencies are required, then the set of problems is probably decidable. If you are interested enough, you could try formulating those problems and raising new questions.

For related result on polynomials, we can search for "decidability of polynomial factorization".


What does "associative" exactly mean in "n-way set-associative cache"?

An n-way set associative cache is a cache that is chopped up in sections called sets. And each set can hold n-blocks.
A cache-address can be broken up up in 3 parts.

the offset within the block
the index that identifies the set
the tag that identifies the block in the set.

When a request comes in, the index is calculated to identify the set. Then the tags of all blocks in the set are checked. And when a block with a matching tag is found, the right bytes are returned based on the offset.
A direct mapped cached is effectively a 1 way set associative cache.
So associativity doesn't mean the number of blocks the cache can hold, but the number of blocks a set within the cache can hold.
The big advantage of a n-way set associative cache compared to a direct mapped cache, is the latter can only have a single block for a set of addresses and the former can hold multiple blocks for a set of addresses.


Multiplying $O\left(n^2\right)$ by $3$ doesn't change it.  Literally, it remains the same thing:

$$3{\cdot}O\left(n^2\right)~=~O\left(3n^2\right)~=~O\left(n^2\right).$$

This is because such complexity qualifications don't track scalar multipliers.

The reason that we discard scalar multipliers is pretty simple: the actual run time will depend on how fast particular computer instructions work, such that if we cared about scalar factors, our complexity qualifications would become extremely context-specific.

For example, many real-world systems will speed up as they run a long-running algorithm due to optimizations that kick in as an algorithm runs (e.g., branch profiling CPU's and hot-spot code optimizations in VM's).  So, any scalar projection of run-time behavior would have to account for these factors.  Such an analysis could still be quite helpful and worth studying when appropriate, but that's not the role that complexity classes intend to fill.

So, as general performance analyses qualifications, complexity classes tend to focus on the largest order-affecting factors while hand-waving the scalar stuff as implementation-dependent.


This sounds very much like a Hamilton path problem. If you set the edge weights all to $1$ and the deadline of the vertices all to $|V| - 1$, then each vertex can only be visited once, since there is not enough time to visit one twice before the deadline runs out. Finding a Hamilton path on the other hand is NP-hard. Thus, your problem is NP-hard as well.


A regular expression for strings with at most one triple of adjacent zeroes

It's hard to say for sure precisely what is meant by "triple of adjacent 0s". My best guess would be that it means the substring 000. In this case, an easy way to get a regular expression is to find an expression for strings with no such substring, and a regular expression for strings with exactly one such substring, and then take the union.

No such substring: $r = (1 + 01 + 001 )^*(\epsilon + 0 + 00)$ should do it.

Exactly one such substring: $s = (1 + 01 + 001 )^*000(1 + 10 + 100 )^*$ looks promising, but you should check it to be sure.

If my interpretation is correct, your answer would be $r + s$. In fact, and again, I may be jumping the gun here, I think that this can "simplify" (?) to something like $(1 + 01 + 001 )^*(\epsilon + 0 + 00 + 000)(1 + 10 + 100 )^*$.


Direction of restriction for NP hard proves

The technique your top paragraph shows NP-hardness. The technique in your next paragraph shows membership in NP.


Dynamic programming and probability - list of problems

You can use search on this site to find some examples: https://cs.stackexchange.com/search?q=%5Bdynamic-programming%5D+probability


Bounding the recurrence $f(n)=2f(n-1)+2f(n/2)$

For concreteness, let's assume that your recurrence is really
$$ f(n) = 2f(n-1) + f(\lfloor n/2 \rfloor) + f(\lceil n/2 \rceil). $$
Define $g(n) = f(n)/2^n$. Then
$$ g(n) = g(n-1) + 2^{\lfloor n/2 \rfloor + 1 - n} g(\lfloor n/2 \rfloor) + 2^{\lceil n/2 \rceil + 1 - n} g(\lceil n/2 \rceil). $$
In particular,
$$ g(n) \leq (1 + 2^{\lfloor n/2 \rfloor + 1 - n} + 2^{\lceil n/2 \rceil + 1 - n}) g(n-1). $$
Taking logarithms,
$$ \log g(n) \leq \log g(n-1) + O(2^{\lfloor n/2 \rfloor + 1 - n} + 2^{\lceil n/2 \rceil + 1 - n}). $$
We conclude that
$$ \log g(n) \leq O(1) + O(1) \sum_{m=c}^n [2^{\lfloor m/2 \rfloor + 1 - m} + 2^{\lceil m/2 \rceil + 1 - m}] = O(1), $$
where $c$ is some arbitrary starting point.
Therefore $\log g(n)$, and so $g(n)$, is bounded. Since clearly $g(n)$ is monotone increasing, we deduce that $g(n)$ tends to some constant $C$. We conclude that
$$ f(n) \sim C 2^n. $$


Using a point as an input for a perceptron

Yes, you can do that.  Nothing prevents it.  Yes, you'd have two inputs, one for $x$ and one for $y$.  You might want to normalize those values so they are in the range $[-1,1]$ or $[0,1]$.


What is an example of a Turing-recognizable infinite word, which is not Turing-decidable?

There's is a significant difference between "arbitrarily long" and "infinite".

As a simple example, an integer can have an arbitrarily great magnitude; formally, for every integer, there exists a larger integer (its successor), which in turn has a successor, and so on. But all integers are finite; $\omega \notin \mathbb{N}$. (Or, if you prefer, $\infty \notin \mathbb{N}$.)

Similarly, the Kleene star operator $A^*$ represents the concatenation of an arbitrarily large number of elements from $A$, but not an infinite number of elements of $A$.

There is an interesting part of formal language theory which deals with sets of infinitely-long strings (ω-strings), but such strings cannot be produced by any regular expression. (You can use ω-regular expressions, which include the infinite repetition operator $A^\omega$.) But you might want to master the material you're currently studying before venturing onto Buchi automata, interesting though they may be.

To answer your questions:

No, there are undecidable languages consisting only of finite strings. Indeed, since such languages are undecidable, it is not necessarily even decidable whether they are finite sets. A classic example of an undecidable language is the set of (descriptions of) Turing machines which halt on every input. Note that every Turing machine (like every integer) has a finitely-long description, so the language is a set (an infinite set, in this case) of finite strings.
A Turing machine is under no obligation to read its entire input. Consider the language of ω-strings which start with an $a$. This is clearly a set of infinitely-long strings, but only a single character needs to be examined to determine whether a string belongs to the language.
Sure, why not. For example, the Turing machine trying to determine whether its input describes a Turing machine which halts on every input could simulate the described machine using every possible input, but that is going to go on forever even if the language describe a Turing machine which always halts.
See, for example, deterministic Buchi automata. Basically, an ω-language $L$ can be deterministic if there is a language $L' \subset Pref(L)$ of finite prefixes which can deterministically predict inclusion in $L$.


Prove that the language L = {a^(m+n) b^m a^n | m, n ≥ 0} ∪ {a^m b^n a^(m+n) | m, n ≥ 0} is not regular

Regular languages are closed under finite intersection, use that to your advantage. In this case, the reason the language isn't regular is because it has a $K = \{a^n b^n | n \geq 0 \}$ hidden inside it, pull it out using a regular language as a filter. More explicitly, notice that $K = L \cap a^*b^*$.


Finding path that minimizes largest of the sum of weights of each group in a directed multigraph

At least for the case $k=2$, there is an efficient algorithm to solve your problem.  Suppose all weights are integers in the range $0..\alpha$.  Then there is an algorithm whose running time is $O(\alpha VE \log^2(\alpha V))$.  In your case, $\alpha=30,000$.

How does this algorithm work?  I'll show that, when $k=2$ and when the solution is known to be at most $\beta$, there is an algorithm with running time $O(\beta E \log (\beta V) \log \beta)$.  It's easy to see that we must have $\beta \le \alpha V$, so this will imply the claimed result (using the fact that $\log(\alpha V^2) \le 2 \log(\alpha V) = O(\log (\alpha V))$.

The algorithm works by reducing to the decision version of the problem.  Given an instance of the problem and a proposed $\gamma$, we test whether there exists a solution that is at most $\gamma$ (i.e., a path from $s$ to $t$ using red edges that total at most $\gamma$ and blue edges that total at most $\gamma$).  Then we do binary search on $\gamma$.  This will require $O(\log \beta)$ solutions of the decision problem, so it suffices to solve the decision problem in $O(\beta E \log (\beta V))$ time.

How do we do that?  We make $\gamma+1$ copies of each vertex $v$; call these copies $(v,0)$, $(v,1)$, ..., $(v,\gamma)$.  Intuitively, the new vertex $(v,i)$ corresponds to a state that can be reached if you can reach vertex $v$ from the starting point along a path where the sum of the blue edges is at most $i$.  Now we'll construct a new graph on these $(\gamma+1)V$ vertices as follows.  For each blue edge $u \to v$ with weight $w$ in the original graph, we add edges $(u,i) \to (v,i+w)$ for each $i$.  For each red edge $u \to v$ in the original graph, we add edges $(u,i) \to (v,i)$ for each $i$.

Once this larger graph is constructed, we check whether there exists a path from $(s,0)$ to any $(t,i)$ with length at most $\gamma$.  This can be done using Dijkstra's algorithm.  Since the larger graph has $O(\gamma V)$ vertices and $O(\gamma E)$ edges, the running time of Dijkstra's algorithm in this graph will be $O(\gamma E \log (\gamma V))$.  Since $\gamma \le \beta$, the claimed result follows.

This doesn't contradict your NP-hardness result, as your NP-hardness result uses very large integer weights, while the running time of this algorithm is proportional to the weights themselves (rather than to the number of bits needed to represent the weights).  Or, to put it another way, this algorithm is a pseudopolynomial time algorithm, but not a fully polynomial time algorithm.


Best algorithm for splitting up departments such that the least unique ones are assigned per day

The first problem to solve is defining the problem.

In general, you have an optimisation problem. What you have not yet defined is the objective function, meaning what you want to optimise (precisely).

Based on what you describe, you might define the objective function as the max number of participants, but this is not great since for example a solution (2,2,5) (2 departments on day 1, 2 on day 2, 5 on day 2) is equal to a solution (1,1,5); such an objective function doesn't distinguish, e.g., unnecessarily splitting two departments over the first two days.

Another option is sum, but that does not help in the case of distinguishing (1,15) and (7.5,8.5).

Perhaps another option that seems to go in the direction you want is to minimise, for example, the sum of the squares, which prefers (1,1,5) over (2,2,5) and (7.5,8.5) to (1,15). But why raise to the power of 2 and not some other value greater than 1?

These are all application-dependent choices that you have to make.

The second problem is the difficulty. You have many options and you want to find the best option according to your objective function. Your general problem is an NP optimisation problem, so you may need to consider approximations. But again, the need to consider approximations depends on the size of your data, the values you choose, how you define the optimisation function, what is the relative cost of computation versus the cost of not finding an optimal solution, and so forth.

So after you define your objective function, you will need to think about what sort of approximation (if any) is cost effective.


first intersection of two arrays of integers - double binary search feasible?

There is a double binary search algorithm.  It will only work is both lists are sorted.  It is basically as follows.

Check the first, lowest number on each list. Compare the numbers to find which number is higher. Assume that higher number is in List A
Take that higher number and do a binary search for it in list B.
If found done.
If not found take the number above the last search location in list B
For example, assume list A had a 5, and in list B you do a binary search and find 6 and 4 with no five in between.  Take the 6 from list B.
Do a binary search for that value is list A.
If found done
If not found take the number above the last search location in list A.
Repeat steps 3–7 switching back and forth between lists.

That is the basic idea, if you want further information, let me know.


Complexity of a graph parity-coloring problem

Note for each node $v$, there is a one-to-one mapping between the parity of incident edges in $S$ and that of incident edges in $\bar{S}$. This means we can consider the problem with minimum weight equivalently.

The minimum weight version is named min-cost T-join that is studied in this note, which is an application of min-cost matching.

The idea is, one can decompose $S$ ($\bar{S}$ in the maximum weight version) into a set of edge-disjoint paths joining black nodes (nodes requiring an odd degree), thus the solution is exactly a min-cost matching of the complete graph induced by black nodes where the cost of edge $(u,v)$ is the length of the shortest path between $u$ and $v$ in the original graph. So this problem can be solved by any algorithm solving min-cost matching.

If the graph is a tree, the solution is much simpler as Yuval Filmus pointed out in the comment.

  Try solving it on a tree using "dynamic programming" (i.e., recursion). For each subtree, solve the corresponding instances with both colors for the root.

Note for a tree, there is at most one feasible solution. So asking for maximum/minimum weight may be meaningless.


Formal Grammar: derivation form posted on Wiki?

You seem to be looking for a deterministic procedure that isn't there.
With multiple production rules, you solve in every possible way.  For instance, for the grammar
$S \rightarrow a \\ S \rightarrow aS$
we have
$
\underset{G}{S \implies a}, \\
\underset{G}{S \implies aS}, \\
\underset{G}{aS \implies aa}, \\
\underset{G}{aS \implies aaS}, \\
\ldots
$