What can you do with lambda calculus if you aren't allowed parentheses?

Answer 1

The best answer to this question is: This is the wrong question to ask! Let me explain.

The fact that we write down expressions (in $\lambda$-calculus or anywhere else) as sequences of symbols is a convenience and tradition established by humans. From a theoretical point of view the strings of symbols are not the optimal way of representing expressions. Instead, abstract syntax trees are.

Abstract syntax trees do not require any parentheses. Parentheses are there only because we use a particular way of writing things. There is nothing deep in having or not having parenthesis. Your question then boils down to the following: "Suppose we use a notation which requires parentheses, but then we remove parenthesis, what happens?" This is not a mathematically interesting question. It can be answered, but it's irrelevant for $\lambda$-calculus. The answer might be interesting, but it will not reveal anything about parentheses. Instead, it will reveal something about abstract syntax trees of a certain shape.

Were you born in a slightly different universe, where everyone used reverse Polish notation then you would not have known that there is such a thing as parentheses.

Let me put it another way. It is a convention that in $\lambda$-calculus we write $a\,b\,c$ to mean $(a\,b)\,c$. Without such a convention we would always have to write parentheses everywhere, all the time. The first person to establish the convention could have picked the other one, so that $a\,b\,c$ would mean $a\,(b\,c)$. Then your question would have a different answer because of some person who picked a convention a long time ago.

Answer 2

It is not entirely clear where you think parentheses are needed, but let's suppose that

application is left-associative, so that $x y z = (x y) z$, and
$\lambda$-abstraction has lower precedence than application, and it binds as much as it can, so that $\lambda x . x y z$ and $(\lambda x . x y) z$ are different expressions.
You think that $x \lambda y . y$ is not a valid expression because it should be written as $x (\lambda y . y)$. That is, a $\lambda$-abstraction in an aplication must always be parenthesized.

