What makes a language "optimized" for a specific task?

There are a few things to consider:

Abstraction: what does the language treat as "special"? Are matrices first-class values, like in Matlab, or do you encode them using simpler types like arrays, as in C? C makes you think about how matrices are implemented, Matlab doesn't.
Likewise, if you've got a complicated system of asynchronous communications, you probably want first-class functions so that you can do callbacks.
The more features that are added, the more complex the language gets. So while there are some "multi-paradigm" languages like C++ and D, most languages pick a niche, choose the things that are important to that niche, and prioritize those as their main abstractions.

Performance: all abstraction comes with a cost, whether it be compile-time or run-time. Some languages limit themselves in a way that makes them less abstract but more performant.
Early Fortran didn't allow for pointers or recursion, so it was great at number crunching, faster than a language like C, where you were running lots of loops. But it was terrible at encoding large data structures, like trees, where you needed pointers for indirection. (Note that I don't know much about modern Fortran.)

Essentially, there are always tradeoffs. More abstract means either slower runtime or more complexity at compile-time. More features means a more complex language. Some features make certain things fast and others slow, like pointers and recursion. There's no perfect language, so each language will reach a sort of local maximum in the space of language qualities.


Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

Worst-case Hardness of NP-complete problems is not sufficient for cryptography.  Even if NP-complete problems are hard in the worst-case ($P \ne NP$), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using the $P \ne NP$ assumption is a major open problem.

An excellent read is the classic by Russell Impagliazzo, A Personal View of Average-Case Complexity, 1995.

An excellent survey is Average-Case Complexity by Bogdanov and Trevisan, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 (2006) 1–106


Data Structure for Representing a Math Expression

Different representations are useful for different purposes. Think what kinds of things you might want to do with the expression, and think how each of them would be done using the stack representation and using the binary tree representation, and choose for yourself.

For fun, you may also want to consider something completely different, e.g. the english language representation: e.g. "the product of the sum of a and b, and the difference between c and d over e", or the representation as X86 machine code which would compute this expression, etc.

Things you may want to do with an expression (in any particular program you would probably need only a small subset of these):

Evaluate it, given certain values of the variables

Just once
Evaluate the same expression repeatedly for different values, with very high performance requirements

Perform simple algebraic manipulation, e.g. simplifications such as replacing x - x => 0, x*1 => x, etc.
Perform sophisticated algebraic manipulation on it, e.g. factorize the polynomials, compute derivatives or integrals.
Understand the expression stored in a variable when you're debugging the program
Format it as a string for displaying to the user
Render it as a mathematical expression to MathML
Draw it as a mathematical expression on a Javascript canvas
Compare two expressions for equivalence
Compare two expressions for equivalence ignoring variable names, e.g. a * a + b being equivalent to p * p + q
Convert a user-supplied string into an expression, checking it for well-formedness
...

Honestly speaking, I can find only one item of these for which the stack representation can possibly make things easier than the binary tree representation, and the array representation seems just completely useless.


Efficient set data structure supporting insert and set equal

Let $F$ be a finite field with efficient procedures for addition and

multiplication and almost-uniform sampling. $\:$ Let $z$ be a field element.