Under these conditions, we cannot ever write any $\beta$-redeces (because we would have to apply a $\lambda$-abstraction). So any expression must be of the form $\lambda x_1 . \lambda x_2 . \ldots \lambda x_n . M$, possibly with $n = 0$, where $M$ is of the form $y_1 y_2 \ldots y_m$ for some variables $y_1, \ldots, y_m$ (which may be equal to the $x_i$'s).

If anyone can say anything interesting about this fragment of $\lambda$-calculus, I'd be interested to hear.


Algorithm to find all acyclic orientations of a graph

As Yuval noted, you can count the number of acyclic orientations by evaluating the chromatic polynomial of a graph at negative unity. For computing chromatic polynomials, there are efficient algorithms known for some graph classes.

There is also a recursive algorithm for generating all acyclic orientations of a graph given by Squire [1]. The algorithm requires $O(n)$ time per acyclic orientation generated. Roughly 20 years ago this was the fastest algorithm known; it's possible a faster one is known now, or that you can improve Squire's algorithm by known techniques.

[1] Squire, M. B. (1998). Generating the acyclic orientations of a graph. Journal of Algorithms, 26(2), 275-290.


Should I keep a relevant constant in the Time Complexity?

In asymptotic notation constant factors are "modded out". For example, an algorithm runs in time $O(n)$ iff it runs in time $O(2n)$ iff it runs in time $O(n/2)$.

If you want to capture such a difference meaningfully, you have (at least) two options:

Add another parameter. There could be a parameter $t$ such that your algorithm runs in time $O(tn)$. One way to think about it is that the algorithm runs in time $O_t(n)$, i.e., with a big O constant that depends on $t$, and the dependence on the big O constant on $t$ is $O(t)$.
Count a specific operation. In some cases you might be able to count a specific type of operation more accurately. For example, perhaps one sorting algorithm performs $(2 \pm o(1)) n\log n$ comparisons on average, and another performs $(3 \pm o(1)) n\log n$ comparisons on average.


Where can I find a data set of graphs with known domination numbers?

One place to look is House of Graphs, which is a database of "interesting" graphs. For instance, there are graphs that have been used as counterexamples to various conjectures, have extremal properties with respect to some parameter, and so on. For more, see [1].

Another possibility is using Mathematica, which also has a database of graphs accessed through its GraphData-function.

[1] Brinkmann, G., Coolsaet, K., Goedgebeur, J. and Mélot, H., 2013. House of Graphs: A database of interesting graphs. Discrete Applied Mathematics, 161(1), pp.311-314. --- Free version at arXiv


Proving that no finite automaton can recognize a Dyck language

Consider a Dyck language $L$ with $k$ types of parentheses, one of them $()$. If $L$ were regular then $L \cap (^*)^*$ would be regular, but this is just the well-known non-regular language $a^nb^n$ (with $a,b$ replaced by $(,)$).

There are many ways to prove that $L' = \{a^nb^n : n \geq 0\}$ isn't regular. Here is one. Suppose that $A$ is a DFA recognizing $L'$, with states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$. Let $q(i) = \delta(q_0,a^i)$. If $i < j$ then $q(i) \neq q(j)$, since otherwise $\delta(q_0,a^ib^i) = \delta(q_0,a^jb_i)$ although the former is in $F$ while the latter isn't. This implies the absurd conclusion that $Q$ must be infinite.


Correctness of following algorithm for 3-QCNF?

Your code ignores quantification levels.  Formulas prefixed with
$\exists{x_1}\forall{x_2}$ are not supposed to be evaluated the same way as those prefixed with $\forall{x_1}\exists{x_2}$.  Your code treats them the same, moving one existential quantifier ahead of all the other quantifiers in each of your 2-QBF subformulas.


Characterising $(aa)^*$ in first order logic

Short answer. There is no such first-order formula, you need a monadic second order formula.

Details. This can be proved directly using an Ehrenfeucht-FraÏssé games argument if you want to stay inside logic, but the real answer to your question is the conjunction of three results.

[1] Büchi (1960): A language is monadic second order expressible iff it is regular.
[2] McNaughton-Pappert (1971): A language is first-order expressible iff it is star-free.
Counter-free Automata. Research Monograph 65. With an appendix by William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9.
[3] Schützenberger (1965): A regular language is star-free if and only if its syntactic monoid is aperiodic.  On finite monoids having only trivial subgroups

[3] gives an algorithm to decide whether a given regular language is star-free (and hence, first-order expressible, by [2]). Now, the syntactic monoid of $(aa)^*$ is the cyclic group of order $2$, which is not aperiodic. To get a monadic second order formula, you need first to have first order "macros" to express $\min$, $\max$ and $+1$ and then the following second order formula will do the job
$$
  \exists X\ \forall x\ (\min \in X \wedge \max \notin X) \wedge (x \in X \leftrightarrow x+1 \notin X)
$$


is it necessary to cover all the verticies in eular path?

It really comes down to your definition of an Euler trail. The one I'm familiar with is similar to the one on Wikipedia:

  An Euler trail is a trail (path that allows repeats) that uses every edge exactly once.

With this definition, an Euler trail doesn't have to touch every vertex: if there's a vertex with no edges, the Euler trail doesn't have to go anywhere near it.

However, if there's a vertex with positive degree, and another vertex with positive degree, and they're not (weakly) connected, then there can be no Euler trail. Because if you use the edges on one, there's no way to reach the edges on the other.


Complexity classes: What if different algorithms exist for different sizes of input?

What you are describing is non-uniform algorithms. You have to be careful when defining them. For example, consider the following algorithm, for inputs of length $n$:

  Look up the answer in a large table.

If this algorithm runs in polynomial time in your model, then the non-uniform version of your computation model can compute all decision functions.

There are two common ways to define non-uniform computation models in complexity theory: using advice and using circuits.

Advice. One possibility is to have a uniform algorithm (working for all input lengths) which gets an additional "advice" which only depends on the input. Let's see how such an algorithm can efficiently decide the following language:

$$ L_H = \{ w : \text{the $|w|$th Turing machine halts on the empty input} \}. $$

(Here $|w|$ is the length of $w$.)

The algorithm gets an auxiliary advice $a_n$, and just returns $a_n$. The advice $a_n$ is simply whether the $n$th Turing machine halts on the empty input.
Incidentally, this example shows that non-uniform models can compute uncomputable functions.

One standard complexity class which can be defined in this way is $\mathsf{P/poly}$, which consists of all decision problems computable by polynomial time algorithms having access to a polynomial size advice.

Circuits. Cook's theorem shows (essentially) that if $L$ can be decided in polynomial time, then for every $n$ we can construct a polynomial size circuit deciding the length $n$ instances of $L$. These circuits are uniform in the sense that they can be constructed by an algorithm.

This suggests the following natural non-uniform model: polynomial size circuits. In this model, for every input length we can supply an arbitrary polynomial size circuit (that is, there is a polynomial $p(n)$ such that the $n$th circuit has size at most $p(n)$). Every problem in $\mathsf{P}$ can be decided in this model, as mentioned above. But this model is much more powerful — indeed, it can compute the uncomputable language $L_H$ mentioned above: the $n$th circuit either computes the constant 0 function or the constant 1 function. It turns out that this circuit model is exactly equivalent to the class $\mathsf{P/poly}$ defined above.

Non-uniform models of computation are important in complexity theory, since many lower bound techniques apply directly to them. For example, one approach for proving $\mathsf{P} \neq \mathsf{NP}$ which used to be popular is proving superpolynomial lower bounds for circuits computing some NP-complete problem such as $\mathsf{SAT}$. Nowadays this approach seems less promising. But various weaker non-uniform models are the object of intensive study in complexity theory.


Is it possible to transmit bits digitally?

HDMI interface is one example of being able to tranmit high-speed digital data. It works using an encoding technique called TMDS (Transition Minimized Differential Signaling) which you can read more about here
Also, HDMI can only be used with older analog-only devices (using connections such as VGA, etc.) by means of a digital-to-analog converter or AV receiver, as the interface does not carry any analog signals from Wikipedia


Connected Graph: Select the minimum number of nodes such that the node and neighbor covers everything

This depends on what you mean by "straight forward". There's a very straight forward brute force algorithm - it just doesn't have very good performance.

As to which problem this is, I would say it is Dominating Set. A vertex cover is also a dominating set, but not every dominating set is a vertex cover (i.e. a vertex cover might be significantly larger than a dominating set).

As for straight forward algorithms with good performance, you're not in a good spot.

It is NP-complete, so no polynomial-time algorithm unless $P = NP$.
It is $W[2]$-complete, so no $FPT$-algorithm unless $W[2] = FPT$.
It has no $n^{o(k)}$ algorithm unless the Exponential Time Hypothesis fails.
It is also $Log$-$APX$-complete, so no $o(\log n)$ approximation algorithm unless $P = NP$.

The best algorithm I know of at the moment is a $O(1.4969^{n})$ exact algorithm, but I don't think that would satisfy the "straight forward" criterion.

Even on restricted classes of graphs, you're unlikely to get good running times.

If you graphs happen to have very small treewidth, local treewidth, or are planar, then there are FPT algorithms, but again, they're not exactly "straight forward".

If you do want to solve Vertex Cover however, then it's still hard, but you have a few more possibilities:

Vertex Cover has a 2-approximation (find any maximal matching, and take all the vertices in the matching).
Vertex Cover is FPT, and has a number of kernelization algorithms of varying complexity (the more complex ones give significantly better running times). This paper contains details on a relatively simple one and this one the current best.
It is also amenable to a number of optimization approaches, and if you have access too something like CPLEX, then the ILP is easy to formulate, and relatively fast to solve.


Metrics and algorithms for complexity of a graph

You can use all sorts of properties of a graph this way; obviously how good they are for you depends on your purpose.

Non-comprehensive list of graph attributes, for general undirected graphs:

Compare simple graph attributes: $|V|$, $|E|$, $\frac{|E|}{|V|}$; you must decide if more or less is considered "more complex".
Obviously if the graph has multiple components, you can use that, as a measure of simplicity or complexity; and/or you can consider it multiple separate graphs.
Treewidth of the undirected graph; computing the treewidth of a graph is exponential-time in the treewidth, $k$; however, you can set $k$ to a constant, and compute the treewidth quickly (wrt. size of the graph) and consider graphs with higher treewidth to be "complex"
How "planar" a graph is

Crossing number (NP-complete problem to compute)
Compare the resulting Kuratowski subgraphs when planarity testing fails (such forbidden graphs can be extracted quickly, but there can be a large number of such graphs)

Presumably a higher number means that there are more non-planar crossings required, thus it is more complex.
Sparseness, average vertex degree, vertex degree distribution

A low average degree, with a nice distribution can indicate an evenly sparse graph, thus perhaps lower "complexity". Easy to compute, simply average the degree of each vertex over all of them; distribution is slightly more complicated I suppose; depends on how you choose to do it; see wikipedia on degree distribution.
Average eccentricity (see wikipedia on Distance (graph theory)), eccentricity distribution
Diameter, radius ratios. Example: large diameter, low radius (see (see wikipedia on Distance (graph theory)); test ratios of these on "complex" and non-"complex" graphs, see if it diffrentiates.
Compare the dimensions of the graphs (NP-hard)
Have some subgraphs you consider "complex", and test for subgraph isomorphism in your actual graphs (NP-complete), or, use Maximum common subgraph isomorphism (NP-hard)
Perhaps some sort of compressibility/entropy measure, but this touches on isomorphism; the same graph can be layed-out or represented in a matrix multiple ways, not all of them equally compressible. A canonical graph labeling could help with this, but that is itself difficult.

Some ideas for an FSM:

Size (though note that you can have equivalent FSMs of different sizes; these measurements are about the graph complexity, not necessarily FSM complexity)
You can do a topological sort or level structure, and compare them that way; possible measures of complexity: depth, level-width.
You can do a DFS, and detect cycles; perhaps more cycles == more complex?

Counting cycles can be a hard problem (NP-hard). Perhaps you can find some relaxation for your specific graphs, for example if they are planar (I don't know that counting cycles in planar graph is any easier, but you would start searching for special cases based on what special cases you do know). There are some approximation algorithms for general cycle counting though. See Counting cycles in an undirected graph using DFS-XOR algorithm, (IEEE paywalled off); abstract:

  We present an algorithm for counting the number of cycles in an undirected graph. The given algorithm generates exact results but it is not guaranteed to run in a polynomial time. Afterwards, an approximated version from the algorithm guaranteed to run in a polynomial time was introduced. The obtained results was used to measure the entropy of graphs. Entropy represents robustness of the graph under analysis. An experiment is conducted to compare the results of our algorithm with the results of another algorithm based on the Donald Johnson backtracking algorithm.


How to make single cycle processor pipelined?

If every complete operation takes one cycle, then pipelining using the same cycle time won't give you any advantage whatsoever.

What you would do is to split up each operation in various parts. First you make the cycle say four times shorter, so now each operation executes in four cycles. Then you split each operation into say five parts, and you have a first stage doing the first part and moving the results to the second stage, then a second stage doing the second part and moving it to the third stage, and so on. It will take all in all a little bit longer because you need the time to move data from one stage to the next.

And now you have five different stages, you can start pipelining. The first stage does the first part and moves the result to the second stage in the first cycle, and in the second cycle it starts work on the first part of the next instruction and so on.

You win because now the cycle time is four times shorter, so you can do up to four times more operations per second, working on up to five instructions at the same time.


After a while I look back on this problem. It turns out using universal gates to generate constant-qubit gates would make no difference to BQP class. The gate complexity, however, depends on $\epsilon$ for the error we try to bound, but precision could be reached in $poly(-\log{\epsilon})$ number of operations.


Every AVL tree can be colored to be a red-black tree

Here is a computer verification of your method.
The height discrepancies occur when we are making a red root, in which case the shorter child with the reduced black height would also have a red root. Since there can't be two consecutive red nodes, we need to turn the shorter child black, which increases its black height to match the taller child.


Proof of Lower Bound for Deterministic Distinct Elements Algorithm

Consider the following argument:

  If $0 > 1$ then $1 > 2$.

Proof: Starting with $0 > 1$, add $1$ to both sides.

Since it is not true that $1 > 2$, we can conclude that $0 > 1$ is also false.

The same is true in your example. Starting with some assumption A, you prove property B. However, property B is clearly false, so assumption A must have been false as well. Don't forget that you can derive everything from False.


This paper [1] provides a consensus algorithm in a model where, in each round, each node can query 2 randomly chosen nodes and update its own value accordingly. As this is essentially a balls-into-bins scenario, the load balancing will be very good. It is shown that this "converges" to a consensus within $O(\log n)$ rounds even if an omniscient adversary corrupts up to $O(\sqrt{n})$ values of the nodes in each round.

I would say the main reason why many protocols have a leader is for having a coordinator that orchestrates the progress of the protocol. Note that most classic work on consensus focuses on achieving the best possible fault-tolerance, whereas load balancing as not always a primary concern.

[1] Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, Christian Scheideler: Stabilizing consensus with the power of two choices. SPAA 2011: 149-158
http://www.cs.ox.ac.uk/people/leslieann.goldberg/papers/SelfStabilizing.pdf


Do Approximation Algorithms Analyzed in the Worst Case?

It's a worst case guarantee. It can in some cases do better than $\rho OPT$, but it will never do worse.

In your example we can say very little about the algorithm since you've only tested it with relatively few random instances of a given size. On non-random (structured) inputs it might perform much worse.


How to show that a $\log_2(x)$ is a recursive function?

Once you have proved that $|x-2^y|=0$ is a decidable predicate, the function
$$\log_2(x) \equiv \mu y(|x-2^y| = 0)$$
should match the description of the function given and proves that it is recursive.

Edit:
To show that $|x-2^y|=0$ is decidable, show that $\overline{\text{sg}}(|x-2^y|)$ is recursive, which requires you to show that $|x-z|$, $2^y$, and $1 - \text{sg}(z)$ are recursive, then use substitution.

$|x-z|$ can be defined as $(x-z) + (z-x)$ where cut-off substraction is used in the latter and you can use $x^y$ is a primitive recursive function to show that $2^y$ is recursive. $\text{sg}(z)$ is computable by noting that $\text{sg}(0)=0$ and $\text{sg}(z+1) = 1$.


You often see negative variables ($\neg x$) and positive variables ($x$). A literal is either a positive or a negative variable.


When we interpret CA rules in a canonical form bijective with the naturals, it's convienient to think in terms of a lookup table array indexed by a neighborhood into the next cell state, or rather a truthtable with a variable from each of the neighborhood cells.

This works when the number of states is a power of two. If not a power of two, you need to use a mixed-radix encoding to remain bijective with the naturals.

The choice of 22369621 as an example rule hints that you haven't fully grasped how many potential rules there are with a neighborhood of 25 binary state cells mapping into the next binary state center cell. I assume this rule was chosen because its length up to the most significant one is 25, which shows you might be thinking that it only requires 25 bits to fully encode any rule from this type.

However, 25 (2-state) neighbors -> 1 (2-state) center cell requires in the worst case 2^25 bits, not 25.

Let's take a more simple example from the von Neumann neighboorhood: 5 (2-state) neighbors -> 1 (2-state) center. This requires at most 32 (2^5) bits.

So now let's take a random number within 32 bits, such as 3427859663.

In binary this is 11001100010100001111110011001111. We can intrepret these 32 bits as the next cell lookup for each of the configurations those 5 cells in the neighborhood can be in:

  a        *
b c d -> * f *
  e        *

~a ~b ~c ~d ~e ->  f
~a ~b ~c ~d  e ->  f
~a ~b ~c  d ~e -> ~f
~a ~b ~c  d  e -> ~f
~a ~b  c ~d ~e ->  f
~a ~b  c ~d  e ->  f
~a ~b  c  d ~e -> ~f
~a ~b  c  d  e -> ~f
~a  b ~c ~d ~e -> ~f
~a  b ~c ~d  e ->  f
~a  b ~c  d ~e -> ~f
~a  b ~c  d  e ->  f
~a  b  c ~d ~e -> ~f
~a  b  c ~d  e -> ~f
~a  b  c  d ~e -> ~f
~a  b  c  d  e -> ~f
 a ~b ~c ~d ~e ->  f
 a ~b ~c ~d  e ->  f
 a ~b ~c  d ~e ->  f
 a ~b ~c  d  e ->  f
 a ~b  c ~d ~e ->  f
 a ~b  c ~d  e ->  f
 a ~b  c  d ~e -> ~f
 a ~b  c  d  e -> ~f
 a  b ~c ~d ~e ->  f
 a  b ~c ~d  e ->  f
 a  b ~c  d ~e -> ~f
 a  b ~c  d  e -> ~f
 a  b  c ~d ~e ->  f
 a  b  c ~d  e ->  f
 a  b  c  d ~e ->  f
 a  b  c  d  e ->  f

Besides the approach of luts for CA, there are other data structures (or canonical numberings) that tend to remove the redundancies found in the most relevant designed rules that utilize large neighborhoods and especially non-power-of-two states. A good resource for more information about these techniques can be found at the Golly webpage.

http://golly.sourceforge.net/Help/formats.html

Some techniques listed there are:

Rule tables
Rule trees (also known as n-ary decision diagrams)


Do we understand when metaheuristics are optimal? (gradient descent & simulated annealing in particular)

In general, we definitely don't know this. In fact, it's practically always so that a-priori, we don't know how well a particular metaheuristic performs (let alone proving optimality) on a given instance (or family of instances) until we try.

It should also be noted that we usually go for metaheuristics only when the problem is so hard it seems unlikely it admits an algorithm that is always fast and correct (i.e., the problem is NP-hard). Put differently, when a problem is solvable in polynomial-time with some other methods, we don't even bother considering metaheuristics.

So if a metaheuristic is always optimal (and assuming it always runs in polynomial time), then the problem must be in P (assuming that P is not equal to NP). Of course, no one is stopping you from taking a problem that is known to be in P and applying a metaheuristic on that, but that's probably not that useful anymore.


There are two reasons that counter-example wouldn't "imply that we've inverted".

(a)

Despite that answer's (probably-not-necessarily-correct) opening sentence,

it's only a counterexample to "$h$ is necessarily one-way", not to "$h$ is one-way".

(b)

That answer's attack does not require inverting  $\hspace{.04 in}f(x_1) \oplus f(x_2)$  "to $x_1x_2$",

it just involves finding a preimage of  $\hspace{.04 in}f(x_1) \oplus f(x_2)$  under $h$.


How to determine the pre and post conditions of a program (Hoare-logic)

Here are two other programs that have the same postcondition given the same precondition:
y = 1;
while (y < x) {
    y = 100 * y;
}

x = y = 1;

Your postcondition doesn't describe the output it enough detail. In particular:

The program doesn't change $x$.
The value of $y$ is the smallest power of 10 which is at least $x$.


If $L = \{ a^{2^n} \mid n \ge 0 \} $ is not regular, then why there is a DFA thats accepts its language?

The definition of an automaton accepting a language is that it must

accept every string that is in the language;
reject every string that is not in the language.

Your automaton does 1. but not 2. – it accepts all strings of $a$s, but it's supposed to reject all the strings whose length is not a power of two.


Evolving expert systems with machine learning

I have been interested in this question and started simple experiments. The idea is to have a basic axiom set that cannot be changed combined with dynamic extension and sensor input. Genetic algorithms add axioms. There can be many sets existing at the same time. In an additional step integration of the sets is attempted by replacing n-ary predicates with (n+m)-ary predicates.

Example: virtual rats learn ways through mazes. There are several mazes and rats can learn any of them. Each maze defines a mapping of sequences of go-left/straight/right decisions to reward/n-reward consequences. The height of the reward also depends on the number of rats that found the way before. The variation is maintained because there is competition, so when a rat variant knowing one maze becomes frequent then knowing a less commonly known maze would become more valuable. In addition to the mazes, there are regularities in the dynamics of the environment, something like: type-1 maze will change to type-2 after 100 runs and change back after 50 runs. This allows the integration of different strategies because switching after frustration is
usually good thanks to the relative stability of conditions.

I did not get beyond initial steps before I had to focus completely on a commercial project again. But I would love to resume work on the idea. If you find more information, please let me know: peter.krall@red-queen-innovations.eu


Logic applications and security protocols references request

I really like the phrase, as well as the book, that logic is calculus of computation. It is kind of hard to find an area in computer science where logic is not used. I will just mention few areas where knowing logic comes in handy.

Verification. Techniques of logic are heavily used in verification area. Specification of hardware and software systems is usually given as logical formulas. Depending on what properties are being checked, such systems are also modeled by appropriate logic (propositional, FOL, modal logics, linear logic, etc.). Methods like satisfiability and model checking are usually used to check whether a system meets its specification. Moreover, there is an area of decision procedures that tries to come up with efficient procedures for checking satisfiability of formulas in various logics (by most first order theories). In general, you might want to take a look at automated theorem proving.
Programming languages. As pointed earlier, there is a deep connection between programming languages and logic. By Curry-Howard isomorphism, every functional program is isomorphic to some proof in constructive logic. Logic is also used for defining axiomatic semantics of programming languages; see Hoare logic. Prolog is a programming language based on a paradigm where computation is specified by logical formulas. Lambda calculus was first intended as a formal logical system aimed to laying foundations of mathematics, but turn out to be more useful as a programming language. It is now at the core of every functional programming language.
Misc. You might also be interested in the way logic and computability interplay. What might be specially interesting to you is descriptive complexity. Logic is also getting more attention in computational biology. It is also used in AI for knowledge representation.

Hope this gives you some kind of a starting point.


Decidability. $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$

Corollary 3.19 from "An Introduction to the Theory of Computation": "A language is decidable if and only if some nondeterministic Turing machine decides it."

You can construct a nondeterministic Turing machine, $TM_A$, which is a decider for the language : $A_DFA = \lbrace \langle B,w \rangle \mid \text{$B$ is a DFA accepting $w$}\rangle$.

$TM_A$ works as follows on input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is a string:

Simulate $B$ on input $w$.
If the simulation ends in an accept state, accept. If it ends in an non-accepting state, reject.

Update:
The string $a^kb^k$ is not regular and cannot be accepted by a DFA. A CFG for that string would be something like : $A \to aAb \mid \varepsilon$.


As for your first question, the reason behind adding $1^n$ as an input to $A$ is to allow it a running time of (at least) a polynomial in $n$. In most applications of one-way functions, $n$ is not a secret, so there is no reason to hide it; in fact, for most functions you can determine $n$ from the output size.

To see what fails if we leave $1^n$ out, consider the situation in the second question. You're misreading the notation - $|x|$ is the length of the string $x$. If $x$ is $n$ bits long then $|x|$ is $O(\log n)$ bits long, and so no machine can find a preimage in time polynomial in $|x|$. However, it is easy to find a preimage in time polynomial in $n$. Add ing$1^n$ as a parameter to the adversary $A$ ensures that $|x|$ is not considered a hard function.

Finally, one-way functions, weak or strong, are not known to exist, even assuming P$\neq$NP. This is similar to the situation in computational complexity, where no worst-case hard functions are known. However, some functions are conjectured to be one-way - ask your professor for their favorite ones.


Has it been shown or can we show that if $SAT \in P$ then SAT can't be in any complexity class C so that $C \subsetneq P$?

SAT is NP-hard with respect to NC$^0$ reductions, and in particular, it is P-hard with respect to NC$^0$ reductions.
Now let $C$ be a complexity class which is closed under NC$^0$ reductions. If SAT is in $C$ then every problem in P can be reduced to $C$ using NC$^0$ reductions, and so belongs to $C$, implying that $C$ contains P.


Boolean Algebra : Using identities, prove x(x + y) = x

Solution:
$$ \begin{align}x(x+y)
&= (x\cdot x)+(x\cdot y) \quad\text{[Distributive Law]} \\
&= x + (x\cdot y) \quad\text{[Idempotent Law]} \\
&= x \cdot (1+y) \quad\text{[Distributive Law]}\\
&= x \cdot 1 \quad\text{[Property of 1]} \\
&= x \quad\text{[Property of 1]}
\end{align}$$


Probability of selecting a particular set, by sampling without replacement from a categorical distribution

For each $\Sigma \subseteq [k+1]$, you can compute the probability $q(\Sigma)$ that the first $|\Sigma|$ elements to appear are $\Sigma$ using the following recurrence: $q(\emptyset) = 1$ and when $\Sigma \neq \emptyset$,
$$
q(\Sigma) = \sum_{\sigma \in \Sigma} q(\Sigma-\sigma) \frac{p_\sigma}{p_\sigma + \sum_{\tau \notin \Sigma} p_\tau}.
$$
You are interested in $q([k])$. The total computation time is $O(k2^k)$ (ignoring arithmetic), if you compute the sum in the denominator in tandem. Perhaps this could be improved to $O(2^k)$.


Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random

I am not 100% sure this answer is correct, but here goes:
I think you can reduce this to uniformly random any-paths, from $s-t$, in a DAG with a single source and a single sink.
Given a graph $G$

Make a new empty digraph, $H$.
First: run the BFS part of Dijkstra's shortest-path, starting from $s$, mark all the nodes with their shortest-distance-from-$s$.
Let $d(s,v)$ be the minimum distance from $s-v$; which we know from the BFS step of Dijkstra's shortest-path algorithm.
Then do the next step of Dijkstra's shortest-path algorithm, obtain the shortest-path, store it in $\mathbf p$ (by going backwards from $t$ to $s$).
Now start the following loop; expanation in comments, and below:

$q_0=\{t\}$
While $q_0 \ne \emptyset$

$q_1= \emptyset$
For $u \in q_0$

So we want to find all possible next nodes for this shortest-subpath from $t-u$
For all $\text{edge}(u,v) \in G$ such that $d(s,v) < d(s,u)$

$v$ is a neighboring node, with less $d(s,\cdot)$ (it will be $1$ less)
Therefore, $t-u-v$ is possible subpath in a shortest path.
Put $v \rightarrow H, \text{di-edge}(u,v)\rightarrow H$
Now we need to check $v$'s lesser-neighbors next turn.
Put $v \rightarrow q_1$

Set $q_0$ to $q_1$:

$q_0 \leftarrow q_1$

Essentially, I am collecting all possible nodes that can be used in the shortest-path, and placing them in $H$.
More on how this works:

Dijkstra's shortest-path algorithm works by first running a BFS, and marking all the nodes $v\in G$ with their-shortest paths from $s-v$. The next step is to go back from $t-s$, and follow the least-neighboring nodes back.
The thing is, here you can choose any of the least neighboring nodes. What I do here is collect all the least-neighboring nodes each step, which means I account for all the shortest-paths.
Now you quickly think, but hey, why is enumerating them exponential, but my way is not?
The answer is, because I use a set to avoid adding the same nodes twice, I avoid recalculating this for each possible path.

Now we have a DAG that we can traverse in any way from $t-s$, and obtain a shortest-reversed-path from $s-t$. The graph should have $t$ as the only source, and $s$ as the only sink.

If the above is correct, then I think we can take this a step further and solve the problem as follows.
Give each node in the DAG a node-weight; the node-weight will be the number of paths from from that node to $s$. Let us call this $w(v)$.
You can compute these quickly, see Algorithm that finds the number of simple paths from s to t in G.
Once we have the node-weight, we can uniformly pick a path by:

Layout the DAG as a level-structure (for visualization)
At each level, choose an arbitrary ordering between the nodes ie. a notion of "left to right".
Traversing down the DAG: at each step $i$, $i \in \left[1,\left|\mathbf p\right|\right]$ (where $|\cdot|$ means size-of, in this case, the length of the shortest-path):

Let $u_i$ be the current node (starting at $t$)
Add up all the weights of the children of $u_i$, and using an RNG, choose one child node, $v_i$, uniformly between the weighted children.
Set $u_{i+1} = v_i$, and go to the next step


Can this be done in polynomial time?

No, it cannot (unless P equals NP, of course).
Consider the case where all the $2n$ sets only contain elements that are colored (say) black. Finding a "white-black hitting set" with $n$ pairs is now exactly the same as finding a regular hitting set with n elements.
A reduction from Hitting Set

Find a set of at most $k$ elements that hits all sets in the collection $\mathcal{C}$, where $\mathcal{C} = r$

to your specific scenario

Find a set of $n$ pairs of white and black elements that hits all sets in the collection $\mathcal{C}$, where $|\mathcal{C}| = 2n$

follows easily. The only extra thing to take care of is if $2k < r$ (just add $r-2k$ black elements to $M$ and make each one a singleton set, now $n = r-k$), or if $2k > r$ (just take some arbitrary set $C\in \mathcal{C}$, add $2k-r$ extra elements to $M$ and, for each one make a set containing the union of it and $C$).


How to encode reachability in a graph with walls as a SAT problem

The point of my exercise is to encode the path existence in CNF

Well, a trivial way to do this is by reducing the problem to 2-SAT, following this set of rules:

Assing a literal to every edge of your graph, for example first element in first row become $a$, second element in first row become $b$ etc.
Put in OR relation the literal in the "start" position with each adjacent literal (
thus obtaining the clauses of your formula). If one or more adjacent literal has value 1, omit the clause in which it appears. Note that, when they are both 0, you dont need to repeat them:
if you have an adjacency between $a$ and $b$, you do not have to repeat the clause between $b$ and $a$.Furthermore you must not consider the diagonal adjacencies.
Perform the same procedure for all the literals adjacent to the starting one and for those in turn, until you reach the destination literal.
Connects all the obtained clauses  with an AND

To better adapt to your example, in which a 0 value means "you can pass" and a 1 value means "you cannot pass", you can negate all the literals in the formula.

So for the  matrix in the first above example  the corresponding path existence encoded into 2-SAT instance will be:

$(\not a \lor\not d) \land (\not d \lor\not e) \land (\not e \lor\not f) \land (\not f \lor\not c)$

By replacing the matrix values in the first example, the formula evaluates to 1, which means that this formula encodes a valid path.
However, for the secon matrix in the example, you never obtain a true formula in which the ending literal is present, so there is no valid path.


Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria

You could formulate this as an instance of integer linear programming.  You use zero-or-one variables $x_{ij}$, with the intended meaning that $x_{ij}=1$ if you assign recipe $i$ on day $j$.  Then your restrictions can be expressed as linear inequalities (e.g., $\sum_i x_{ij}=3$ means you eat 3 meals per day, $\sum_j x_{ij}=1$ means that you eat each recipe once).  You introduce a variable $y$ that expresses how far off from the goals you're allowed to be; then the restrictions on calories and macronutrients are also linear.  Finally, you feed this to an off-the-shelf ILP solver to minimize $y$.

Or, assuming you have three meals per day, you could generate all possible ways to pick a single day's menu that meets the calory requirement for that day, then exhaustively explore all possible ways to combine those daily menus into a week's worth of menus.


Complexity of a recursive bignum multiplication algorithm

The idea is to divide each $n$-bit integer into two halves of $n/2$ bits. For example, $10100010$ would be divided into $1010$ and $0010$. Naively, we would need to multiply four such halves, but in fact there is a way to do with only three. (This is similar to matrix multiplication algorithms such as Strassen's.) The algorithm described by the exercise is known as Karatsuba multiplication.

Regarding your other question, once you have reduced the computation of running time to a recurrence relation, you no longer need to understand anything more about the recursion in order to compute the running time - this is the main point of this abstraction.


Algorithm for finding all the combinations on a boolean array

The pattern you're trying to match is regular and can be matched by the regular expression 1(0?1)*.  A good strategy would be to convert the binary array to a string and do regular expression matches over substrings of it.

There aren't an exponential number of bit strings to check.  For a string of length $n$, you only have to check 1 string of that length.  You then check 2 strings of length $n - 1$, 3 strings of length $n - 2$ and so on.  In total there are $n(n+1)/2$ strings to check.


Precise relation between complexity classes(focus on P, NP and EXPTIME)

The Wikipedia page on EXPTIME summarizes all the known relationships:

$\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{EXPTIME}$.
$\mathsf{P} \subsetneq \mathsf{EXPTIME}$ due to the time hierarchy theorem.

You can find more information on the time hierarchy theorem in Wikipedia, in textbooks, and in online lecture notes. It is a very standard topic.

The P vs NP question is about the first two levels of the polynomial hierarchy. It is conjectured that all levels are distinct and different from $\mathsf{PSPACE}$, which is an upper bound on the hierarchy; and that $\mathsf{PSPACE}$ is distinct from $\mathsf{EXPTIME}$ (it is known that $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}$).

The proof of the time hierarchy theorem uses diagonalization in a straightforward manner (at least conceptually), and in this regard it is part of a line of results that includes Gödel's (first) incompleteness theorem and Turing's undecidability of the halting problem. In fact, it is a time-bounded version of the latter.

Finally, while some people have some ideas on how to prove $\mathsf{P} \neq \mathsf{NP}$, we mostly know a few general methods which cannot prove $\mathsf{P} = \mathsf{NP}$. These are known as barriers, and include diagonalization (used to prove the time hierarchy theorem), natural proofs (used to prove lower bounds in circuit complexity), and arithmetization (used to prove $\mathsf{IP}=\mathsf{PSPACE}$). The Wikipedia article about the P vs NP problem has a nice summary about these barriers.


In general, everything that you can describe in pseudocode, you can convert into a circuit. So if you can do modular arithmetic by hand, then a circuit can do it. More to the point, here are some concrete ideas for doing modular arithmetic, where the modulus is $m$:

Addition: You already know how to add two numbers. Assuming both numbers were in $\{0,\ldots,m-1\}$, the answer lies in $\{0,\ldots,2m-2\}$, so it is enough to check whether the results is at least $m$, and if so, subtract $m$.
Subtraction: This is similar to addition. The idea is that $-a = m-a$.
Multiplication: Here the basic idea is to compute the result $ab$, divide by $m$, and keep the remainder. You can (possibly) optimize this by doing modular reductions along the way.
Division: This is more complicated, and is probably better implemented in microcode or software. Suppose we want to compute $a/b$. If $m$ is prime then we can assume that $b \neq 0$. We compute the modular reciprocal $b^{-1}$ of $b$ using the extended Euclidean algorithm, and then multiply $a$ by $b^{-1}$. If $m$ is composite then the situation is slightly more complicated since $b$ doesn't always have an inverse. In that case we first compute the GCD $g = (a,b)$, and $a' = a/g$, $b' = b/g$. There is a quotient $a/b$ only if $(b',m) = 1$, in which case we can proceed as before.
Powering: This is again quite complicated, and better implemented in microcode or software. Here the idea is to use the repeated squaring algorithm, reducing modulo $m$ at every step.
Discrete logarithm: Given $g$ and $g^a$, find $a$. This is complicated enough that it probably isn't implemented in hardware.


As Yuval indicated, the most powerful and most popular proof technique is to use definitions.

The first principle of mathematical proof is by definitions. Always check the definitions. Whenever you are stuck in an unfamiliar area, look up the definitions first. We can not succeed in overemphasizing the importance of definitions. I can remember I had been chewing the definitions a dozen times in a row from time to time.

Here our task is to prove $A(B \cap C) \subseteq AB \cap AC$.

What is the definition of "$\subseteq$"?

  If $X$ and $Y$ are sets and every member of $X$ is also a member of $Y$, then $X$ is a subset of $Y$, denoted by $X\subseteq Y$.

So according to the definition, you are supposed to show

  if $w$ is a member of $A(B \cap C)$, then $w$ is also a member of $AB \cap AC$.

What does it mean by $w$ is a member of $A(B\cap C)$? It means $w=uv$, where $u\in A$, $v\in B$ and $v\in C$ as noted correctly in the question.

What are the members of $AB\cap AC$?

  The intersection of two sets $X$ and $Y$, denoted by $X \cap Y$, is the set of all elements that are members of both the sets $X$ and $Y$.

So you are supposed to show $w$ is a member of both $AB$ and $AC$. Since $w=uv$, where $u\in A$, $v\in B$, you know $w$ is a member of $AB$. Similarly, $w$ is a member of $AC$. Done.

  $AB \cap AC = \{ UV \mid U \in AB \text{ and } AC, V \in AB \text { and } AC \}$ for the right part.

Can you see where you made a mistake?


What is the difference between these two Edit Distance Algorithm

I'm going to assume by "doesn't work" you mean "gives the wrong answer".
In dynamic programming, every cell in the table is supposed to represent a solution to a subproblem. In the case of edit distance, the subproblem is

Let dp[i][j] be the distance between word1.substring(i) and word2.substring(j)

But in your code, the statement of the subproblem is ambiguous. The cell dp[i][j] contains something that depends on count, but which count? It might very well be that many different counts correspond to the same pair i,j, because you can get to it by different "routes". If that happens, your program will just use whatever count it encountered first, write the answer to the table and never revise it again. Therefore, if the first route you took is not the optimal one, then the result will be wrong.
Consider what happens when I give your program the words "WORD" and "SWORD". Which number will be in dp[3][4]? The correct program will write 0 into that cell, and eventually it will find a route that leads to the point 3,4 and has a cost of 1. Your program, on the other hand, will write the count of the first route it takes, which in this case will be  4. And even though it may later find a better route, it will still trust that 4, because that's what the table says.
In summary, you make a subproblem with the indices i,j depend on some other quantity, which violates the principles of dynamic programming. If your dp table had a third dimension, as in dp[i][j][count], then it might have worked, because then every subproblem would be fully specified.


Given a NP Algorithm for SAT, do we expect to have Correct and Incorrect Solutions?

Usually, when one develops an algorithm, there is a proof of correctness. From what I know, "nondeterministic" means the algorithm may or may not give you the correct answer, but it will definitely not give you an incorrect one.


finite automata that accepts integers divided by 3?

I believe you are misunderstanding the way finite automata work. A finite automaton accepts a language, i.e. a subset of the finite strings of a given finite alphabet. In your case, the accepted language is the set of strings made of $0$ and $1$ which encode a well-formed multiple of $3$.

Given a string, imagine placing a token on the initial state, then for each character of the string, left to right, move the token along the transition labelled $0$ or $1$, according to which character you read.

After having consumed each character of the string, the automaton accepts if and only if the token is on one of the accepting states.

Considering your automaton, intuitively, the top three states determine whether the string encodes a well-formed number (i.e. a string that starts with $1$ or is exactly $0$, for instance, $1000$ is valid, but $000$ isn't) while the bottom three determine whether or not it is divisible by $3$ using elementary number theory.


What determines the number of inputs and outputs when initialising weights in a convolutional neural network?

The question is about basic principles of Convolutional Neural Networks, specifically how the layers are organized (it's best explained here, in fact I highly recommend to complete the whole CS231n course, it's amazing!).

  What decides what values you input there? and what do they affect?

W_conv1 = weight_variable([5, 5, 1, 32])

The input channel of the first convolutional layer is the depth of MNIST images. Since they are grayscale, there's only one channel. If you had colorful CIFAR-10 images, you'd use 3 channels (R, G, B).

The 5x5 filters in this layer (32) would be the the output of this layer and input to the next layer. Indeed, as you can see the next layer defines

W_conv2 = weight_variable([5, 5, 32, 64])

  When I'm designing my own neural network, could I put any value I like
  for the last two, or if I were to change them in a neural network
  would it 'break' the entire network?

Yes, you have freedom here, you only need to make input-output channels consistent. If you decide to use 48 filters instead 32, you would write:

W_conv1 = weight_variable([5, 5, 1, 48])
b_conv1 = bias_variable([48])
...
W_conv2 = weight_variable([5, 5, 48, 64])
b_conv2 = bias_variable([64])

Like I said before, the first 1 is determined by your data. But you can change the filter size as well, from 5x5 to 3x3.

Note that if the number of channels doesn't match, the graph won't simply compile. You'll see an error even before the training starts, so don't be afraid to experiment.


Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?

In fact, something stronger is true: if you can approximate maximum clique within $n^{1-\epsilon}$ for some $\epsilon > 0$ then P=NP. This is because for every $\epsilon > 0$ there is a polytime reduction $f_\epsilon$ that takes an instance $\varphi$ of SAT and returns an instance $(G,cn)$ of maximum clique such that:

If $\varphi$ is satisfiable then $G$ has a $cn$-clique.
If $\varphi$ is not satisfiable then $G$ has no $cn^{1-\epsilon}$-clique.

If you could approximate maximum clique within $n^{1-\epsilon}$ you would be able to distinguish the two cases (exercise), and so to decide whether $\varphi$ is satisfiable or not.

The reduction uses the PCP theorem as a first ingredient. Given the PCP theorem it is not hard to give a similar reduction with a constant gap, and with some effort to give a reduction with a gap of $n^\epsilon$ for some $\epsilon > 0$. The reduction claimed above, which has a gap of $n^{1-\epsilon}$ for every $\epsilon>0$, is much harder. See lecture notes of Guruswami and O'Donnell for the constant gap, and lecture notes of Scheideler for the $n^\epsilon$ gap.


Bottom up chart parser adding active arc step

You have spotted a typo in that book.

The dot $\circ$ in step 3 of figure 3.11 should be after constituency C. To be explicit and precise, step 3 should be stated as the following.

  For each rule in the grammar of form X $\to$ C X$_1$ ... X$_n$, add an active arc of form X $\to$ C $\circ$ X $_1$ ... X$_n$ from position P$_1$ to P$_2$.

As you have observed, all examples following figure 3.11 show clearly that the dot $\circ$ are placed after constituency C.

This can also be verified by the statement a few lines below.

  Notice that active arcs are never removed from the chart.

We can check that we cannot, indeed, find any instance of an active arc in all of section 3, chapter 3 of the book that starts with a $\circ$.

There is also a rule that for each active arc from position $a$ to $b$, the symbols before the $\circ$ should correspond to the terminals between those positions inclusively. That rule also implies that a dot $\circ$ cannot be at the very front of an active arc.

By the way, that books is written so clearly that I have to say that glaring typo is an almost reverse testimonial.


I am afraid that you cannot construct a DFA for $L$ since it is not regular.

Intuitively, a finite automaton cannot even make sure the number of $a$'s and the number of $b$'s are the same since its finite memory cannot keep track of the number of the $a$'s in the initial part of $a^nb^n$ when $n$ become sufficient large.

How to prove that  language is not regular?

Use the pumping lemma. For example, what about a word that barely satisfies the condition such as $a^pb^{p+10}$?

Use Myhill–Nerode theorem. How about elements $a^n$ for all $n$? Does any of two of them belong to the same Myhill–Nerode class?

Exercise 1. Let $\lfloor x\rfloor_a$ be the minimum number of consecutive $a$'s in $x$ and $\lceil x\rceil_a$ be the maximum number of consecutive $a$'s in $x$, where $x\in\{a,b\}^*$ contains $a$. $\lfloor x\rfloor_a=\lceil x\rceil_a=0$ if $x$ does not contain $a$. Is the following language regular?
$$L = \{x \in \{a, b\}^*  \mid  \lceil x\rceil_a - \lfloor x\rfloor_a \le 10 \}$$

Exercise 2. Is the following language regular?
$$L = \{xy \mid x,y\in \{a,b\}^*  \wedge ||x|_a - |y|_a| \leq 10 \}$$


Can computation models be categorized in terms of efficiency?

If your model contains a notion of "step" (which is reasonable), and consequently defines the running time as the number of computational steps, then you can define the class $P$ for your model. If you think about polynomial time as efficient (which is what we normally do, see for example the question here), then you have a definition for what is efficiently solvable in your new model. You can now ask about the differences between the classes $P_M$ (set of languages decidable in polynomial time in the new model $M$), and the regular $P$ (which relates to Turing - machines).

Now, a reasonable definition for "the model $M$ is more efficient than $M'$" would be $P_{M'}\subsetneq P_M$.

Although $P$ has the advantage that it can be defined relative to any reasonable computational model, sometimes our notion of efficiency changes depending on the context.

For example, in quantum computation (for a formal definition of the model you can look up quantum circuits or quantum Turing machines) our notion of efficiency is captured by the class $BQP$ (since we involve error probabilities, it makes sense to allow our polynomial algorithm to be wrong with small probability). Same goes for the probabilistic Turing machine (Turing machines with the additional ability to toss coins). Our notion of "efficiently computable" with respect to probabilistic Turing machines is captured by the class $BPP$.

The question whether these models are "more efficient" than the classical Turing machine, translates to whether $P\subsetneq BQP$, and whether $P\subsetneq BPP$.

Since we know factoring integers is in $BQP$ (Shor's algorithm), and we suspect that it is not in $P$, we suspect that indeed $P\subsetneq BQP$, meaning that quantum computers can decide more problems efficiently (although it has the same computational power as the classical Turing-machine).


Returning sorted lowest k elements in a binary heap

Construct a new min-heap $H$ using the root of the original heap $O$ as its only element. Then $k$ times you want to pop the smallest value from $H$, append it to our output array and add the children that node has in $O$ to $H$.

The maximum size $H$ gets here is $k + 1$, so all the above has a complexity of $O(k \log k)$.

If you meant to keep the original heap intact, you are now done. If you also want to remove these $k$ elements from $O$, then all you need to do is use $H$ as your new heap, making any leaf of $H$ use the child pointers that respective node had in $O$.

All of the above is assuming you have a pointer-based tree structure. If you use an array as your heap data structure using indices as implicit children, I doubt it's possible at all.

On top of that, this optimization is likely not worth it unless $n$ is very large and $k$ is very small.


Let $A_n\subseteq \{0,1\}^{\log n}$ denote the set of binary strings of length $\log n$ with at least $c\log n$ trailing zeros on the right (here I assume that $\log n$ in an integer and $0\le c\le 1$). Note that $|A_n|=2^{\log n -\lceil c\log n\rceil}\le 2^{(1-c)\log n}$. Since $H:\{0,1\}^{\log n}\rightarrow \{0,1\}^{\log n}$ is a one to one function, $\Pr_{x\sim U_{\log n}}\left[H(x)\in A_n\right]=\frac{|A_n|}{2^{\log n}}\le\frac{1}{n^c}$, where $U_k$ is the uniform distribution over $\{0,1\}^k$.


Register Machine code for Fibonacci Numbers

Here is some code in C, which you can "compile" into your assembly language:

int x = 0, y = 1, z;
while (n--) {
  z = x;
  x = y;
  y += z;
}
return x;

After $n$ iterations of the loop, $x = F_n$ and $y = F_{n+1}$.


If possible, use binary search to find an element in sorted array

No. Let's define an array $B$ as $B[i] = i^2 - 1$. Clearly it has  no solution, but it is sorted.
Now I define $A$ to be a copy of $B$, with exactly one element, $A[k]$ incremented by one. This array is still easily seen to be sorted, but there's no way to find out which $k$ I used to increment a single element other than scanning the complete array. After all, if you inspect $n - 1$ indices of this array, I could've chosen $k$ as the single index you didn't look at.


Is there a usable implementation of PBFT?

Not necessarily NFS, but Hyperledger used PBFT for their blockchain platform.

This is a Go implementation: https://github.com/hyperledger-archives/fabric/tree/master/consensus/pbft

That is an old repo, they seem to be currently using a new repo with implementations in other languages as well, however I haven't gone through it in detail:
https://gerrit.hyperledger.org/r/#/admin/projects/

There are more related details in this question: https://stackoverflow.com/questions/41710738/pbft-algorithm-in-hyperledger

Good luck


How to determine if a language is deterministic context-free language?

Here $L$ is DCFL.

  (a) $f_1(L) = \{u\in\Sigma^*: ua\in L\text{ for some }a\in\Sigma\}$ (that is, $f_1(L)$ is the set of strings obtained by dropping the last symbol of strings in $L$.)

Let's define homomorphism $h$ as follow:

$h(a) = a, \space a\in\Sigma$

$h(\epsilon)= c$

$L' = h^{-1}(L) \cap (\Sigma^*c\Sigma), c\notin\Sigma$. (note that $L'$ is DCFL.)

Now start with DPDA of $L'$ and whenever you find $c$ in input make transition to final state.

  (b) $f_2(L) = \{v\in\Sigma^*: av\in L\text{ for some }a\in\Sigma\}$ (that is, $f_2(L)$ is the set of strings obtained by dropping the first symbol of strings in $L$.)

Consider $L=\{a^nb^{2n}\} \cup \{ca^nb^n\}$ Now $f_2(L) = \{a^{n-1}b^{2n}\} \cup \{a^nb^n\}$ Which is not DCFL.


Using master theorem to solve recurrence with log

Clearly $c := \log_3 4 > 1$. Choose $1 < d < c$ arbitrarily, say $d = \frac{1+c}{2}$. Then $O(n\log n) = O(n^d)$ and $d < \log_3 4$, and so we can apply the first case of the master theorem.


Solving inhomogeneous recursion using quadratic particular solution

Given:

$a(n) = a(n-1) + 5n^2 + 2n + 4$

We hypothesise that because the difference is quadratic, $a(n)$ is cubic. In particular:

$a(n) = a_3 n^3 + a_2 n^2 + a_1 n + a_0$

So:

$a_3 n^3 + a_2 n^2 + a_1 n + a_0 = a_3 (n-1)^3 + a_2 (n-1)^2 + a_1 (n-1) + a_0 + 5n^2 + 2n + 4$

$\Rightarrow 3 a_3 n^2 + (-3 a_3 + 2 a_2) n + (a_3 - a_2 + a_1) = 5n^2 + 2n + 4$

This must be true for all $n$. Therefore:

$3 a_3 = 5$

$-3 a_3 + 2 a_2 = 2$

$a_3 - a_2 + a_1 = 4$

Note that $a_0$ doesn't appear in these equations, so this is effectively a linear system, three equations in three unknowns. The unique solution is:

$a_3 = \frac{5}{3}$

$a_2 = \frac{7}{2}$

$a_1 = \frac{35}{6}$

And so:

$a(n) = \frac{5}{3} n^3 + \frac{7}{2} n^2 + \frac{35}{6} n + a_0$

is a solution to the recurrence equation for any $a_0$.


Is this correct : whether or not a type 3 grammar generates $\Sigma^*$ is not c.e

To see if a type 3 grammar (regular) generates $\Sigma^*$ just build the minimal DFA accepting the language, and check if it is just initial = final state, with loop on all symbols. All constructions involved are effective.


Proving that a (tree) language is not Buchi recognizable

The idea is to play with the $m_i$'s, as follows.

Consider a tree $t_1$, which has $a$ in $\epsilon$, and nowhere else. Look at the path $1^\omega$ — an accepting run on it has infinitely many accepting states. Wait until such an accepting state was reached, and only then put $a$ at $1^{m_1}0$, where $m_1$ is large enough.

Now look at the path $1^{m_1}01^\omega$, again, it has an accepting state eventually, denote the length up to it by $m_2$, put an $a$ at $1^{m_1}01^{m_2}0$ and look at $1^{m_1}01^{m_2}01^\omega$. By now you have almost what you wanted - two accepting states with an $a$ between them (informally speaking). But you are not yet guaranteed that both accepting states are equal. To enforce the latter, we repeat the process for $n$ times, thus exhausting the number of accepting states, and by the pigeonhole principle, two accepting states must be equal.


Regular Expression as basis for creating this grammar

$A \rightarrow ba \mid A \mid B \mid cA$

under this $bababaccc$ is also legal

You could try something like this...

$S \rightarrow cS|cA$

$A \rightarrow baA|B$

$B \rightarrow bb$


Upper bound for runtime complexity of LOOP programs

Take Ack(n-1). Grows much slower than Ack(n).


Meaning of "positive position" and "negative position" in type theory?

Unfortunately "polarity" is a somewhat overloaded concept in type theory. "Positive position" and "negative position" refer to a different notion of polarity than what Bob's talking about with focusing/polarization.

Your Meaning

When you're defining an inductive type you give a series of rules which correspond to operations for the type you're defining. For example you might say a Nat is something with

a value zero : Nat
a function suc : Nat -> Nat

And then expect that Nat contains all the values that can be generated from repeatedly applying suc to other Nats and includes zero. In line with this inductive construction we get an recursion principle across Nats which works based on the fact that any Nat is generated by those constructors.

rec : A -> (A -> A) -> Nat -> A

so that

rec Z S zero = zero
rec Z S (suc n) = S (rec Z S n)

However, there are some restrictions on what we can write as rules. Otherwise, we can write down a series of rules for which the recursion principle cannot be justified. Consider the "inductive type" D with one constructor

d : (D -> D) -> D

Here there isn't a sane recursion principle here. and for good reason! If we had some recursion principle, we could use it to encode a version of self application and with it, nontermination. This means D can't be called "inductive" because inductive types are finite constructions generated from repeatedly applying constructors!

In order to deal with this we restrict how inductive types can be recursive in type theory. Specifically, we stop them from appearing in "negative places". This is that notion of polarity you were talking about. The polarity of a position is determined thusly,

The argument starts in a positive position
Everytime we go to the left an arrow, the polarity flips

So X is positive in the first two and negative in the second two

X
Int -> X
X -> Int
(Unit -> X) -> Int

This idea is justified with a recourse to category theory where an inductive type with whose only recurrences are positive gives rise to a covariant functor. The details of how this works and why its interesting a a bit long.

Bob Harper's Meaning

In his blogpost Harper was talking about a different meaning of polarity. This polarity is reference to how various connectives in logic are given meaning. In particular, we can classify connectives in two ways

Positive connectives can be defined by defining how to introduce them (their introduction rules)
Negative connectives can be defined by defining how to use them (their elimination rules)

In programming language terms, this nicely captures the distinction between lazy and strict types. A strict type is defined by its values. A lazy one is defined by how can pattern match on them. In order to handle this properly, we define a language with 2 main constructs, ways to build up positive types and "spines" to decompose negative types. We can use this to incorporate both strict and lazy computation into one language.

In order to understand this better, I refer you to chapter 38 of Bob Harper's book.


How to perform local search on simple paths?

I can't comment yet, so I'll post this as an answer:

Assuming you can find the S-T path with a pathfinding algorithm, why not use the same algorithm with an "antiheuristic" topology?

As you increase the "heat," the further away your found paths will be from your initial solution.

Additionally, you could add some grainy noise wavelets, or random hills and valleys, into the landscape to toss things up a little.

But still:

  The evaluation function is complex and can't be evaluated until all the edges in the path are known

This is always the case. It is usually better to try and find a proper heuristic/path abstraction than monte-carloing it. I recommend you post more info about your problem.


How to remove objects from an array most efficiently?

You can maintain a pointer that, in the $i$th iteration, points to the $i$th element that is not 2, i.e., the $i$th element in the final array. In each iteration, we only move the element to which the pointer points to the $i$th position.

int size = 7;
int array[7] = {1,2,2,3,4,5,7};
int i = -1;
int p = -1;
while (1)
{
    ++i;
    do ++p; while (p < size && array[p] == 2);
    if (p >= size) break;
    array[i] = array[p];
}
size = i;

In your example, it works as follows.

Initial: 1 2 2 3 4 5 7
After the 1st iteration: 1 2 2 3 4 5 7
                         i
                         p

After the 2nd iteration: 1 3 2 3 4 5 7
                           i   p

After the 3rd iteration: 1 3 4 3 4 5 7
                             i   p

After the 4th iteration: 1 3 4 5 4 5 7
                               i   p

After the 5th iteration: 1 3 4 5 7 5 7
                                 i   p

After the 6th iteration: 1 3 4 5 7 5 7
                                   i   p


Take any policy that you like. It will consist in a number of calls to $C$ during which you will reduce the size of the incertainty of the location of $x$.

Whatever rule you use, you can't beat dichotomy, because if you split in unequal subintervals, you can always end-up in the longest, which is longer than the half.

This also holds in the average sense. Assume a split in relative sizes $\alpha$ and $1-\alpha$, which will be performed with these probabilities. The expectation of the relative length after a division is $\alpha^2+(1-\alpha)^2\ge1/2$. The minimum is reached for $\alpha=1/2$.

You might only improve on this result when $x$ is not uniformly distributed and you have some information about this distribution, such as the histogram of frequencies. (In such a case, the optimal rule is probably to split in equiprobable subintervals.)


Converting along regular expression to NFA

What you need is the Berry-Sethi algorithm, constructing the Glushkov's automaton.
However, for your problem, I'd consider constructing directly a DFA with $10 = \begin{pmatrix}5\\2\end{pmatrix}$ states corresponding to words of size 5 containing exactly two zeros, and a sink state (and maybe some other states for the begining of the reading).
The Glushkov's automaton on your regular expression will be very big.


What is an estimation of the Kolmogorov Complexity for the first N integers?

No, there is no general algorithm to compute a close approximation to the Kolmogorov complexity of the sequence $1,2,\dots,n$.  Any candidate algorithm you come up with will have some inputs where it gives a bad answer (a poor approximation to the correct answer).

Denote by $[n]$ the binary encoding of the natural number $n$, and let $[[n]] = [1],[2],\ldots,[n]$ denote a comma-separated encoding of the sequence $1,\ldots,n$. It is not hard to check that $|K([n]) - K([[n]])| = O(1)$.  Since computing $K([n])$ is undecidable, it follows that computing a good approximation to $K([[n]])$ is also undecidable.

Furthermore, it is known that for "most" integers $n$, $K([n]) = \Theta(\log n)$. So for "most" integers $n$, $K([[n]]) = \Theta(\log n)$.


The thing you're missing is that you aren't search for $|3\rangle$, you're searching for "the input that makes $f$ return true" where $f$ is some function.

For example, maybe $f$ is a discrete logarithm checker like $x \rightarrow 2^x \equiv^? 432821 \pmod{7438927891}$. Or $f$ could interpret its input as a claimed proof of the Riemann hypothesis, and check if that proof is correct. Anything you can imagine checking, $f$ could be that.

So Grover's algorithm is very very widely applicable. But unfortunately it also only gives a quadratic advantage, so "applicable" often doesn't translate into "useful". For example, the space of (reasonably sized) possible Riemann-hypothesis proofs is so huge that it laughs at square roots.


Solving a recurrence relation using Divide and Conquer Master Theorem

Yes. Recall that the Master Theorem deals with recurrences of the form
$$
T(n) = a\cdot T\left(\frac{n}{b}\right)+f(n)
$$
In your particular case you have $a = 16$, $b=4$ and $f(n) = n!$.

Then we decide the complexity by comparing $f(n)$ to three functions of $n$, $a$ and $b$ (really we compare it basically the same function, with a $\log$ wiggle room, but in different ways).

In particular the third case holds where $f(n) \in \Omega(n^{c})$ where $c > \log_{b}a$. You have that $\log_{b}a = \log_{4}16 = 2$, so you have to prove (or at least convince yourself, depending on how rigorous you're being) that $n! \in \Omega(n^{c})$ for some $c > 2$.

It should be reasonably clear that you can pick any constant $c$ in this instance, and that this case holds. As it does, we get immediately (which is of course the point of the Master Theorem) that $T(n) \in \Theta(f(n))$, which in this case gives $T(n) \in \Theta(n!)$.


A simple Query regarding Modulus Notation?

Note that the definition of this problem considers positive integers without $0$, which is instead denoted by $B \bmod B$.


If a connected graph has a bridge then it has a cut vertex

An edge $e=uv$ is a bridge in $G$ if there is no path between $u$ and $v$ in $G-e$.

In general, $u$ and $v$ are cut vertices, but there are some special cases you must treat with care.

(1) If $G \simeq K_2$, then depending on the definition of connectivity, the $G-u \simeq K_1$ might and might not be considered connected*.

(2) There is another case in which you would not consider $u$ to be a cut vertex; An edge  $uv$ is called a pendant edge if $\deg(u) = 1$.  In this case, if $uv$ is a pendant edge and $\deg(v)>1$, you would not typically call $u$ a cut vertex.

Postlude

All that being said, definitions in graphs are hard (case in point: Diestel).  When we try to make definitions very general, special cases sometimes become absurd.

Note

1

* To address David Richerby's objection, $K_1$ is considered disconnected when deriving connectivity from k-connectivity, in which you require the graph to have more than $k$ vertices. By that definition ("a 1-connected graph is called connected"), $K_1$ is disconnected by having too few vertices.

2

To answer Thinker's follow-up question; since you wanted to know what to answer to a hypothetical exam question, I would do it this way:

Let $e = uv$ be a bridge.  We have three cases:

$\deg(u), \deg(v) > 1$.  The statement is true.
$\deg(u) = 1, \deg(v) > 1$.  The statement is true, $e$ is a pendant.
$\deg(u) = \deg(v) = 1$.  The statement is true if and only if $K_1$ is considered connected.


Bucket computation, cutting array with lines

For the considered line you know the start position (xs, ys) and the end (xe, ye). For instance on the N=7 visual you provide, let's take the first upper left line:

xs = 0
ys = 4.5
xe = 7
ye = 2.5
(I use coordinates right, down starting from upper left corner).

Let's take a parameter t of the linear position on the line with t=0 on start and t=1 on end. You know how many verticals or horizontals your line crosses and at which t value. In our exemple:

6 verticals crossed at t = v/7 with v=1 to 6 (not counting outlines).
2 horizontal crossed at t = 0.25 and t = 0.75.

Now just sort t increasing all these crossings:

(1/7, V), (0.25, H) (2/7, V), (3/7, V), (4/7, V), (5/7, V), (0.75, H), (6/7, V).

They correspond to cell change starting in cell (1, 5) to cell (7, 3). So you can compute the relative length of the line in each cell. For instance:

cell (1, 5) L = 1/7-0 = 1/7
cell (2, 5) L = 0.25-1/7
...

And you know how to select the X pixels now.


Linear Regression using a Neural Network

No.  This is not the correct way to train such a network.  To update the network, we want to update the weights of the network.  Thus instead of using $\frac{d\mathcal L}{dA}$ to update the weights, you should be using $\frac{d\mathcal L}{dW}$, where $W$ are the weights.  This could be computed as

$$\frac{d\mathcal L}{dW} = \frac{d\mathcal L}{dA} \times \frac{d\mathcal A}{dW},$$

where $\frac{d\mathcal L}{dA}$ is computed using the formula you obtained ($\frac{d\mathcal L}{dA} = A-Y$ is correct), and where $\frac{d\mathcal A}{dW}$ is computed using backpropagation through the network.

Or, better yet, use an existing framework that performs automatic differentiation for you (e.g., Keiras, Tensorflow), and save yourself a lot of effort.


What precisely differentiates Computer Science from Mathematics in theoretical context?

Theoretical computer science is what theoretical computer scientists do; and mathematics is what mathematicians do. Other than that, there is no accepted definition of either. One might argue that theoretical computer science is a particular branch (or branches) of mathematics, influenced (at least originally) by the problem of efficient computation.

Many areas of mathematics are clearly not theoretical computer science, say functional analysis, category theory, algebraic geometry, algebraic number theory, and many others. However, sometimes these areas are applied to theoretical computer science. Parts of them might then form part of theoretical computer science, if there is a community of theoretical computer scientists who decided to work on them.

On the other hand, computability theory is not necessarily part of theoretical computer science, depending on which community of theoretical computer science one takes as reference. Theoretical computer science (or at least its part known as "Theory A") is traditionally about what can be efficiently computed rather than about what can be computed at all.

Many mathematical theorems have no computational content, and in some cases this can be made precise. One example is Kawamura's result that ODEs are hard to solve in general. It is not true that every mathematical proof has constructive content – indeed there are mathematical techniques which are inherently non-constructive, for example the use of compactness or the axiom of choice in any of its other guises.

If you are interested in the computational content of mathematical statements and proofs, you might want to look into reverse mathematics and bounded arithmetic (sometimes known as feasible mathematics or feasible arithmetic).


A* algorithm how to choose $h(n)$, a heuristic estimation of the cost of node n

Let's try to walk together through the $f$ function!

The intuition here is that we want to choose nodes in our exploration frontier which are:

Close to the start state
Close to a goal state

The shortest distance to the start state can be calculated recursively for every node in the search space pretty much as we do in uniform cost search.

However, the distance of a node to a goal state cannot be precisely calculated (for that we would need to know the shortest path to a goal, which would mean we have already solved the problem).

Thus the best we can do is try estimating it, using a heuristic function $h$. Obviously, we want this estimation to be as precise as possible, but we also want some other properties to hold:

(admissibility) we want $h$ to never overestimate the cost to the goal from any given node.
(consistency) we want $h(n)$ to not be greater than $h(n')+c(n,n')$ for any successor $n'$ of $n$, where $c(n,n')$ is the cost of the path that joins both states. In other words, the true cost of going from any given node to another must be less than the difference between the heuristic value of both nodes.

If we impose the restriction that $h(n)=0$ if $n$ is a goal state, then it is easy to see that consistency implies admissibility.

These properties guarantee that the algorithm is sound, complete and optimal for tree-search (admissibility) and graph-search (consistency).

Now, there are many heuristics out there for each problem.

One example is the trivial heuristic which assigns $h(n)=0$ for every $n$. This heuristic is indeed consistent. In this case, $A^*$ behaves as uniform cost search.

We can find heuristics better suited to solve a problem. One way to do so is by relaxing the conditions to solve the problem, and calculating the exact solution of the relaxed problem from the state we are in.

For example, we can take the $n$-queens problem, where each step consists in moving one queen, and take as a heuristic the number of queens under attack minus one (or zero if no queen is under attack).


Is finding the smallest collection of subsets so that the number of elements among the subsets is <= the number of subsets NP-hard?

This is too long for a comment but is not really a full answer.

Let's re-formulate the problem setting slightly as a bipartite graph $G$, with $\{1,2,\ldots,N\} = X$ as one set of vertices and the collection of subsets (say, $Y$) as the other set of vertices, with an edge between $i \in X$ and $J \in Y$ iff $i \in J$. For any set of vertices $W$ in $Y$, define $N(W)$ to be the neighborhood of $W$ in $G$ -- namely, the set of all vertices in $X$ that are adjacent to at least one vertex in $W$.

Then, the problem asks to find a minimal subset $W \subseteq Y$ such that $|N(W)| \leq |W|$. However, if we change the criterion slightly to $|N(W)| \lt |W|$, we find that such a subset exists if and only if there does not exist a matching between $X$ and $Y$ that covers $Y$, for it is exactly equivalent to Hall's Marriage Theorem.

Since such matchings are findable in polynomial time (e.g.: via Hopcroft-Karp), I think this version of the problem should probably be relatively easy but I'd have to do some more work to figure out if and how the standard algorithms for bipartite matching expose these deficient sets and whether or not minimal deficient sets can also be obtained easily. Furthermore, I can't tell right away how much harder the original version of the problem (which allows $|N(W)| = |W|$) is than this modified version.


When represented as a function, why is the input of a decision problem a natural number?

It's probably easier to understand if you think of a program as a bit-string, i.e., an element of $\{0,1\}^*$; and think of a decision problem as a function that maps a bit-string to either 0 or 1, i.e., a function $\{0,1\}^* \to \{0,1\}$.  The input to the decision problem is a bit-string.

Why is this reasonable?  Any program can be expressed as a sequence of bits (e.g., convert each character to bits, and concatenate them).  The input to the program can be expressed as a sequence of bits.  So everything is bits.

Hopefully that approach makes sense.

Now, why does your professor/textbook talk about natural numbers instead of bit-strings?  That's just a convention.  It turns out that every bit-string can be encoded as a natural number, and vice versa.  Given a bit-string, you can think of it as the binary representation of a number; and given a number, you can turn it into a bit-string by expressing it in binary.  So bit-strings and natural numbers are in some sense interchangeable or equivalent.


When we say that a problem $B$ is a special case of a problem $A$, we mean that $B$ is the same problem as $A$, with the exception that not all problem instances of $A$ are problem instances for $B$. If $B$ is a special case of $A$, we say that $A$ is a generalization of $B$.

Two examples: the addition of positive whole numbers (say $5 + 3$) is a special case of addition of whole numbers (say $5 + (-3)$), and sorting of integers in the range $\{ 1, 2, \dots, k \}$ for fixed $k$ is a special case of sorting of arbitrary integers.

Any solution to $A$ is also a solution to $B$, and any hardness results for $B$ (for example, it is $NP$-hard or needs $\Omega(n^2)$ time to be solved) immediately transfer to $A$. However, we usually consider special cases because we can sometimes find better algorithms for them compared to the general case.

Examples: the $\Theta(n \log n)$ sorting algorithm works just as well on integers in the range $\{ 1, 2, \dots, k \}$, but CountingSort works on the special case (not on the general) in $O(n + k)$, which is usually faster if $k$ is small. $SAT$ is $NP$-hard, $3SAT$ is a special case of $SAT$ that is still $NP$-hard (which therefore implies that $SAT$ is $NP$-hard), but $2SAT$ is in $P$.

Note that the above definition is sometimes stretched (abused) to say that you can encode any instance of $B$ as an instance of $A$, and that this encoding is extremely simple. In that case, the above usually still holds, but is less rigorous.


exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow

Since you just have to satisfy the conservation of flow property and capacity property. You can consider the following example:
$V = \{s,t,u,v\}$ and $E = \{(s,t), (u,s), (u,v), (v,u)\}$ with each edge of capacity 1.
You can send a flow of 1 via $(u,v)$, $(v,u)$, and $(s,t)$. It follows all properties of a valid flow. It does not have a path from $s$ to $u$. Also, the flow via $(u,v)$ is at its full capacity.


Production for $\{b^jc^k\; |\; j\neq 2k \}$ can be written as

$B\rightarrow bBcc\;|\;bB_1\;|\;cB_2$

$B_1\rightarrow bB_1\;|\;b\;|\;c\;|\;\epsilon$

$B_2\rightarrow cB_2\;|\;c\;|\;\epsilon$

You can see that it can't accept $bbcccc$. We can use $B\rightarrow bBcc$ twice but the final $B$ would have to be substituted with either b or c.

It accepts $bbccc$ as $B\rightarrow (bBcc) \rightarrow b(bB_1)cc \rightarrow bb(c)cc$

For even number of cs $B\rightarrow bBcc$ can be used. For odd number of cs, an extra $B_1\rightarrow c$ can be used.

So $\{a^ib^jc^k\; |\; j\neq 2k \}$ has the following grammar

$S\rightarrow AB$

$A\rightarrow aA \;|\; \epsilon$

$B\rightarrow bBcc\;|\;bB_1\;|\;cB_2$

$B_1\rightarrow bB_1\;|\;b\;|\;c\;|\;\epsilon$

$B_2\rightarrow cB_2\;|\;c\;|\;\epsilon$

Note: i can be 0 but j and k can not be 0 simultaneously.


Show that language generated by grammar is regular

Prove by backwards complete induction that each $X_i$ generates a regular language (backwards induction means that you first prove it for $X_n$, then for $X_{n-1}$, and so on, until you reach $X_1$; complete induction means that when proving this for $X_i$, you can use the induction hypothesis for all of $X_{i+1},\ldots,X_n$).

Perhaps the easiest way to carry out the inductive proof is to give a regular expression for the language generated by each $X_i$.

The only non-trivial part is handling productions of the form $X \to XY$. Here you need to use Arden's rule, which states that if the only productions having $X$ at the left-hand side are $X \to XY \mid Z$ then
$$ L(X) = L(Z)L(Y)^*, $$
where $L(X)$ is the language generated by $X$.


How hard is it to factorize sum of two numbers

There is currently no known (asymptotical) more intelligent algorithm (and it is also not expected that there should be one) than if factorizations of $m$ and $n$ were not known (assuming $m$ and $n$ to be coprime). Even the case where $2$ is a prime factor doesn't count, because checking some of the smallest prime numbers can be done without much effort anyway.


Standard Parameters for Genetic Algorithms

As you say, there are no universal parameter settings, which means that you won't find a source that cites any such settings. Instead, you find some papers who tune the parameters to their particular problem, and you find many, many others that simply take a "standard" set of parameter settings without much attempt to justify them. In that case, it's not like there's a single authoritative source you can cite -- it's more like bunches of people sort of converge on parameters that seem common to everyone. The best you can really do is to say something like "the parameter values were chosen as being commonly observed in the literature."

Also, it depends not just on the problem, but on the particular structure of your GA. CHC (Eshelman, 1991), for example, is usually used with a population size of 50 (very small by typical standards) and has no conventional mutation operator, but it adds other pieces that make up for it. Genetic programming practitioners often use population sizes in the thousands and use very high mutation rates.

For a "standard GA", if you were to use a population size of 100-200, a mutation rate of 1/L (with L=the length of your encoding, assuming it's discrete), and "enough" generations (more on that in a second), no one would question things too much. However, aside from just citing a random selection of papers, there's not a lot you can point to as justification. Also, some light parameter tuning is almost certainly a better idea if you can afford it at all.

For generation count, the basic rule is to go until you either exhaust the amount of time you have to allot to it or until the algorithm converges, whichever comes first. Of course, these are interdependent. Raising the population size and/or raising the mutation rate will slow convergence, so you still need to tune parameters for the best results.

If you're doing this for research purposes at least, you should also measure the runtime in fitness function evaluations rather than generations. The reason is that if my algorithm finds a solution in N generations, you can almost certainly find a better solution in N generations if you just multiply the population size by 100 or so. You'll get to do about two orders of magnitude more searching than I could do, so the comparison is unfair. Reporting generations used is an automatic red flag in a paper unless the other GA parameters are controlled to a degree that we can be sure that the comparison is apples to apples. Measuring evaluations is much more tightly correlated to wall-clock time than measuring generations, and should essentially always be preferred.


You're almost there, but when you find a back edge you already have all the information you need to describe the cycle it forms. Also, there's a bit of a complication where you might find duplicate cycles. Or you might not. Do you consider {A, B, C} to be the same cycle as {C, B, A}? What about {B, C, A}? Depends on what you're doing, but let's assume they're equivalent.

So you've got a graph you're DFSing.
illustration http://imageshack.us/a/img687/1598/tjd.gif.

And you go down one branch and detect a few cycles. Cool.
illustration http://imageshack.us/a/img14/9295/4bo.gif

But you haven't explored all possibilities, so you unwind the stack and take the next branch. You find some more cycles. Groovy.
illustration http://imageshack.us/a/img818/3851/t69.gif

The adventure continues. You go down another path and find another cycle. Good.
illustration http://imageshack.us/a/img543/48/c5mb.gif

No, wait. BAD. You've got two equivalent cycles. And when you unwind to having only explored A-B, and take A-B-E this time, that's going to reveal more duplicates. You'd need a way to get rid of those, if they are a problem in your application.


Dynamic Programming formulation for hotel problem

Start with yinnosanders algorithm, then try to get faster than $O (n^3)$ in typical cases:

With your cost model, travelling a total distance of x miles in d days costs at least $x^2 / d$. If you could stop anywhere you like, you would travel $a_n / d$ miles every day.

First find a reasonably good set of stops: On each day, when there are d' days left, you pick the hotel whose distance is closest to the remaining distance, divided by d'. This gives you an upper limit L for the cost of the optimal journey.

Now jinnosanders suggests that you calculate dp(i,j). But first we calculate a lower limit for the cost of any journey that involves stopping at hotel i on day j: The cost would be lowest if you drove the same distance on each of the first j days, and the same distance on the remaining last days. The cost is at least $a_i^2 \space/\space j\space+\space(a_n - a_i)^2/(d-j)$. If this cost is higher than the upper limit L for the best solution that we found earlier, then there is no need to calculate dp (i, j) and we set dp (i, j) = infinity instead.

We will have dp (j-1, j-1) ≥ dp (j, j-1) ≥ dp (j+1, j-1) ... so when we calculate dp (i, j), we stop when dp (i-n, j-1) = infinity. This should work considerably faster than O (n^3) in typical cases if the hotels are reasonably close to equidistant.


I quite disagree with your textbook.

First, Interrupts can be very different between architectures. Most does not support nesting interrupts, while others allow some forms of it (fast interrupts for time critical operations in embedded...)

One can imagine a CPU having 3 modes :

User
Supervisor
Interrupt

When the interrupt request signal[s] is active, the CPU automatically saves a few registers, sets the supervisor flag and branches into the interrupt vector. If several interrupts occurs simultaneously, the highest priority interrupt is taken. If one or several interrupts becomes active while the CPU is already in interrupt processing mode, it will wait until the end of the current interrupt service routine to eventually process the next highest level interrupt. This is similar when interrupts are temporarly masked by the OS when it is updating some structures...

Which registers are saved depends a lot of the type of CPU. The minimum is just being able to resume execution later : PC, flags, one register. You can also have a full set of shadow registers reserved for interrupts and which don't need to be saved.

OS tasks are not interrupts. There is usually a timer that regularly tiggers an interrupt which, in turn, wakes the scheduler for switching tasks. It is also done by I/O related interrupts : A network packet is received, an interrupt is triggered, the Ethernet NIC interrupt routine tells the OS to wake the network daemon...

No task has higher priority than interrupts.

Because while being in "interrupt" mode, the CPU cannot be interrupted and cannot process higher priority stuff, OSes try to spend as little time as possible in that state, they instead schedule tasks to asynchronously process events, for one or several symmetric CPUs.


Issue with Campaign problem to find distinct valid campaigns

Let $DP[i]$ be the number of distinct valid campaigns whose last marketing email is the $i$-th email, $i$ from $1$ to $n$. As an extension, let $DP[0]=1$, which is the number of distinct valid campaigns without marketing emails.

For all $i\le k+1$, it is clear that the only valid campaign whose last marketing email is the $i$-th email is the campaign that has no marketing email other than the $i$-th email. That is,
$$DP[i]= 1\quad\color{#d0d0d0}{\text{ for all }i\le k+1.}$$
For all $i\gt k+1$,

Consider a valid campaign $\mathcal C$,  whose last marketing email is the $i$-th email. If the last marketing email of $\mathcal C$ is changed to a transactional email, $\mathcal C$ will become another valid campaign, which does not have marketing email or whose last marketing email is one of the first $i-k-1$ emails.
Conversely, consider a valid campaign $\mathcal D$, which does not have marketing email or whose last marketing email is one of the first $i-k-1$ emails. If we change the $i$ email of $\mathcal D$ to a marketing email, $\mathcal D$ will still be a valid campaign, whose last marketing email is the $i$-th email.

So, we have
$$DP[i]= DP[0] + DP[1] + \cdots + DP[i-k-1]\quad\color{#d0d0d0}{\text{ for all }i>k+1.}$$
The number of all distinct valid campaigns is
$$DP[0] + DP[1] + \cdots + DP[n].$$
If we implement the above approach to compute the array $DP$ iteratively, we can get an algorithm that runs in $O((n-k)^2)$ time and $O(n)$ space.

The algorithm above runs in time that is quadratic of $n$ when $k$ is not near $n$. It might not be fast enough when $n$ is large.
Let us do better. Since
$$DP[i+1]= DP[0] + DP[1] + \cdots + DP[i-k-1] + DP[i-k],$$
we have the following simpler recurrence relation,
$$DP[i+1]= DP[i] + DP[i-k]$$
for all $i\ge k+1$. Now we can write an algorithm that runs in $O(n)$ time and $O(k)$ space.

Here is a sample implementation in Python. For simplicity, $O(n)$ space is used.
def ways(n, k):
    dp = [1] * (n + 1)

    for i in range(k + 1, n):
        dp[i + 1] = dp[i] + dp[i - k]

    print(dp)  # for educational purpose.
    return sum(dp)

def test():
    print(5, 0, ways(5, 0))
    print(5, 1, ways(5, 1))
    print(5, 2, ways(5, 2))
    print(5, 3, ways(5, 3))
    print(5, 4, ways(5, 4))
    print(5, 5, ways(5, 5))

test()


Why is T not a minimum spanning tree of G?

Vertices: {A,B,C}

Edges: (undirected)
{A,B,4}
{A,C,3}
{B,C,2}

So basically it's a triangle with the given weights. Starting from A, Dijkstra's algorithm will give you (A,B) and (A,C) but the minimum spanning Tree will give you (A,C) and (C,B).


Is there any nontrivial problem in the theory of serial algorithms with a nontrivial polynomial lower bound of $\Omega(n^2)$?

There are such problems by time hierarchy theorem. Just take any problem that is complete for a large complexity class. For example, take a problem that is complete for $\mathsf{ExpTime}$. Such a problem will be $\Omega(n^c)$ for all $c\in\mathbb{N}$.

However also note that for problems in $\mathsf{NP}$, there are not strong time lower-bounds in multiple-tape TM model and existence of linear time algorithms for SAT is consistent with current state of knowledge. (In single-tape TM model it is not difficult to show that many problems like palindromes require $\Omega(n^2)$ time but such lower-bounds depend essentially on the particulars of the single-tape TM model.)


There are two settings under which you can get $O(1)$ worst-case times.

If your setup is static, then FKS hashing will get you worst-case $O(1)$ guarantees. But as you indicated, your setting isn't static.
If you use Cuckoo hashing, then queries and deletes are $O(1)$ worst-case, but insertion is only $O(1)$ expected. Cuckoo hashing works quite well if you have an upper bound on the total number of inserts, and set the table size to be roughly 25% larger.

There's more information here.


Yes, "that terminates" is the halting problem, not really in disguise but also not pointed out as problematic.


Hint:

Consider $25_{10}$. The number can be written as $5 \cdot 10^0 + 2 \cdot 10^1$.

How can $25_{r}$ be written?


What is the difference between strong normalization and weak normalization in the context of rewrite systems?

Weak normalization means that any term has a terminating rewriting sequence, i.e. admits a finite amount of rewritings which lead to a normal form (no more rewritings from that).

Strong normalization means that any term can never be rewritten infinitely many times. Any maximal rewriting sequence eventually reaches a normal form (hence it is finite).

For instance:

$$
    S \rightarrow (SS) \qquad
    S \rightarrow A
$$

is weakly normalizing (given any term, we can rewrite every $S$ into an $A$, after which normal form is reached) but not strongly normalizing ($S \rightarrow (SS) \rightarrow ((S S) S) \rightarrow \cdots$).

It is immediate to prove that strong normalization implies weak normalization.


What are the recents topics of research that combine both systems research and theoretical computer science?

This might not be what you mean by "theoretical computer science", but there's some rich interaction between Programming Languages Theory and Distributed systems going on with Session Types. They basically are a way to use type systems to specify communication protocols, increasing safety in distributed languages.

For example, The Imperial Mobility Group has many publications in session types, this should at least get you started on finding research in the area.


Where can I find a reasonable NLP CFG or CSG for English?

It is uncommon to use a "closed set" context free grammar because the number of production rules is staggeringly large. The typical approach is to recover a probabilistic context free grammar from a treebank (e.g., the Penn Treebank) in order to do statistical parsing (via probabilistic CKY, Earley, etc).

The only time you might want a "closed set" is when working with toy data in which case you may define an overly simplistic subset of English grammar dealing with sentences, noun phrases, verb phrases, and so on. Such miniature grammars can be found in standard NLP texts such as Jurafsky and Martin, and Manning and Schuetz.


Why $P$ cannot have NULL string in Arden's Theorem?

Here is the version of Arden's theorem on Wikipedia:

One solution of the language equation $R = Q+RP$ is $R = QP^*$.
If $\epsilon \notin P$, then this is the only solution.

When $\epsilon \in P$, there are more solutions. In fact, we can prove the following result:

The solutions of the language equation $R = Q+RP$, where $\epsilon \in P$, are $R=SP^*$ for all $S \supseteq Q$.

Proof. Let us first show that $SP^*$ is always a solution. Since $\epsilon \in P$, $RP = SP^+ = SP^*$. Since $SP^* \supseteq S \supseteq Q$, $Q + RP = Q + SP^* = SP^* = R$.
Let us now show that all solutions are of this form. Suppose that $R$ is a solution. Clearly $R \supseteq Q$. Since $\epsilon \in P$, this implies that $RP \supseteq R \supseteq Q$, and so $RP = Q + RP = R$. Induction shows that $RP^n = R$ for all $n \in \mathbb{N}$, and so $RP^* = R$. Since $R \supseteq Q$, this is a solution of the required form. $\square$


How the LZ77 compression algorithm handles the case when the entire look-ahead buffer is matched in the search buffer

A simple solution:  your look ahead buffer is no smaller than your longest match length.
  As long as the start position is in the Search Buffer(a min of 1 byte), then the look-ahead buffer will have that one extra byte available to use as the follow byte