(I use that letter because things will be slightly more convenient if $z$ is

the zero element, although efficient sampling means that even if one

can't find the zero of $F\hspace{-0.03 in}$, one should still be able to find a field element.)

To initialize the data structure, sample a field element $x$.

Empty sets are represented by $z$, Insert(s,i) adds $x^i$ to the representation of s,

and Equal(s1,s2) just tests if the two representing field elements are equal.

Since addition is associative and commutative, there are no false negatives. $\:$ If each integer is only inserted once into a set, then the probability of there being at least one false positive is at most

the distance from $x$'s distribution to uniform $\;+\;$ $((N\cdot \text{number of equality tests})\hspace{.02 in}/($$\hspace{-0.03 in}\operatorname{card}$$(F\hspace{.03 in})) \;\;$.

To efficiently compute $x^i\hspace{-0.04 in}$, see this paper, and either avoid the methods that involve negative

powers or make slightly stronger assumptions on $F$. $\:$ I would recommend 5.1 on page 14.


Static type analysis with dynamic scoping?

There is a paper titled Implicit Parameters: Dynamic Scoping with Static Types that discusses just such a system.

The implement a slightly different system from Scala under the name "implicit parameters". By having compiler automatically generate implicit parameters in any function that calls other functions with implicit parameters the problem becomes nearly identical to standard type inference. Additionally, since these implicit parameters are still part of each functions type signature they propose a syntax for declaring most of a functions signature, while still allowing the compiler to determine the types of any implicit parameters.


How are binary trees represented on disk

This may not be an exact answer but some information of interest related to your question

Other answers have mentioned various ways in which the binary data structure can be represented and you might want to use one of them but mostly when using databases the Adjacency List Model and Nested Set Model are used for representing Binary Trees.

Binary Trees are mostly not used for storing data on disk and some alternatives are usually preferred.If you are interested in optimized data access, search,insertion and deletion  on disk then you may want to consider these alternatives

B-Tree data structure is one of the alternatives used for storage on disk.It provides search, sequential access, insert, and delete  operations in logarithmic time and is optimized for disk storage.

B-Tree data structure was created by Rudolf Bayer and Ed McCreight in 1972 to  overcome a shortfall of Binary Tree i.e. using too many disk reads.B-Tree reduces the number of disk reads by allowing more keys in a single node ( typically making a B-tree node as large as the sector minimizes the number of access times).

SQL Server uses a further optimized extension of B-Tree data structure known as B+Tree in which only the leaf nodes hold the actual data and the rest of the nodes are pointers.

According to Wikipedia B+Trees are also used for storing directory structures by some filesystems:

  The ReiserFS, NSS, XFS, JFS, ReFS, and BFS filesystems all use this
  type of tree for metadata indexing; BFS also uses B+ trees for storing
  directories. NTFS uses B+ trees for directory and security-related
  metadata

Update
How will a tree be represented as bits on the disk?

Trees can be represented by using static data structures like arrays  in a  fashion similar to this,consider each row tag as an array

//Node A can be represented as

[row 1][node A data in bits][separator bits]
[pointer to B i.e row 2][separator bits]
[pointer to C i.e. row 3][row1end]

//Node B can be represented as

[row 2][node B data in bits] [separator bits]
[no child flag][separator bits][no child flag][row2end]

//Node C can be represented as

[row 3][node C data in bits] [separator bits]
[no child flag][separator bits][no child flag][row3end]

I'd recommend studying some file formats so that you know how to represent logical data in a file, this also might be helpful

dcs.gla.ac.uk/Keith/Chapter.4/Ch.4.html


Explanations for the truth-value of each assertion:

(1) is true because any process running P() after another process has already run P() will see y==1 and so be stuck in the do-loop.  If context-switching is disabled inside P() [and we assume re-enabled on exit from P()], then the process stuck in the do-loop will be the ONLY running process, so no other process can release that one from the do-loop by calling V().

(2) is false because a context-switch may occur between the load of y and the store to x.  Consider processes P1, P2, both calling P().  The following sequence is possible: (a) P1 loads y, which happens to be 0; (b) The context switches to P2; (c) P2 loads y -which is still 0-, then sets x to 1 and exits the loop (because for it y==0) and enters the critical section; (d) The context switches back to P1, which now sets x to 1 -but still sees its version of y as 0, so it exits the loop and enters the critical section.  Verdict: Mutual-exclusion is NOT enforced!

(3) The implementation of V() is not wrong, given the implementation of P().  Execution of V() WILL set 'value' to 0, and by the atomicity property this must occur either entirely before or entirely after any test_and_set.  If before, then test_and_set will set y to 0 immediately; if after, the same thing will happen on the next do-loop iteration.

(4) [because of 2 & 3].


Clustering algorithm with specific cluster grouping areas

One approach would be to devise a loss function for each point, that says how much you will penalize the cluster assigned to that point, as a function of what clusters are assigned to its neighbors and what the nearest zones are; then let the total loss be the sum off the losses for each point; and then use some optimization algorithm to find the assignment that minimizes the total loss.


Need help with previous "Automata / Theory Of Computation" exam question

The relevant set-theoritic relations are
$$
\mathsf{REXP} = \mathsf{DFSA} = \mathsf{NFSA} \subsetneq \mathsf{CFG} = \mathsf{PDA}.
$$
The corresponding Venn diagram consists of two circles, one inside the other.


Prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is **not** recursively enumerable

As Andrej states, what you've (correctly) done is show that $D=\{x:\Phi_x(x)\uparrow\}$ is not recursive. However, there are plenty of sets which are recursively enumerable but not recursive, so you're not done yet: you need to show that $D$ is not the domain of any partial recursive function.

REMARK: Some texts define a set to be r.e. if it is the range of a total recursive function, or is empty. This is slightly less elegant since it requires a separate clause to handle $\emptyset$; it also generalizes less well if one looks into higher computability theory. However, regardless of what definition your book gives, the equivalence between them should be a very early exercise.

There are a couple ways to do this:

You could argue directly: suppose $D$ is the domain of $\Phi_i$. Can you use the recursion theorem to cook up a $j$ such that $\Phi_j(j)\downarrow\iff \Phi_i(j)\downarrow$? Do you see why this gives a contradiction?
Alternately, note that $D$ is the complement of the Halting Problem $H=\{x: \Phi_x(x)\downarrow\}$. Two early results in computability theory are that (i) $H$ is r.e. but not recursive and (ii) if a set and its complement are r.e., then they are each recursive. Do you see how to prove each of these facts, and apply them to the current problem? (Note that this approach isn't actually much different than the first one, since the recursion theorem is used in proving (i).)

REMARK: Some texts define the Halting Problem differently, some common alternate candidates being $\{x: \Phi_x(0)\downarrow\}$ and $\{\langle x, y\rangle:\Phi_x(y)\downarrow\}$. It's a good exercise to show that these are all r.e. and Turing equivalent (indeed $1$-equivalent!) to each other.

By similar arguments you can show that minor variations of $D$ are also not r.e. - e.g. can you show that $\{x: \Phi_x(17)\uparrow\}$ is not r.e.?

Responding to the comments: one may be tempted to try to enumerate $D$, or things like $D$, by looking at approximations given by stages. E.g. we could let $D_s=\{x:\Phi_x(x)[s]\uparrow\}$; this is the set of indices of machines which on their own input don't halt in fewer than $s$ steps. The $D_s$s are r.e. - indeed, uniformly recursive - and approximate $D$ "from above" in the sense that $D=\bigcap_{s\in\mathbb{N}} D_s$. However, this ultimately isn't relevant to this problem since the intersection of infinitely many r.e. sets need not be r.e.


Efficient algorithm for a modified stack to pop the smallest element

You can simply push elements to the stack only if they are smaller than the element on the top of the stack.If they are bigger you will count them in different counter in order to know how much elements were pushed and keep those counters in another stack. When you have to pop you will pop only the top element.

Here is sample pseudo code (some check for empty stacks and initial values are omitted):

    input: element
    // stack.peak() - gets top element without popping it
    if (element == -1)
        top = stack.pop()
        print(top, (counter_stack.pop() +1))

    if (element > stack.peak())
        count = counter_stack.pop()
        counter_stack.push(count+1)
    else
        stack.push(element)
        counter_stack.push(0)

Here is what should this look for your example:

9
stack: [9*]
counter_stack: [0]
6
stack: [9 6*]
counter_stack: [0 0]
8
stack: [9 6*]
counter_stack: [0 1*]
-1
stack: [9 6*]
counter_stack: [0]

print : 6(the popped value), 2 (counter_stack popped +1)

2
stack: [9*]
counter_stack: [0 0]
0
stack: [9 2 0*]
counter_stack: [0 0 0]
6
stack: [9 2 0*]
counter_stack: [0 0 1]
-1
stack: [9 2*]
counter_stack: [0 0]
print : 0(the popped value), 2 (counter_stack popped +1)

3
stack: [9 2*]
counter_stack: [0 0 1*]
1
stack: [9 2 1*]
counter_stack: [0 1 0*]
2
stack: [9 2 1*]
counter_stack: [0 1 1*]
10
stack: [9 2 1*]
counter_stack: [0 1 2*]
5
stack: [9 2 1*]
counter_stack: [0 1 3*]

-1
stack: [9 2*]
counter_stack: [0 1]
print : 1(the popped value), 4 (counter_stack popped +1)

and so on.


Non-recursivity of language of TMs which have equivalent TMs of smaller and larger description length

First, let us notice that in the definition of $L$, a machine $M_2$ accepting the same language as $M$ but having a longer description always exists, so only the condition on $M_1$ is pertinent.

Suppose that $L$ were computable. Consider the following Turing machine $T_\ell$. The machine enumerates all Turing machines of size at least $2^\ell$, until it finds a machine $M$ such that $\langle M \rangle \notin L$ (such a machine must exist, since there are infinitely many computable languages but only finitely many Turing machines of size less than $2^\ell$).  Then it transfers control to the machine $M$, i.e., it runs $M$ on the input.

By construction, $L(T_\ell) = L(M)$. Since $\langle M \rangle \notin L$, necessarily $|\langle T_\ell \rangle| \geq |\langle M \rangle| \geq 2^\ell$. However, by hardcoding $\ell$ into a Turing machine in which $\ell$ is an additional input, we see that $|\langle T_\ell \rangle| = O(\ell)$. We obtain a contradiction for large enough $\ell$.


What are the axioms, inference rules, and (formal) semantics of lambda calculus?

First of all, note that the notion of a formal system is an informal notion and there is no general (or generally accepted), formal definition of what a formal system is. In my opinion, the Wikipedia article on formal systems does not do a good job at explaining this and creates the illusion that formal systems are more or less the same as (the syntactic part) of logical systems, axiomatic systems, or proof systems, etc. Personally, I would rather go with the intuition given by the link at the bottom of the article, that leads to the following quote from John Haugeland's Artificial Intelligence: The Very Idea (1985), pp. 48-64.

  A  formal system is like a game in which tokens are manipulated
  according to rules in order to see what configurations can be
  obtained.  (Examples: chess, checkers, go, tic-tac-toe. Nonexamples:
  marbles, billiards, baseball).   All formal games have three essential
  features:

  They are token manipulation games;
  they are digital; and
  they are finitely playable.

where

  A digital system is a set of positive and reliable techniques (methods, devices) for producing and reidentifying tokens, or configurations of tokens, from some prespecified set of types.

From this perspective, it is much easier to see lambda calculus as a formal system:

the tokens are lambda expressions
the reduction rules provide the techniques as required per the "digital system"

If you want to reconcile this with the Wikipedia definition of the topic, you could consider the reduction rules to be the inference rules and the set of axioms to be empty.

Another way to look at it, is by considering the equational theory of the $\lambda$-calculus, which would look something like

Axiom: reflexivity $$\frac{}{s=s}$$
Rules: symmetry and transitivity
$$\qquad \frac{s=t}{t=s} \qquad \frac{s=t \quad t=u}{s=u}$$
Rules: application and abstraction
$$
 \frac{s=s^\prime\quad t=t^\prime}{st = s^\prime t^\prime} \quad \frac{s=t}{\lambda x.s = \lambda x.t}
$$
Axiom:  $\beta$-conversion $$\frac{}{(\lambda x.s)t=s[t/x]}$$

It is easy to show that $t =_\beta s$ (i.e. $t$ $\beta$-reduces to $s$) if and only if $t=s$ can be proved using the axioms and rules above. Using this system, it also makes sense, for example, to ask the usual "logical" question of consistency: Are there terms $s$ and $t$ for which we can not prove $s=t$.

Regarding the question of semantics, you can use the reduction rules in order to give $\lambda$-calculus operational semantics and there are also denotational semantics see Dana Scott's Data Types as Lattices For the latter, it might be easier to go via combinator algebras, see Engelers Algebras and Combinators. On a side note, this article on architectures for interpreters gives a good idea of what denotational and (small-step and big-step) operational semantics mean in this context.

In general, these questions are, however, quite hard and it might be better to first consider the simply typed $\lambda$-calculus as a starting point. Here, it is (somewhat) easy to see that it actually is a logic via the Curry-Howard correspondence. You will also find a nice answer to the question of semantics in this simple case. From the simply typed $\lambda$-calculus you can go on to consider more complicated systems in the lambda cube or things like homotopy type theory.

Also, maybe the discussion Is lambda calculus a logic? in the Lambda the Ultimate forum might also provide further insights.

Finally, this might be slightly off-topic, but if you really want to go deep down into the rabbit hole of $\lambda$-calculus, logic, and semantics, Girard's Proofs and Types and The Blind Spot might be worth a look.


Decidability of languages containing bitstrings and their corresponding ones' complements

Given a language $L$, you can create a language $L'$ which is equivalent in power and OCC:
$$
L' = \{ 0 x : x \in L \} \cup \{ 1 c_1(x) : x \in L \}.
$$
The two languages are recursively equivalent. This means that there is a computable reduction from $L$ to $L'$ and another one from $L'$ to $L$.

Using this construction, you can now answer your own question.


What's an "applicable event" in the context of the FLP paper?

An event $e$ is applicable in configuration $C$ if it could happen at configuration $C$. Since $e = (p,m)$ means that message $m$ arrives at processor $p$, $e$ is applicable at $C$ if the message queue at $C$ contains the message $m$ directed at $p$. If there is no message directed at $p$ with contents $m$ then $e$ is not applicable at $C$.


I know the algorithms, but i still don't know how to approach the questions

Allright, if I read this correctly here is what I think it should do (Some parts are possibly missing or badly formatted, but the following should make sense):

You basically copy your graph 4 times into different layers. Let's call them L1,L2,L3,L4

In L1, the highest Layer, every connection from the original graph instead goes down to L2.

From L2 every connection goes to L3, and from L3 to L4

Finally L4 looks like your original graph.

So if you search for the shortest path between u and v with at least three edges, you start at u in L1 and want to end at v in L4

Since you can only move down 1 layer at a time, you need at least three edges to reach v.

Take this graph as an example:

Let's assume we want to move from the left to the right, and the upper connection is the

shortest one. Then the correct answer is still to move through every other node, because taking the shortcut uses too few edges.

If we convert this graph we obtain the following:

Here we want to reach the bottom right from the top left. As you can see, finding a solution in this graph, automatically gives us a solution with at least three edges.

Note: Sorry that the vertices are not labelled, could not figure out the text function in the drawing tool I used :/


Why does the time hierarchy theorem use a rather intricate diagonal argument?

The output size does not scale with (time) complexity of problems in general.
In fact, complexity theorists are largely interested in decision problems for which the output will either be 0 or 1.


Your base predicate states that there exists some real number that's larger than or equal to all other real numbers (i.e that there is a highest real number).

The inverse states that every real number has a number larger than it (i.e. that there is no highest real number).

Your test cases don't produce a paradox because feeding x=y into the first predicate means that you're no longer working with R+. If all you have in your test set is a single number, then of course there's a maximum value. All you show with this test is that:

In a set containing a single real number, there exists a highest value

All that having been said, I'm sure you'll get a better answer on math.stackexchange.com!


PDA to accept language with more a's than b's and c's

Note the language where the number of $a$'s is larger than both the number of $b$'s and the number of $c$'s is not context-free, and cannot be accepted by a PDA.

Formally the language can be written as $L = \{ x\in\{a,b,c\}^*\mid \#_a(x) > \#_b(x) \text{ and }\#_a(x) > \#_c(x) \}$.

Intuitively we cannot recognize $L$ using a single pushdown as the count of $a$'s has to be used twice, but in comparing with the number of $b$'s and the number of $c$'s. That is no formal argument, there might be clever tricks avoiding the direct comparison of numbers. Yet there is a possible water tight proof, it uses the pumping lemma for context-free languages.


Algorithm to calculate average weight from every pair of nodes

One possible approach is Floyd-Warshall algorithm. This algorithm computes shortest paths between each pair of nodes. Since there is only one path between each pair of nodes, the shortest path will correspond to the weight of path between each pair of nodes. After computing all shortest paths you sum them and divide by the total number of paths (which is trivial given the number of nodes). This algorithm works in $O(|V|^3)$ time.

Also note that your graph is a tree. You may take a time to think over better algorithm which would work faster.


Smallest possible sorting network for given permutation

For concreteness, let us assume that $x_1,\ldots,x_n$ are numbers between $1$ and $n$, and that a comparison puts the smaller number at the smaller index.

Consider first the case in which $n$ is even. We divide $x_1,\ldots,x_n$ into two halves: $x_1,\ldots,x_{n/2}$ and $x_{n/2+1},\ldots,x_n$. Let us call a number misplaced if it is in the wrong half: that is, a number in the first half is misplaced if it is in $\{n/2+1,\ldots,n\}$, and a number in the second half is misplaced if it is in $\{1,\ldots,n/2\}$. Note that the first half contains as many misplaced numbers as the second half (why?). Using one round of parallel comparisons, you can exchange the locations of the misplaced numbers, and guarantee that $\{x_1,\ldots,x_{n/2}\} = \{1,\ldots,n/2\}$, and similarly $\{x_{n/2+1},\ldots,x_n\} = \{n/2+1,\ldots,n\}$. Now recursively sort each half, in parallel.

When $n>1$ is odd, we use the same strategy, dividing the array into two unequal halves, say the first half larger than the second by one element.

As an illustration, suppose that we are given the array
$$3,4,2,6,1,5$$
We switch $1$ and $4$ to obtain
$$3,1,2,6,4,5$$
Now we recursively sort $3,1,2$ and $6,4,5$.

In order to sort $3,1,2$, we first exchange $1$ and $3$ to obtain $1,3,2$, and then sort the two halves $1$ and $3,2$ in parallel, which means to exchange $2$ and $3$.

Sorting $6,4,5$ is completely analogous.


Time complexity of comparing $N$ strings

It’s much better. Say you have strings implemented as a sequence of 8 bit characters. You put each string into one of 256 bins depending on the first character. Then you examine the bins with more than one entry, by putting strings into bins depending on the second character and so on.
The worst case is all strings starting with the same $k$ characters for $k$ close to $n$; this is handled in $O(kN)$ steps. Your algorithm suffers badly in this case.


Context-free grammar for tautologies in one variable

Every formula in $p$ is equivalent to one of four formulas: true, false, $p$, $\lnot p$. This suggests having four different nonterminals, which generate exactly formulas which have this truth values. Calling these $T,F,P,N$, we have, for example,
$$
T \to T \land T \mid T \lor S \mid S \lor T \mid P \lor N \mid N \lor P \mid (T) \mid \lnot F \mid \mathrm{true},
$$
where $S \to T \mid F \mid P \mid N$; this additional nonterminal is only used as shorthand.

In the same way, you can write rules that generate all tautologies over any fixed number of variables.


Closure of regular languages under permutation

You can consider the regular language $(ab)^*$. We have
$$ \mathrm{Perm}((ab)^*) \cap a^*b^* = \{ a^n b^n : n \geq 0 \}, $$
which isn't regular. If you take instead $(abc)^*$ and intersect with $a^*b^*c^*$, you get the language $\{ a^nb^nc^n : n \geq 0 \}$, which isn't even context-free.
In contrast, the class of context-sensitive languages is closed under permutation. To see this, it suffices to observe that you can nondeterministically permute the input without any additional space (for example, by applying an arbitrary number of transpositions).


What's the reason for the second condition of the pumping lemma(s)?

Consider the language of words over $\{a,b\}$ consisting of words with an equal number of $a$s and $b$s. This language is context-free but not regular. To show that it is not regular using the pumping lemma, you start with the word $a^pb^p$ and pump $y$, which must consist solely of $a$s. Without condition (2), this wouldn't work: you can pump $ab$ (in the middle) and remain inside the language. Moreover, for any word that you start with, you will be able to find one of the substrings $ab,ba$ which you could then pump.

Similar considerations show that condition (2) is needed for proving that the language over $\{a,b,c\}$ consisting of those words having an equal number of $a$s, $b$s and $c$s is not context-free.


A)

  First of all because we want Reverse the accepting state would become the start and the rejecting states will become accepting, also change the direction of the edges to the oppositse side.

You're almost there. What happens if you have multiple accepting states in the original DFA? That's where you need NFA capabilities to convert them.

Here is a spoiler in case you want to check your answer: Designing a DFA and the reverse of it on ComputerScience.SE.

B)

Your answer is true although you might want to phrase it a bit more carefully. We want to prove "if $L$ is not regular, $L^R$ is not regular". So let $L$ be not regular. If $L^R$ were regular, so were $(L^R)^R = L$, which is a contradiction. Hence, $L^R$ is not regular.


How does the computer know whether an address contains an instruction to be executed, or data to be used in an instruction?

A full answer to this question depends on the underlying computer architecture, as well as on layers of protection that the operating system may add on top of the basic architecture.

In the Harvard architecture instructions and read/write data are held in physically separate memory stores accessed by separate data pathways (buses). It is physically impossible to load a value from the data memory into the instruction register and it is physically impossible for a program to modify its own instructions. Values in the instruction memory may be copied into data registers and then treated as data, but the processor will know this from context e.g. when it sees an opcode "load the next word into Register A", the processor will assume the value in the next address in the instruction memory is a data value to be copied into Register A.

In the more flexible von Neumann architecture (which is adopted by most modern computers) instructions and data are held in the same memory and the processor does not see any difference between them. The processor assumes that whatever memory address its program counter points to at the start of an instruction cycle holds an instruction, and it will load that value into its instruction register and will try to execute it as if it were an instruction.

The danger with the von Neumann architecture is that the processor may treat data that was not intended to be executed as instructions, with unpredictable results. Or it may treat its own instructions as data and change them - this is known as self-modifying code, and is usually avoided because it is difficult to understand, test and maintain.

The solution to this danger is to re-introduce a distinction between data and instructions into the von Neumann architecture by using a no-execute bit, which can be implemented at a hardware level or in the operating system software.


What is the minimum required storage for a sparse, depth-first octree?

The number of octrees with $n$ nodes is OEIS sequence A007556:

$$T(n) = {8n \choose n}/(7n+1)$$

I worked this out, incidentally, by writing a short program to generate the first few values of $T(n)$ and then searching for it.

If you had no other information than $n$, then the minimum number of bits required to store an octree with $n$ nodes is $\log\,T(n)$. (We're doing information theory here, so all logarithms are in base 2 unless otherwise specified.) Using Stirling's approximation to the logarithm of the factorial:

$$\log n! = n \log n - n \log e + O(\log n)$$

We find:

$$\log\,T(n) = (24 - 7 \log 7) n + O(\log n)$$

Which works out to $24 - 7 \log 7 \approx 4.349$ bits per node. So to answer the first part of your question, this is the theoretical minimum. You cannot do better than this.

Now we just have to address the second part: How close can we get?

Consider a bit vector of size $8n$, $8$ bits per node, where you put a 1 if the node has a child in that slot, and a 0 if it doesn't. This obviously uses about twice the space theoretically needed.

However, 0's and 1's don't occur with the same frequency. Specifically, given an octree with $n$ nodes, exactly $n-1$ of the bits must be 1 (exercise: why?), leaving $7n+1$ of them 0. The entropy of a bit is, therefore, approximately:

$$H = -\frac{1}{7} \log \frac{1}{7} - \frac{6}{7} \log \frac{6}{7} \approx 0.59$$

So you should be able to compress the bit vector to $8nH \approx 4.733n$ bits.

The actual compression method that I will suggest, because it's easy to understand and doesn't use anything complicated to implement like arithmetic coding, is Elias-Fano coding with parameter $b=2$.

We'll use your octree as an example. The bit vector corresponding to your exanple is:

11000000 01000100 00000000 00000000 00000000

We know that because $n=5$, the number of bits that are set must be $n-1=4$. We work out the indexes of the bits that are set:

$$\left\{0, 1, 9, 13\right\}$$

Or in binary, using $\left\lceil \log(8n) \right\rceil = 6$ bits per entry:

0000 00
0000 01
0010 01
0011 01

I've separated the low order $b$ bits for a reason. The compressed representation has two parts, one for the high-order bits and one for the low-order bits.

For the low-order bits, we just store these in an array. That is:

00 01 01 01

For the high-order bits, we count the patterns. Since there are no indexes that are larger than $8n-1=39$, There are only 10 possible patterns for the high-order bits:

$$\{0000,0001,0010,0011,0100,0101,0110,0111,1000,1001\}$$

We count the number of indices with each of the high-order patterns, and then encode those counts using a unary code:

110 0 10 10 0 0 0 0 0 0

(In practice, you probably don't need to work out all the high-order bit patterns, just stop when you run out of indices. But I digress.)

On this example, the representation uses 8 bits for the first array, and 14 bits for the unary-encoded bit vector, for a total of 22 bits, or 4.4 bits per node.

Recall that the asymptotic theoretical minimum is 4.349 bits per node.

Working out the asymptotic size of this representation as $n \rightarrow \infty$ is left as an exercise. So is actual code to do the compression and decompression.

Finally, I know you didn't ask about algorithmic efficiency, but storing the bit vector in an SDArray with succinct rank/select indices (there are implementations all over the place; look them up), you should be able to make this data structure random access in close to constant time. That is, you should be able to query the octree in its compressed form. The details are, again, left as an exercise.


Existence of path under weight and value budgets

Here is the idea of the reduction; I'll let you fill in the details.

We are given an instance of the partition problem, consisting of numbers $x_1,\ldots,x_n$ summing to $S$. We construct a (non-simple) graph on the vertex set $s = v_0,\ldots,v_n = t$. For $i=1,\ldots,n$, there are two edges from $v_{i-1}$ to $v_i$: one with weight $x_i$ and value $0$, and one with weight $0$ and value $x_i$. Our target weight and value are both $S/2$.

I'll let you figure out why this works, and convert it to a simple graph.


1/r attractive force by cellular automaton

If by "simulate" you mean something like "generate a picture of what the dynamics would be under such a force," then the answer to your question is yes: there exist universal cellular automata (including Conway's original Game of Life rule set).

If, however, you're asking about whether our universe can be explained in terms of strictly local update rules, then your question is still open.  Konrad Zuse was one of the first to explore this question explicitly in terms of CA; see Wolfram, Schmidhuber, or t'Hooft for more recent work.


What happens when all reference bits set to 1 in Second Chance Page Replacement Algorithm?

Well, I found the answer in a textbook which is saying since there is a pointer looking for a page whose reference bit is 0, it will traverse the circular queue setting all reference bits to 0 and replacing the page who came first like FIFO.


When does the nearest neighbor heuristic fail for the Traveling Salesperson?

Consider a ladder

a----b----c
|    |    |
d----e----f

Say length of a-b is $2$ and length of a-d is $1$. The optimal route is a-b-c-f-e-d-a, $10$ units long. Starting at a, NN would produce a-d-e-b-c-f-a which is $7 + \sqrt{17} > 11$ units long.

There is actually a four node example, a rhombus

  A
 /|\
B-+-C
 \|/
  D

Say length of B-C is $10$, length of A-D is $24$ and thus length of A-B is $13$. The optimal route is A-B-D-C-A, $52$ units long. NN would produce the path A-B-C-D-A, $60$ units long.


Yes $\Theta(logn)$ is correct. By the definition of $\Theta$ notation we can say that some function $g(n)$ is at least $k_1⋅f(n)$ and also it is at most $k_2⋅f(n)$ for considerably large $n$ and $k_1 > 0$ and $k_2 > 0$. If you apply this definition to the heap's height, you will find that the heap's height satisfies this. So, $\Theta(logn)$ is totally correct.


How can a operating system run on more than one CPU architecture?

Operating systems don't detect the CPU architecture.  Instead, you have to ensure that you install the correct version of the operating system given its CPU architecture.  If you make the wrong decision, then the OS won't boot, as the CPU won't understand (either reject or misinterpret) the machine code that you've provided.

The reason's that an operating system is just a program written as a series of instructions for the CPU to execute.  Since different types of CPU's have different instructions, a procedure (program) written (compiled) for one CPU could be gibberish for another.


Easiest way to find y in $x \text{ xor } y = z$ with given $x \text{ and } z$

One can observe that, for any boolean values $a,b,c$, we have
$a=b$ if and only if
$a \text{ xor } c = b \text{ xor } c$.

(To prove that we note that $\Rightarrow$ is trivial, and $\Leftarrow$ follows by xor-ing with $c$ once more and applying the cancellation law.)

Hence, the equation
$x \text{ xor } y = z$
is equivalent to
$(x \text{ xor } y) \text{ xor } x = z \text{ xor } x$
which in turn (by the cancellation law), simplifies to
$y = z \text{ xor } x$.

If we wanted to be more pedantic we could explicitly point out those steps where we also implicitly used associativity, commutativity, and the identity law.


How to prove the language of suffixes of a regular language is still regular?

Your conclusion that $L’$ is a concatenation of two regular languages is wrong.

$L’$ is basically the set of suffixes of all the strings in $L$. Try to prove it for the prefixes and use the “closed under reverse operation” property of regular languages.

Hint for prefix language: make some special states as final state in the DFA of a regular language.


What is a good resource to learn about oriented matroids in the context of digraphs and optimization?

These notes written by Winfried Hochstättler for an MAA short course on matroids look like a good, short, introduction. They also contain references to several longer references on oriented matroids.


Suppose $T_n = O(n)$. That means that for some constant $C$, $T_n \leq Cn$. Therefore $$ \sum_{m=1}^n T_m \leq C \sum_{m=1}^n m = \frac{C}{2} m(m+1) = O(m^2). $$ If also $T_n = \Omega(n)$ then you can show in exactly the same way that the sum is $\Omega(n^2)$, so that no better bound is possible (for concreteness, you can take $T_n = n$).


If $A$ is PSPACE-Complete, then any $A' \in$ PSPACE can be reduced to $A$ in polynomial time. What can you say about a polynomial time reduction from $A'$ to $B$?


This coincidence just shows that the function $n \mapsto 2^n$ shows up in many places. For example, an $n$ bit register can store up to $2^n$ different values. If wireless frequency is parametrized using $n$ bits, then there are up to $2^n$ possible frequencies (in fact, there are probably a bit less). If an IP address is $n$ bits, then there are at most $2^n$ possible IP addresses (in fact, there are fewer). If a cryptographic key is $n$ bits long, then there are $2^n$ possible keys. And so on.


Determining whether $L^*$ is a finite union of $L^n$ for unary regular $L$

We can identify every unary regular language $L$ with the set $S = \{ n : 1^n \in L \}$. It is known that $S$ is eventually periodic, that is,
$$ S = A \cup (B + m \mathbb{N}) = A \cup \{ b + mn : b \in B, n \in \mathbb{N} \} $$
for some finite $A,B$ and $m \geq 1$.
Let us consider four cases:

Case 1. $S$ is empty. In this case, $S^* = S^0$.

Case 2. $S$ is finite and non-empty. In this case, $S^*$ is infinite but $S^0 \cup \dots \cup S^n$ is finite for all $n$.

Case 3. $S = B + m\mathbb{N}$ for some non-empty $B$ and $m \geq 1$. I claim that
$$
B^* \bmod{m} = (B^1 \cup \dots \cup B^\ell) \bmod{m}
$$
for some finite $\ell$. Indeed, if $i \in B^* \bmod{m}$ then $i \in B^j \bmod{m}$ by definition of $B^*$ for some $j \geq 1$ (when $i = 0$ we can take $j = m$), so we can take $\ell$ to be the maximum of the $j$'s. It follows that
$$
S^+ = \bigcup_{i \in B^* \bmod m} n_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m}, \\
S^1 \cup \cdots \cup S^\ell = \bigcup_{i \in B^* \bmod m} n'_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m},
$$
where $n'_i \geq n_i$. It follows that $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ is finite, and so $S^* = S^0 \cup \cdots \cup S^r$ for some finite $r \geq \ell$, since every element in $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ appears in some $S^j$.

Case 4. $S = A \cup (B+m \mathbb{N})$ for some non-empty $A,B$ and $m \geq 1$. Let $C = A \cup B$. As before,
$$
C^* \bmod m = (C^0 \cup \cdots \cup C^\ell) \bmod m
$$
for some finite $\ell$.
Since $B$ is non-empty, $(B+m \mathbb{N})^m$ contains some multiple of $m$, and so all large enough multiples of $m$. Assuming $\ell \geq m$, it follows that
$$
S^* = D \cup \bigcup_{i \in C^* \bmod m} n_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m}, \\
S^0 \cup \cdots \cup S^\ell = D' \cup \bigcup_{i \in C^* \bmod m} n'_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m},
$$
where $D \supseteq D'$ are finite and $n'_i \geq n_i$. It follows that $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ is finite, and so $S^* = S^0 \cup \cdots \cup S^r$ for some finite $r \geq \ell$.

Conclusion. The property $S^* = S^0 \cup \cdots \cup S^n$ holds for some finite $n$ unless $S$ is finite and non-empty. Given a finite automaton for $L$, this condition is easy to check (in linear time).


There is at least one thing that could be wrong with your recurrence, depending on how exactly the algorithm is stated: you are overlooking the case that the element could be found before recursion.


Can heuristic methods and machine learning approaches be considered alternate methods to solve NP-Complete problems?

I haven't seen these lectures, but here's what I think about he questions you pose.

No. NP-completeness is unrelated to the existence of algorithms. For example, we have plenty of problems that we can prove only have an exponential solution. We typically talk about "is there a solution" as decidability. There are problems that have no solution and we call these undecidable. The Halting Problem is a popular example.
Absolutely. When we can't find an efficient solution for all inputs, we find something that works for "most cases". In some cases, we can can prove the solution generated is not worse than K times the true optimal solution. In other cases, we cannot.
Yes.  Machine learning works well for certain classes of problems, but is really hard to apply to others.  It's not a "silver bullet" or alternate solution to computational complexity.

Regards.


Has the problem of finding the most profitable transactions given a set of discrete time series been well-studied?

This can be solved using dynamic programming.  Note that the optimal solution never requires holding more than one type of stock at a time; if you sell a stock, then you might as well sell all of it, and before buying a stock you should sell all existing stock.  This enables a nice solution using dynamic programming.

Here are the details.  Let $A[i,s]$ denote the maximum value of your assets that can be achieved by the end of year $i$, denominated in dollars, if you are holding stock $s$ at the end of year.  Then there is a simple recursive expression for $A[i,s]$ in terms of the values of the form $A[i-1,t]$, based on the idea that either you sell or buy at the start of year $i$:

$$\begin{align*}
A[i,s] = \max(&A[i-1,s] V[i,s]/V[i-1,s],\\
            &\max \{(A[i-1,t]/V[i-1,t] - C) V[i,s] : t \ne s\}),
\end{align*}$$

where $V[i,s]$ denotes the price/value of stock $s$ at the end of year $i$ and $C$ denotes the fixed transaction cost.  Now you can compute these values iteratively, by first computing $A[1,\cdot]$, then $A[2,\cdot]$, and so on.  You can also keep track of which choice was optimal at each step and thereby reconstruct the sequence of transactions as well if you like.


Minimal set of rows and columns covering all non-zero entries in matrix

Your problem can be phrased as minimum vertex cover in a bipartite graph: there is a vertex for each row and column, and each non-zero entry contributes an edge. You can find a minimum vertex cover by finding a maximum matching; see Kőnig's theorem.


on "On the cruelty of really teaching computing science"

This is pretty much what TU Eindhoven's Computing Science education, designed and implemented by Dijkstra and colleagues, was like from the time it started, around 1980, until Dijkstra's influence started to wane, somewhere half way through the 1990s.

I started studying CS at Nijmegen University in 1982; a classmate did the same at TU Eindhoven. Every spring, our old secondary school would have a day on which former students would introduce their chosen field of study to current students, and we were both there to introduce CS, so we compared our experiences. They were vastly different. In Nijmegen, we obtained actual experience with actual programming languages, actually running our assignment programs on an actual computer (a VM/CMS virtual machine, to be precise). Not so in Eindhoven.  My former classmate told me they weren't allowed to touch a computer in the first year. Programming, in Eindhoven, meant learning to mathematically construct provably correct algorithms from mathematically stated problem definitions.  On paper.

This attitude was somewhat relaxed after Dijkstra left, but even in the early 1990s, the courses called Programmeren (Programming), numbered 1 to 9, and spanning several years, still consisted of that same activity, and one in particular presented a major hurdle for the students. I never took any of those courses, but I doubt any use of computers was involved.

In case you're wondering: today's computer science education at TU Eindhoven is very different.


The idea is that
$$
\mathbb{E}[u^{\prime T} v'] = \mathbb{E}[u^T S^T S v] = u^T \mathbb{E}[S^T S] v,
$$
due to linearity of expectation. You can take it from here.


How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs?

There is already an explicit construction of Ramanujan graphs, due to Margulis and (separately) Lubotzky–Philips–Sarnak. Their construction only gives graphs with degree $p+1$ for some prime $p$. Later this was extended to cover prime powers $p$.

Recently, Marcus, Spielman and Srivastava gave a probabilistic construction of bipartite Ramanujan graphs of all degrees, and the paper appeared in FOCS 2013, and is due to appear in the Annals of Mathematics. This construction cannot even be implemented by an efficient probabilistic algorithm, and only works for bipartite graphs. In very recent work, the same authors extend their method to give bipartite Ramanujan graphs of all degrees and all sizes, in work that was submitted to FOCS 2015 (per Adam Marcus's homepage).

The community finds the recent line of work exciting not only because of the results themselves, but also because of the very interesting technique, which while (as far as I understand) not entirely new, has reached a new level of sophistication and applications. Improving on their results, either to get efficient algorithms or to remove the bipartiteness assumption, will likely require new techniques, and so will be exciting for the community.

While both papers mentioned above were submitted to FOCS, this is just due to coincidence; they might as well have been submitted to STOC. There is no real difference between these conferences, other than the time of year in which they take place, and the organization sponsoring them. SODA is considered less prestigious than FOCS and STOC.


Is there an algorithm which can compute every algorithm's time complexity?

It would be great, wouldn't it?
And like most problems regarding Turing Machines (or "algorithms"), there is no such algorithm, and there never will be:

Consider for example the language
$$\{M: M\text{ is a TM that runs in time }O(n^3)\}$$
It is quite easy to reduce the halting problem to this language. Indeed, given input $M,w$ for the halting problem, the reduction outputs a machine $K$ that given input $x$, runs $M$ on $w$, and accepts $x$ iff $M$ halts on $w$, and does not halt otherwise. Since running $M$ on $w$ takes constant time (if it halts at all), then $K$ runs in time $O(n^3)$ iff $M$ halts on $w$.

Thus, it is undecidable (not in $coRE$, to be exact).
There is nothing special about $n^3$, the same reduction works easily for every function greater than $n\log n$ (below $n\log n$ things get a bit more involved).

Also, the Halting problem itself can be regarded as a sort of "run-time problem", in the sense that you don't even ask what the runtime of an algorithm is, but just whether it halts. Even that is undecidable.

It is interesting to note that the language, as formulated in this answer, is also not in $RE$, it is an easy exercise to show it. However, if you replace the $O(n^3)$ with exactly $n^3$, then the problem is in $coRE$. Then, the former reduction needs certain adjustments, but the problem is still undecidable.


How are conditionals implemented at hardware level?

The semantics of any non-jump CPU instruction is to increment the program counter PC (a.k.a. instruction pointer) so that the subsequent instruction can be executed next.

Uncoditional jumps overwrite PC with a new, fixed value, written in the instruction. (Or, for relative jumps, add to PC said value)

Conditional jumps instead consider two possible values for PC: one pointing to the next instruction, another written inside the instruction (possibly as a PC increment, for relative jumps). Then, they test some given register, obtaining a bit. For instance, the register might be a flag, which is taken as is. Otherwise, the register might be tested for parity, sign, zero, etc. so to obtain a single bit. This bit controls which one of the two PC values is the one to write in the PC register. Usually, a hardware commutator is responsible to choose between the two ones, exploiting the control bit.


How to construct a Turing machine for a language

Try to come up with an algorithm, and then write the simplest possible program in some usual programming language for recognizing L. Then translate that program to a Turing machine.

N is not "in base 10" - it's just a number in your computer's memory, which is probably internally represented in base 2, but your program shouldn't care.

To check if a number contains 1 in base 3 representation, try to build the base-3 representation using the usual base conversion algorithm (digit = x mod 3, proceed with x div 3), and stop when you see a 1.


We always measure the running time of a machine with respect to input size. For this reason, your language is in P. Given a sequence of moves, you can easily check in polynomial time that the sequence is valid.
You can construct a language in $R \setminus \mathit{NP}$ using diagonalization. This is the content of the nondeterministic time hierarchy theorem.


How to generate regular expression for language of regular expressions?

Let us consider first a simpler situation, in which you have only one "atom" $a$, only one binary operator $\circ$, and no unary operator. The expressions you are captured by
$$
X (\circ X)^*, \quad X = a+[a(\circ a)^*].
$$
In order to get an actual regular expression, substitute $X$ (surrounded by parentheses) in the left expression.

Adding a postfix operation $\star$ isn't too difficult:
$$
Y (\circ Y)^*, \quad Y = A+[A(\circ A)^*]\star^*, \quad A= a\star^*.
$$

In order to get an actual regular expression, first substitute $A$ into $Y$, then $Y$ into the leftmost expression.

Finally, the expression you are looking for only differs in that there are several "atoms" and several binary operations:
$$
Z (\circ Z)^*, \quad Z = B+[B((\cup + \circ) B)^*]\star^*, \quad B= (0+1+\underline{\epsilon}+\underline{\emptyset})\star^*.
$$
Here $\underline{\epsilon},\underline{\emptyset}$ are the versions in your alphabet.


No, it doesn't mean that FNP = NP.  NP is a class of decision problems; FNP is a class of function problems.  See the definition of FNP (e.g., on Wikipedia, or in any textbook).  Therefore, the elements of NP have a different type than the elements of FNP.

It's like asking whether the set of tart apples is equal to the set of seedless oranges; one is a set of apples, the other is a set of oranges, so they're certainly not equal, and you don't need to know anything about exactly which apples are tart or which oranges are seedless to know that.


How to validate a connect X game (Tick-Tak-Toe,Gomoku,...)?

One approach that may be useful is to represent your field by a matrix and use a matrix vector product to test whether there is a winning position. Suppose we are playing connect $3$ and are testing whether player $A$ wins by a horizontal row, in this field:

A A A _ B
B _ _ B _
B B _ B A
A A _ A A

Construct a matrix $M$ by representing player $A$'s pieces by $1$, player $B$'s pieces and empty fields by $0$:

$M = \begin{pmatrix}
1 &1&1&0&0\\
0 &0&0&0&0\\
0 &0&0&0&1\\
1 &1&0&1&1\\ \end{pmatrix}$

Now, multiply the matrix by the vector $v=(1,2,4,8,16)^T$:

$Mv = (7,0,16,27)^T$. As we are looking for adjacent $1$'s, we see that there is a value in $Mv$ equal to $7$ ($=1+2+4$), $14$ ($=2+4+8$), $28$ ($=4+8+16$), $15$ (=$1+2+4+8$), $30$ ($=2+4+8+16$) or $31$ ($=1+2+4+8+16$).

Since the first entry of $Mv$ is equal to $7$, we know there is a row of three $1$'s there.

In general, for a $k\times n$ size grid, we take the vector $v=(1, 2,4,\ldots , 2^i,\ldots, 2^n)^T$ and know that there is a connected line of length at least $x$ when any of the values $\{\sum_{i=j}^{j+y} 2^i \mid 0\leq j \leq n-y, x\leq y< 2x\}$ are present in the vector $Mv$. (we can take $y<2x$ as when $y\geq 2x+1$, there must have been a row of length $x$ already on the field)

To test for columns, we can simply take the transpose of the matrix.

To test for diagonals, rotate the field such that they become rows and add padding to construct a rectangle: e.g. given our playing field above, a rotation for a diagonal would be:

_ B _ _
_ _ _ _
A B A _
A _ B A
A _ _ A
_ B B _
_ B A _
_ A _ _

(Note that it doesn't matter whether we place the padding to the left or the right, as we only check rows)


Does a computation tree for a probabilistic Turing machine have to be a binary tree?

There are many ways to think of how a probabilistic Turing machine works.  One way is to imagine that it has the ability to flip a fair coin (sample a random bit) at any point.  In that case, it's reasonable to imagine a binary tree, where each branch corresponds to a coin flip -- the fact that we are choosing a random bit / flipping a 2-sided coin is why it is a binary tree.  Another way to think of a probabilistic Turing machine is that it has an additional input tape that is full of random bits.  There you could imagine a binary tree, which each branch corresponds to another bit on that additional input tape.

Typically probabilistic Turing machines can sample a random bit, i.e., a random number from the set {0,1}.  If you want a random number from a different range, you must emulate that by repeatedly sampling random bits and doing something with them.


Absolute orientation alignment with vectors

A simple modification of Horn's approach can be made to incorporate local rotation information: rather than just matching the centers of the body (trajectory points), use several off-centered points on the body such as the endpoints of a tied reference frame (in a way, forming dipoles, quadrupoles, octupoles...). Then use Horn's method on this augmented point set.

By adjusting the remoteness of these points from the center, you can trade good translational fitting for good rotational fitting.

This aside, you can probably develop a method based on static equilibrium of two solids (formed by the whole trajectories), where elastic forces are developed between corresponding points as a function of distance and torques as a function of misalignment.

CAUTION: in case there is significant scaling difference, you will need to adjust the remoteness proportionally to the size of the whole trajectory, otherwise artificial discrepancies will arise because of rescaling.


Proving that a set of operations can't generate one integer from a given one

If you have implemented breadth first search correctly, you should have found that 1889 can be reached.
$\quad 2019+7\to 2026$
$\quad 2026+7\to 2033$
$\quad\quad\cdots\quad$ (add 7 repeatedly)
$\quad 4238+7\to 4245$
$\quad 4245 \div 3 \to 1415$
$\quad 1415 * 2 \to 2830$
$\quad 2830 * 2 \to 5660$
$\quad 5660 + 7 \to 5667$
$\quad 5667 \div 3 \to 1889$
It is possible that you had been asked to show that 1883 can't be derived from 2019.
A number can be derived from 2019 iff it is a positive integer not divisible by 7
Proof:
"$\Longrightarrow$": If $n$ is not divisible by 7, neither is any of $n+7$, $n*2$ and $n/3$ (when $n$ is divisible by 3). If we start with a number that is not divisible by 7, it will remain not divisible by 7 regardless of how many operations we have applied on it. Since 2019 is not divisible by 7, we cannot derive any number that is divisible by 7.
"$\Longleftarrow$":
In fact, we can derive all positive numbers not divisible by 7 without the operation $n\to n * 2$. For all $k\ge0$,

$\dfrac{2019 + 7 * (((7k+1)*3^{6k+7}-2019)/7)}{3^{6k+7}}=7k+1$
$\dfrac{2019 + 7 * (((7k+2)*3^{6k+11}-2019)/7)}{3^{6k+11}}=7k+2$
$\dfrac{2019 + 7 * (((7k+3)*3^{6k+6}-2019)/7)}{3^{6k+6}}=7k+3$
$\dfrac{2019 + 7 * (((7k+4)*3^{6k+9}-2019)/7)}{3^{6k+9}}=7k+4$
$\dfrac{2019 + 7 * (((7k+5)*3^{6k+8}-2019)/7)}{3^{6k+8}}=7k+5$
$\dfrac{2019 + 7 * (((7k+6)*3^{6k+10}-2019)/7)}{3^{6k+10}}=7k+6$

Exercises
Exercise 1. Assume the same three operations. Let $n$ be a positive number not divisible by 7. Then a number can be derived from $n$ iff it is a positive integer not divisible by 7.
Exercise 2. Assume the same three operations. Let $n$ be a positive number divisible by 7. Then a number can be derived from $n$ iff it is divisible by 7.
Exercise 3. If positive integer $m$ can be derived from positive integer $n$ using the three operations, then $m$ can be derived from $n$ using the first and last operations, namely, $n\to n+7$ and $n\to n/3$ (if divisible).


Hint: Given an instance $\{x_1,\ldots,x_n\},T$ of SUBSET-SUM, construct the instance $\{2x_1,\ldots,2x_n\},2T$ of your problem.


What is the branch of Computer Science that studies how Anti Virus programs work?

There is a subarea of computer security called Computer Virology. The Journal of Computer Virology is devoted to the topic. Studying how anti-virus software works only scratches the surface of what the area is about.

For instance,  there is even some work applying logic to malware: A General Definition of Malware by S. Kramer and J.C. Bradfield. Journal of Computer Virology (6) 2010.


Examples of maximal paths in undirected graphs

We can say a path is maximal if you cannot add any new vertices to it to make it longer. You can contrast this with a path of maximum length: it is the longest path in a graph (so it is also maximal, but note the difference). A bit informally, when something is "maximal", it means you cannot add anything to it to make it larger. When something is "maximum", it is globally the largest "object" there is.

For an example, consider the tree pictured in this Wikipedia article. The path on the vertices $\{1,2,4\}$ is maximal; you cannot add any vertex to it to make it longer. But a maximum path (i.e., longest path) in the tree is on the vertices $\{ 1,4,5,6 \}$. Clearly, it is no problem if the graph you consider contains a cycle. For example, then you can see that not every vertex of the graph can be in a longest path.


In a 32-bit floating number with normalized mantissa and excess-64 exponent base 16, the number $16^{-65}$ denotes

The format you are using is not IEEE-754 but an IBM FP format.  The mantissa is fractional, so the binary representation 0001_0000_0000_0000_0000_0000 means 0.1 (base 16).  With a zero value in the exponent field, the exponent would be -64.  So you can see that $16^{-65}$ would be the smallest normalized positive value ($1 * 16^{-1} * 16^{-64}$)


Integer LP formulation and the existence of a solution

Express this problem as an integer linear program in which the variables take on values on [0,1]

$$\begin{align}
\text{max: } &\sum_i^m y_i \cdot p_i - \sum_j^n x_j \cdot s_j &\\
\text{subject to: } &x_i \geq y_j &\forall i \in L_j \\
 &0 \leq x_i \leq 1 &\forall i \\
 &0 \leq y_j \leq 1 &\forall j
\end{align}$$

We see that if we select an investor $y_j$ we must select all of the investor's actors $x_i$ for $i \in L_j$. Our profit is the residual income left over from paying actors.

  Show that there must in fact be an integral optimal solution (as is the case, for example, with maximum flow and bipartite matching)

If our constraint matrix $A$ is totally unimodular, then the relaxed LP is sufficient to give a 0-1 solution.

Sketch: Observe that $A$ is an $N \times M$ matrix where $N = n + m$ and $M = \sum_j^m |L_j|$. This defines an incidence matrix of a bipartite graph where each row corresponds to an edge $(y_j, x_i)$ with coefficients $(-1, 1)$. We see that any cycle in the graph defined by $A$ will be balanced. That is, for any cycle $C$, $\prod_{e \in C: e=(u,v)} A_{e, v} = 1$. The proof for this can be done using the fact that any cycle in a bipartite graph is even. The corollary to this is that the incidence matrix for any balanced signed graph is totally unimodular.


Yes and yes.

Any key that doesn't mess up the sort order can be used. Typically (in my experience), this is the minimum value from the right subtree. However, I'm not aware of any specific scenario where this would cause a problem either way.

When you delete a key (one practice I have seen is that) you delete the key along with the value. So, if you delete "Gold" you also delete all the keys with the value "Gold", so that no "Gold" remain. This wasn't done in this case and it's perfectly fine.

The thing about B tree and variants is that there are several ways you can implement them without violating any of the B tree properties. This leads to subtle differences like the one you've observed.


Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?

I learned the following argument from Dieter van Melkebeek (but any mistakes are my own). I'm not sure that this is what Arvind and Mukhopadhyay had in mind, because the assumptions are not the same, as I point out after the argument. I am still interested in learning alternative proofs.

The idea will be to start with the collection of all subsets, and iteratively fix it by removing subsets until the conditions are satisfied. This is similar to the deletion method from the probabilistic method.

We will iterate the following algorithm:

F := Powerset([n])
While there is some i in [n^c] such that w_i makes F min unique:
    Update F by removing the element with min w_i weight.

It suffices to show that this algorithm terminates with a non-empty set $F$.

To wit, note that each time we find such an $i$, the minweight of $F$ under $w_i$ increases by at least $1$. Since the max weight of any set under $w_i$ is $n^{c' + 1}$, this means that for each weight $w_i$, we can update $F$ at most $n^{c' + 1}$ times during the algorithm. Thus, in total $F$ is updated at most $n^{ c + c' + 1}$ times. Since each step removes one set from $F$, this means that $F$ is nonempty at the end of the procedure provided that $2^n > n^{ c + c' + 1}$.

Additionally, at the end of the process $F$ can be culled to size at most $2n^{c}$, by picking two min-weight sets for each $w_i$ $i \in [n^c]$.

Since we delete up to $n^{c + c' + 1}$ sets from $F$, we only need to work with a universe of set systems of size ${2^n \choose n^{c + c' + 1} } = O( 2^{(n^{c + c' + 2})})$. This makes me think that this argument is not the one that uses the fact that there are $2^{2^n}$ set systems.


Is rejecting in polynomial time required for language to be in P?

Suppose you have a problem $A$, and a TM $M$ which accepts all the words $w \in A$ within a polynomial time bound $p(|w|)$, and diverge (or reject) otherwise.

Then, we can craft a new TM $N$, which on input $w$ performs the following:

simulate $M$ with input $w$ for $p(|w|)$ steps;
if $M$ accepts, we make $N$ accept as well
otherwise we make $N$ reject

It is immediate to see that $N$ runs in polynomial time: simulating a step of $M$ requires polynomial time on the $M$ configuration (whose size remains polynomial during the whole simulation), and we only need a polynomial number of steps.

Further, $N$ decides $A$ by construction.

TL;DR: if we know we can only accept a word within a time bound $t$, we can set an alarm on $t$. When the alarm rings, if we have not accepted before, we know it's a reject.

Conclusion: your alternative definition of $P$ is equivalent to the regular one. I would argue that it is harder to work with in proofs, though.


What other instructions are stored in the ROM?

You store software in ROM for security, because it cannot be modified. Especially when your device’s operating system is updated, you want that to be controlled by software in ROM so you can detect fake or hacked software updates in a way that cannot be hacked.


Given a set C of set P of sets R, find the smallest set S such that at least one subset R from each P is a subset of S

Your problem is NP-hard, by reduction from Monotone SAT.

Recall that Monotone SAT is (the decision version of) the following problem: given a CNF formula $\varphi$, find a satisfying assignment with the fewest variables set to true.

Now, map each clause, say $x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k}$, in $\varphi$ to a set $P=\{R_1,R_2,\dots,R_k\}$ where $R_1=\{x_{i_1}\}$, $R_2=\{x_{i_2}\}$, etc.  Finally, form $C$ to be the set of $P$'s obtained in this way from the clauses of $\varphi$.  Then a set $S$ satisfies $C$ iff it corresponds to a satisfying assignment for $\varphi$ (including the element $x_i \in S$ corresponds to setting $x_i$ to true in the assignment), so the minimal-size set $S$ that satisfies C corresponds to the minimal-size satisfying assignment for $\varphi$.

Since Monotone SAT is NP-hard, your problem is NP-hard, too.

If you need to try to find an exact solution in practice, you could try formulating your problem as an instance of SAT and feed it to a SAT solver (using binary search over the size of $S$), or you could formulate it as an instance of integer linear programming and feed it to an ILP solver.


Is this algorithm bubble sort or selection sort?

Yes, the code written by your friend implements the selection sort. It is not exactly how the selection sort is usually implemented, though.

What is done in your friend's code?

At the first iteration where i=0, it finds the smallest element by comparing the element at index 0 with all other element, swapping if necessary so that the minimum element so far will stay at index 0.

At the end of this iteration, the smallest element is at index 0.
At the next iteration where i=1, it finds the next smallest element by comparing the element at index 1 with all other element except the smallest element, swapping if necessary so that the next smallest so far stays at index 0.

At the end of this iteration, the smallest and second smallest element is at index 0 and 1, respectively.
At the next iteration where i=2, it finds the next smallest elements by comparing the element at index 2 with all other element except the smallest element, swapping if necessary so that the next smallest so far stays at index 2.

At the end of this iteration, the first 3 smallest elements are sorted at index 0, 1 and 2.
And so on.
Finally, at the beginning of last iteration where i=9, the first 9 smallest elements are sorted at first 9 indices. The 10th smallest elements, which is also the largest element in this 10-element array, must have been at the last index.

So the sorting is done.

Your friend implements the selection sort.

Let us check what is selection sort. According to the Wikipedia article, here is the idea of selection sort.

  The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

We can verify that your friend's code implements exactly that idea above. In fact, if you replace int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; with int arr[5]= {11, 25, 12, 22, 64};, updating the bounds accordingly, your friend's code will produce exactly the same sublists at end of each outer loop as shown in the example in Wikipedia.

Your friends' code is different from how the selection sort is usually implemented. The common implementation uses an index iMin to track the minimal element while your friend uses the element at the expected location to track the minimal element.

Your friend's code runs slower than the usual implementation because it uses much more swaps in average although both implementation uses exactly the same number of comparisons, $n(n-1)/2$. On the other hand, it uses no more swaps than a bubble sort.

Your friend's code is simpler to write and ends up even shorter than the common implementation, supporting the claim "selection sort is noted for its simplicity".

You may want to enjoy visualization of various sorting algorithms at Topal.com.

Exercise

If arr[j] > arr[j + 1] in your code is changed to arr[j] < arr[j + 1], what is the result? Does it implement bubble sort still?
If arr[i] > arr[j] in your friend's code is changed to arr[i] < arr[j], what is the result? Does it implement selection sort still?

Show that your friend's code uses no more swaps than a bubble sort. Give an example when your friend's code uses less swap than a bubble sort.


Is X+Y sorting problem still an open problem?

Here the problem status is "open". The page was revised in 2006 and it seems updated to September 2017, so we can safely suppose that the problem is still open.
Anyway, an algorithm that solves the problem using $O(n^2)$ comparison (and total complexity $O(n^2\cdot \log(n))$) is known from 1992: J.-L. Lambert, Sorting the sums $x_i+y_j$ in $O(n^2)$ comparisons, Theoretical Computer Science, (1992):103, 137–141 doi 10.1016/0304-3975(92)90089-X.


Decide $\{a^nb^n\mid n>0\}$ in log space

The hint that you have pretty much solves the problem.
Essentially you need two counters; one for a and one for b.

If the first occurrence is not an a, you reject.
Start counting as. You will encounter n of those, until the end of input, or you find a different character. When you stop reading as, at that point you have n in binary. Essentially, every time you read an a, you simply perform addition in the counter that is used for counting as.
If you have reached the end of input, or if the next character is not b, you reject.
Start counting bs in the same manner as you were counting as until you reach the end of input or encounter a different character. You will read at most n bs, by checking every time that you read a b if you have read less than n characters. This is again straightforward because the two counters for a and b are in binary. If you read a different character you reject. If you reach the end of input after n bs, then you accept; otherwise reject (there is another character coming up - might even be a b).

Thus, we need O(log(n)) space.


Show by induction on the height $h$ of the tree that a tree of height $h$ has at least $2^{\frac{h}{2}}$ nodes.
The base case $h=0$ is easy since a tree of height $0$ has $1$ vertex and $1 \ge 2^\frac{0}{2}$.
Suppose that the claim holds up to some $h \ge 0$. Consider a tree $T$ with height $h+1$ rooted in $r$. Let $u$ and $v$ be the children of $r$. Let $n(x)$ and $h(x)$ denote the number of nodes and the height of the subtree of $T$ rooted at $x$, respectvely.
We must have $h(r) = 1 +\max\{h(u), h(v)\}$. Suppose w.l.o.g. that $h(r)=1+h(u)$. Then, regardless of whether $u$ is the left or right child of $r$, we have $\frac{n(v)}{n(u)} \ge \frac{1}{2}$, i.e., $n(v) \ge \frac{n(u)}{2}$.
$$
\begin{align*}
n(r) &= 1 + n(u) + n(v) > n(u) + \frac{n(u)}{2} = \frac{3}{2} \cdot n(u) \\
&\ge \frac{3}{2} \cdot 2^{\frac{h(u)}{2}}
= \frac{3}{2} \cdot 2^{\frac{h(r)-1}{2}}
= \frac{3}{2} \cdot 2^{\frac{h}{2}}
> 2^{\frac{1}{2}} \cdot 2^{\frac{h}{2}} =  2^{\frac{h+1}{2}}.
\end{align*}
$$
This concludes the proofs, and shows that a tree with $n$ nodes has height at most $2 \log n$.


Polynomial Identity Testing $(\mathsf{PIT\text{}})$ in non commutative setting

PIT and PIT1 are not equivalent. For example, $xy-yx$ is the zero polynomial in the commutative setting but not in the non-commutative setting. You can get a non-commutative analog of EZE by considering large enough matrices, where large enough depends on the formal degree of the polynomial involved.

Suppose that $P$ is a multivariate polynomial in $x_1,\ldots,x_n$ which is not identically zero. We want to find a point where it is non-zero. The proof is by induction on $n$. If $n=0$ then $P$ is some non-zero constant, and there is nothing to prove. If $n>0$, write
$$ P = \sum_{i=0}^d Q_i x_n^i, $$
where the $Q_i$ are polynomials in $x_1,\ldots,x_{n-1}$, and $Q_d$ is not identically zero. The induction hypothesis shows that $Q_d(\alpha_1,\ldots,\alpha_{n-1}) \neq 0$ for some real $\alpha_1,\ldots,\alpha_{n-1}$. Making this substitution, we obtain a univariate polynomial $P'$ in $x_n$ which is not identically zero. If $|\alpha_n|$ is large enough, simple estimates show that $P'(\alpha_n) \neq 0$, and so $P(\alpha_1,\ldots,\alpha_n) \neq 0$.

Here are the simple estimates: if $P' = \sum_{i=0}^d c_i x^i$ and $|\alpha| \geq 1$ then
$$
|P'(\alpha)| \geq |c_d| |\alpha|^d - \sum_{i=0}^{d-1} |c_i| |\alpha|^i \geq
|\alpha|^{d-1} |c_d| \left(|\alpha| - \frac{\sum_{i=0}^{d-1} |c_i|}{|c_d|}\right).
$$
This is non-zero if $|\alpha| > 1+\sum_{i=0}^{d-1} |c_i|/|c_d|$.


Average Case runtime for random choice search

The probability you find the element in each guess is $1/n$. The number of guesses until you find it is a geometric random variable with success probability $1/n$, whose expectation is $n$.

Your formula is wrong – the probability to find the element after $k$ steps is $(1-1/n)^{k-1} (1/n)$.


Shamos-Hoey Line segment intersection runtime

The BST is ordered with a "above/below" relationship. The idea is that for any "event", the BST is ordered by the y-value where each line segment intersects the x-value of that "event".

When a segment is inserted or deleted, the comparisons in the BST are between the y-value of each line segment at the x-value of the current event. This can be computed with geometry in constant time given the slope of each line. The ordering only requires a single update at each event (a little subtle); the BST requires no other maintenance.

In your example, at the 2nd event when C is added, it is actually inserted above A. Then the B/C intersection would be found correctly.


Prime factorization for compressing streams of random numbers

No.  If it is a stream of random bytes, where each byte is independently and uniformly distributed, it cannot be compressed.  It doesn't matter what method you're using.  You're trying to do something analogous to inventing a perpetual motion device; we don't have to look at the detailed blueprint to know that it won't work.


Pumping Lemma Proof (Type of wcw language)

The structure of the language i think can be explained as (based on definition above) $\{a^n b^n ~c~ a^n b^n |c \in \{a,b\} \}$

As explained in the comments, this is a wrong inference. If
$$
L = \left \{ d k d ~|~ d \in \{ a, b \}^{*}, k \in \{a, b\} \right \}
$$
then $d$ can be any finite sequence (of any length) of $a$ or $b$ terminals. Recall that, for an alphabet $\Sigma$, Kleene star is defined inductively as
\begin{align}
\Sigma^0  & = \{ \epsilon \} \\
\Sigma^n  & = \{ \omega a ~|~ \omega \in \Sigma^{n - 1}, a \in \Sigma \} \\
\Sigma^{*}  & = \bigcup_{n \ge 0}{\Sigma^n}
\end{align}
So for example
$$
\{ \epsilon, a, b, ab, ba, abab, abbb, baba \} \subset \{ a, b \} ^{*}
$$
while instead
$$
\{ a^n b^n | n \ge 0 \} = \{ \epsilon, ab, aabb, aaabbb, \ldots \}
$$
To tackle your problem, I can recommend negating the Pumping lemma and then

Fix an arbitrary $N > 0$
Take $\omega = a^N b a^N$ with $d = a^N$ and $k = b$
Equate $\omega = xyz$ and note that it must be $|xy| \le N$ and $|y| > 0$

Can you conclude your proof?

 We just chose our $\omega \in L$. We must show that, whatever our decomposition, $\exists k \ge 0. ~ x y^k z \not \in L$. Let $x, y, z$ be such that \begin{cases} \omega & = xyz \\ |xy| & \le N \\ |y| & > 0 \end{cases} then, whatever $y$, for $k = 0$ you always have \begin{equation} x y^0 z = a^M b a^N \end{equation} with $M \neq N$.  Thanks @plop for strenghening the proof.


Give a specific case where calling a polynomial time function n times gives an exponential time algorithm

A concrete example is repeated squaring. Squaring an integer of length $n$ takes time $O(n^2)$ (using the naive algorithm; you can do much better with more complicated algorithms). If you square an $n$-bit integer $i$ times in a row, its length becomes $2^i n$. So if you square it $n$ times in a row, the complexity is $O(4^n n^2)$, which is exponential.

The source for confusion is the input length. If the polynomial time function increases the length, then the behavior can be exponential. If it doesn't, the behavior stays polynomial.


A* graph search heuristicfor pathfinding

There is nothing wrong with the heuristic function you suggest. Note what the consistency condition actually says: If you have nodes $n_1,n_2$, and the cost of traveling from $n_1$ to $n_2$ is $c$, then the heuristic values need to satisfy a triangle condition: $h(n_1)$ must not be more than $h(n_2)+c$. It is ok for $h$ to underestimate the distance from a node, as it does for your start node (though obviously, the performance of the algorithm can suffer in this case).


How to figure out whether two texts refer to the same object or event

This is a document clusterization problem. A general solution is to define some sort of distance between documents and apply a standard clusterization algorithm, such as k-means or expectation maximization. There are different approaches to picking distance measure $L$:

Build a common vocabulary and convert each document into a bag of words, i.e. a long vector consisting of zeros and ones of length $|Vocab|$. Then let $L$ be the Hamming distance between these two representations.
Compute word2vec embeddings of each word in a document and average them (can be also weighted by TF-IDF -- see this question on SO for details). This will produce a dense $d$-dimensional vector per each document. The distance $L$ can then be defined as Euclidean, Minkowski or more sophisticated distance on vectors in $\mathbb{R}^d$.
Compute doc2vec embedding directly. Once again it's a dense $d$-dimensional vector per document, so the same choice of vector distances applies.


By “final state” I assume you mean “accepting state”.
The answer is no, as the accepting state should have an empty string $\epsilon$ for it to be meaningful.

You can of course define a transition relation that consumes everything after it has reached an accepting state. It will act as a prefix detector.


can network layers communicate between each other?

No. Ultimately, for two computers to communicate, something physical (such as a bunch of electrons or photons) must pass between them and that's the lowest possible level of the OSI model.

In general, though, you shouldn't view the layers too rigidly. They're a vocabulary for talking about networking, rather than a requirement for writing network protocols.


I see two possible points of confusion in your question, and I will address them separately.

What is meant by the title of your post: ""Regular languages over a common alphabet are closed under union."
"The union of $L_1,L_2$ is $\{x:x∈L_1∨x∈L_2\}$
Does this mean that, for any string $s∈L_1$, we also have $s∈L_2$?"

What is "Closure Under Union"?

Regular languages are a class of languages that exhibit the closure property with the union operation.

The closure property means that when an operation is applied to language(s) of a certain class the resulting language will also be of that class.

In this case the class of languages is the regular languages and the operation is union.

So all this means is that the union of two regular languages is also a regular language.

What is the union of two languages?

Languages can be thought of as sets of strings, so the union operation works the same way as in typical Set Theory.

I would read $\{x:x∈L_1∨x∈L_2\}$ as "the set of strings such that the string is in $L_1$ or the string is in $L_2$."

This does NOT mean that for any string $s∈L_1$, we also have $s∈L_2$.

We only have that for any string $s$ in the union of languages $L_1$ and $L_2$, denoted $s \in (L_1\cup L_2$), that string $s$ is in either $L_1$ or $L_2$.


You can upper-bound your probability using a union bound.  In particular,

$$\Pr[\exists x \in S . \phi(x)] \le \sum_{x \in S} \Pr[\phi(x)].$$

Using a union bound we obtain ${M^s \choose 2}$ terms in the sum, and each term is upper-bounded by $1/N^s$, so we find that your probability is at most

$${M^s \choose 2}/N^s.$$

If $M < \sqrt{N}$, then this probability will be at most $1/2$.  If $M \gg \sqrt{N}$, then this probability is close to $1$.

(Qualitatively, this upper bound is fairly close to tight for a wide range of settings of $M,N$.  I am not going to prove this fact, but you can take my word on it.  So there's not much hope for a significantly better bound using some other proof technique.)

In short: as Yuval Filmus says, unless $M$ is very small, your event is actually pretty likely.

No, something stronger than $s$-independence will not help.  Even if you assume that $h$ is generated uniformly at random from the set of all hash functions with the right signature (something that is not actually implementable), you don't get a much better bound.

The only plausible approach I can see is to choose a hash function $h$ that does not have any collisions at all: e.g., choose $h$ from a family of injections, or use a perfect hash.  Each of these has serious shortcomings: the former requires $M<N$, and the latter typically requires you to know in advance the full set of values that you will ever compute $h$ on.


Note that $\#P\in FP^{PP}$ follows from a simple binary search. Given some non-deterministic machine $M$, the language $\{(x,k) |\#M(x)\ge k\}$, where $\#M(x)$ is the number of accepting paths on input $x$, is in PP (you can change the constant in the definition of PP to any FP function). Thus, using a PP oracle we can count the number of accepting paths via binary search.
This implies that $\mathsf{P=PP}$ puts permanent in $VP$, as the problem of counting the number of perfect matchings in a bipartite graph (or equivalently, computing the permanent of the adjacency matrix) is in $\#P$.


Checking equality of integers: O(1) in C but O(log n) in Python 3?

Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit.

Not quite. C ints are machine-word-sized and compared with a single machine instruction; Python ints are represented in base $2^{30}$ (see e.g. https://rushter.com/blog/python-integer-implementation/) and compared digit-by-digit in that base. So the relevant base of the logarithm is $2^{30}$.
If at least one of numbers can be bounded by $2^{30d}$ for any fixed $d$, the comparison is $O(1)$ (because the number of digits is compared first), and if they can't, other operations are likely of much more concern than equality comparison. So in practice I'd say it's very unlikely to matter and if it does you'll know (and would be using not ints but something like the GNU Multiple Precision Arithmetic Library in C as well).


Machine with an oracle for a language that cannot decide another language in polynomial time

Let $A,B$ be two incomparable Turing degrees (these can be constructed by diagonalization, known in this context as forcing). If $P^A \subseteq P^B$ then in particular $A \in P^B$, and so $A$ reduces to $B$; since we know this is impossible, we can conclude that $P^A \nsubseteq P^B$. Similarly $P^A \nsupseteq P^B$.


Identifying set of longest time periods excluding overlapping time ranages

Your problem is known as weighted interval scheduling, and can be solved using dynamic programming. It's a nice exercise. You can find the solution in these lecture notes as well as in many other places.


Given an oriented graph, return true if paths have a specified length

Let's say a vertex $v$ is at distance $t$ from the set $A$ if there exists a path of length $t$ from some element of $A$ to $v$; and there is no shorter path.

Can you think of an efficient way to compute the distance from $A$ to each individual vertex in the graph?

Perhaps you might like to modify BFS.  Hint:

   Maybe you can think of some way to change the initialization, to make BFS do what you want.


Finding the kth smallest element of an array using DAC

The problem is in your rand_partition(p,q) function.

I made some changes with comments.

def rand_partition(p,q):
    i=randint(p,q)               # get a random index between p and q
    swap(i,q)                    # move the pivot element to the end
                                 # after now, do the same as normal partitioning
    pivot=lst[q]                 # save pivot
    s=p-1
    j=p
    while(j < q):                #keep invariants (this would be better with a for loop):
        if(lst[j] <= pivot):     # lst[p...s] <= pivot,
            s+=1                 # lst[s+1...j-1] > pivot
            swap(s,j)
        j+=1

    swap(s+1,q)                  # put the pivot in the correct place
    return s+1

Also, you can set a base case for select(p,q,k) (although this is not critical):

def select(p,q,k):
    if (p==q):
        return lst[p]
    #...

For more info: Introduction to Algorithms (Cormen, Leiserson, Rivest & Stein)


Is there a concept called "white waveforms" in computer science?

I suspect you might have misheard.  I suspect the lecturer said "takes the file decodes it generates the right waveforms and so on"  (right, not white).


Algorithms that run in polynomial time if P=NP

Wikipedia is describing Levin's universal algorithm. This is an algorithm for verifiable problems, which is competitive with the optimal algorithm (in some sense). In particular, the exact same approach would work for any problem in NP, not just SUBSET-SUM.


Adapt a one-tape turing machine's algorithm that find the center of a string in O(nlog(n)) to find the first third

Let's start with a new way of computing the center. First of all, it's not so clear what to do with a string of even length. Fortunately, it doesn't matter, since we can fix it once and for all: initially, we determine the parity of the length of the input, and then add one symbol at the beginning or end (according to the definition of center for strings of even length).
From now on, we assume that we are given a string of odd length. Here is the idea in a nutshell:
\begin{align}
&\verb|XXXXX| &\verb|XXXXXXX| \\
&\verb|X X X| &\verb| X X X |
\end{align}
In words, we erase part of the input so that the remaining string has the same center. How we do this exactly depends on whether the input has length $4n+1$ or $4n+3$.

Let's move on to your case. The $1/3-2/3$ midpoint is well-defined for strings of length $3m+1$. You can reduce to this case by adding one or two symbols to either end of the string as before, so let us assume that our string has length $3m+1$. We again consider two cases, according to the parity of $m$:
\begin{align}
&\verb|XXCXXXX| &\verb|XXXCXXXXXX| \\
&\verb|X C X X| &\verb| X C X X Y|
\end{align}
We have highlighted the center using the letter C.
If the string has length $6n+1$, then we simply cross of every other letter. If the string has length $6n+4$, then we cross of every other letter (starting from the second), and then remove the final letter (which we denoted by Y in the example).


If you want to cover the entire tree then your algorithm must run in $\Omega(n)$, assuming $n$ is the number of nodes in the tree. You are right, however, that you could optimize the code by checking that the child is non-empty before calling the function. This is an optimization that the compiler probably wouldn't do on its own. This optimization could improve your algorithm, but its running time will still be asymptotically $O(n)$ (assuming $O(1)$ processing per node); at most you improve the constant.


Reducing minimum vertex cover in a bipartite graph to maximum flow

According to König's theorem, the size of minimum vertex cover in bipartite graph $G$ equals to the size of maximum matching in $G$, and there is an obvious reduction from maximum matching in bipartite graph to maxflow problem.


What is the error when using Levenshtein distance on flattened binary trees?

This approximation is essentially arbitrarily bad.

Suppose you have a complete binary tree $T$ containing $2^k - 1$ nodes, of which the bottom $2^{k-1}$ are leaves.  Let $u$ and $v$ be the left and right child of the root, and $U$ and $V$ be the subtrees rooted at these vertices, respectively.  Let $w$ be the rightmost leaf in $U$.  To transform $T$ into a tree in which the locations of the leaf $w$ and the entire subtree $V$ have been swapped (so that the new tree has height $2k-1$) requires $2^{k-1}-1$ deletions of all nodes in $V$, the deletion of $w$, followed by the same number of insertions -- but the Levenshtein distance between the corresponding strings is just 2: delete the single list element corresponding to $w$ (from just before the half-way point of the string) and append it to the end.

(Well, possibly up to 2 tree-edits can be saved by turning pairs of insertions and deletions into substitutions.)


Give a computation of the expression to normal form (Lambda calculus)

Usually, a series of applications $f\,x_1\,x_2 \dots$ means $\big(\big((f\,x_1)\,x_2\big)\,\ldots\big)$. We say that application is left associative.

According to this convention, there is an extra set of parentheses that is implied in the expression you write. Here I've made it explicit:
$$\big((\lambda f.\lambda g.\lambda x. f \,(g\,x))\,(\lambda u.u)\big)\,(\lambda v.v)$$

The expression $(\lambda f.\lambda g.\lambda x. f \,(g\,x))$ is a function and it is applied on input $(\lambda u.u)$. Reducing this will result to a function of the form $(\lambda g. \lambda x. \langle\text{body}\rangle)$, which in turn gets applied to $(\lambda v.v)$.


Polynomial time counter of solutions of 2SAT expression with pure literals

Counting the number of satisfying assignments in a positive 2SAT formula is the same as counting the number of vertex covers in the corresponding graph (after removing singleton clauses). Counting the number of vertex covers is known to be $\mathsf{\#P}$-complete. See also this question on cstheory.


IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary?

Start by initializing a boolean array $T$ with indices from $0$ to $b$, inclusive. $T_0$ starts as true (because you can always achieve a sum of 0) and the rest of the array starts as false.
For each value $a_i$, we update the array by going though each value $x$ where $x+a_i\leq b$, and setting $T_{x+a_i}$ to true only if $T_x$ is true.
Essentially, at any point, the array describes which sums are possible using only the values of $a$ which have already been looked at. When a new $a_i$ is looked it, any value that can be made by adding $a_i$ to a currently possible sum becomes possible.
The final decision simply involves checking if $T_b$ is true.
The bulk of the program involves iterating over all $n$ values of $a$ and all $b$ elements of the array, for a total runtime of $O(nb)$. The size of the input is at least $n+b$, because it describes each value of a $a$, and $b$ is written in unary.
Because $O(nb)$ is polynomial with respect to $n+b$, the described problem can be decided in polynomial time.


Is the language $L=\{a^{2^{n}} \mid$ n is a natural number$\} $ context free?

Suppose that $L$ is CFL then $L$ is regular because it is a unary language. So exist a constant $N$ associated to $L$ by the pumping lemma for regular languages.

We choose the word $\sigma = a^{2^N}$ and $|\sigma| = 2^N > N $ so the pumping lemma should complies for $\sigma$. Then exist a factorization of $\sigma = \alpha \beta \gamma$ such that:

1) $|\alpha \beta|\leq N $

2) $|\beta|\geq 1$

3) $\alpha\beta^i\gamma \in L \forall i \in \mathbb{N}_0$

$|\alpha\beta^i\gamma|= 2^N + |\beta|(i-1)$ choosing $i=2$:

$|\alpha\beta^2\gamma|= 2^N + |\beta|$ so:
$$2^N+1\leq|\alpha\beta^2\gamma|\leq 2^N+N$$
$$2^N<2^N+1\leq|\alpha\beta^2\gamma|\leq 2^N+N<2^N +2^N$$
$$2^N<|\alpha\beta^2\gamma|<2^{N+1}$$

Then $|\alpha\beta^2\gamma|$ can't be a power of 2(with natural exponent) so $\alpha\beta^2\gamma\notin L$ and we find a contradiction. Finally $L$ can't be regular and it is not CFL too.