Yes, you can.  You are defining the recurrence $T'$, so define $T'(1) = T(1)$.  Then, since $g(n)$ satisfies the regularity conditions, the Master theorem tells you that $T'(n) = \Theta(g(n))$.  Note that the Master theorem doesn't depend on the choice of $T'(1)$; it is a constant, and you get the same asymptotic bound for $T'(n)$ regardless of which constant you choose.

Now, you can prove by induction that $T(n) \le T'(n)$ holds for all $n$.  This is a simple induction.  The base case holds because you defined $T'$ that way.  The inductive step holds because $f(n) \le g(n)$ for all $n$.

Once you've proven that $T(n) \le T'(n)$ for all $n$, you are entitled to conclude that $T(n) = O(T'(n))$ and thus $T(n) = O(g(n))$.


This is a well known problem in computer science, and can be mentioned as "Find all distinct subset sums in an array". The obvious solution is to generate all subsets which will take O(2^n) time for an array of i elements. Instead, if the sum that you can make is relatively small, you can can use dynamic programming technique to precompute a table which will mark the reached sums. The implementation details of these two ideas can be seen here. Notice that this answers also the second question.

Regarding the third point, whether having a sorted array will allow for further optimizations, the answer is no. If you would've had an applicable greedy solution (taking always the maximum or the minimum element according to some criteria) than it would've been very possible to optimize it somehow, but with simple tests it can be proven that greedy doesn't work in this case. (if it had it would certainly be faster than the dp).


As a Teacher: Choosing a suitable programming language

My answer? Python.

Let me explain by tackling all your points.

Simplicity. Python code reads like English. Seriously, how simple is
print("Hello World!")
Generality. Python can be used for web development (via. Flask/Django), data analysis (via. NumPy/Pandas/SciPy), games (via. PyGame), as well as a multitude of other tasks because of the sheer amount of libraries there are.
Minimum Objective stuff. You can do some OOP in Python but it isn't required.
Platform. Python2.7 is in pretty much on every Linux distro and there are plenty of YouTube videos on setting it up on Windows/Mac. If anything, you can use the online interpreter that Repl.It offers.
Industry Preference. Correct me if I'm wrong, but Python has consistently been ranked as one of the most popular languages.

In my experience teaching, it is extremely important to make sure that the syntax is as easy as possible to write and understand. For a new programmer, it can be pretty discouraging when he/she writes code only to see an error message (especially if he/she does not have the skill to read an error message and debug).

Side note, PythonTutor will be really helpful in explaining some major computer science/programming concepts.


Difference between the Cartesian product in set theory and in relational algebra

The Wikipedia definition merely "opens the parentheses". Using the pure set-theoretic definition, we would expect
$$ ((r_1,r_2,\dots,r_n),(s_1,s_2,\dots,s_m)) $$
instead of
$$ (r_1,r_2,\dots,r_n,s_1,s_2,\dots,s_m). $$
Assuming $R,S$ are both relations over the same universe $U$,
the Wikipedia definition ensures that $R \times S$ is an $(n+m)$-ary relation over $U$. Under the set-theoretic definition, we get a binary relation over $U^n$ when $n = m$, and a unary relation over $U^n \times U^m$ in general.

We often write $U^n \times U^m = U^{n+m}$, but this isn't in general an equality of sets (it might be in some special cases, depending on the exact definition of $U^n$). Rather, we identify $U^n \times U^m$ with $U^{n+m}$, that is, we ignore the difference (this informal notion can be formalized). The difference between $R \times S$ as sets and as relations is similar – we identify the two objects although they are "physically" different.


How to compare the efficiency of two encoding schemes or hypothesis languages?

The answer was just tree depth. What I needed to do was learn about evaluating the complexity of finite automata and how we can use a decision-tree model (decision-tree complexity) to put bounds on the complexity of an automata (analysis of algorithms). So I take my two coding schemes (call them A and B) and I make binary decision tree to predict the output of my system based on the inputs provided by the coding schemes. If both coding schemes A and B are equally useful for predicting the outputs but A requires a tree depth of 15 while B requires a tree depth of 54 then A is "better".  This is because our decision-tree model of the system is simpler when using A than when using B and as stated before we strongly believe that our system is as simple as possible.

Of course I also need to include the complexity of the coding scheme itself but that just goes with alphabet size since it is a Nearest Neighbor search.

So it was under my nose, I just needed some context.


You need to ignore for a moment the strong feeling that the "$O$" is in the wrong place and plough on with the definition regardless.  $f(n) = \log^{O(1)}n$ means that there exist constants $k$ and $n_0$ such that, for all $n\geq n_0$, $f(n) \leq \log^{k\cdot 1}n = \log^k n$.

Note that $\log^k n$ means $(\log n)^k$.  Functions of the form $\log^{O(1)}n$ are often called polylogarithmic and you might hear people say, "$f$ is polylog $n$."

You'll notice that it's easy to prove that $2n=O(n)$, since $2n\leq k n$ for all $n\geq 0$, where $k=2$.  You might be wondering if $2\log n = \log^{O(1)}n$. The answer is yes since, for large enough $n$, $\log n\geq 2$, so $2\log n \leq \log^2n$ for large enough $n$.

On a related note, you'll often see polynomials written as $n^{O(1)}$: same idea.


Hint: Divide $A$ evenly into two smaller arrays $A_1,A_2$, and solve the problem (recursively) on $A_1$ and $A_2$. Can that help you find the optimum on $A$? Don't forget you're allowed to use extra processing costing up to $O(n)$.

Another hint: Suppose that $p,q$ is the optimal pair for $A$. Either $p,q \in A_1$, or $p,q \in A_2$, or neither of these cases is true. What can you say in the third case about $p$ and $q$?

As an aside, this can be solved in $O(n)$, in fact even online. We maintain the minimal element seen so far $m$, and the maximum difference $D = q-p$ over elements seen so far. Upon getting a new element $x$, we put $D = \max(D,x-m)$ and $m = \min(x,m)$, and update $p,q$ with $m,x$ if needed.


Where do these DRAM row/column calculations come from?

The first value describing the DRAM is the number of data-interface-sized "chunks" it contains and the second value is the width of the data interface in bits, i.e., bits per "chunk".  A 16x1 DRAM would only have 16 bits addressable at 1-bit granularity, with four rows and four columns allowing a minimization of address pins.  A 16x4 DRAM would have 64 bits addressable at 4-bit granularity (and with 16 addressable units a 4 row and 4 column arrangement would minimize address pins).


Why are some programming languages "faster" or "slower" than others?

In programming language design and implementation, there is a large number of choices that can affect performance. I'll only mention a few.

Every language ultimately has to be run by executing machine code. A "compiled" language such as C++ is parsed, decoded, and translated to machine code only once, at compile-time. An "interpreted" language, if implemented in a direct way, is decoded at runtime, at every step, every time. That is, every time we run a statement, the intepreter has to check whether that is an if-then-else, or an assignment, etc. and act accordingly. This means that if we loop 100 times, we decode the same code 100 times, wasting time. Fortunately, interpreters often optimize this through e.g. a just-in-time compiling system. (More correctly, there's no such a thing as a "compiled" or "interpreted" language -- it is a property of the implementation, not of the language. Still, each language often has one widespread implementation, only.)

Different compilers/interpreters perform different optimizations.

If the language has automatic memory management, its implementation has to perform garbage collection. This has a runtime cost, but relieves the programmer from an error-prone task.

A language might be closer to the machine, allowing the expert programmer to micro-optimize everything and squeeze more performance out of the CPU. However, it is arguable if this is actually beneficial in practice, since most programmers do not really micro-optimize, and often a good higher level language can be optimized by the compiler better than what the average programmer would do.
(However, sometimes being farther from the machine might have its benefits too! For instance, Haskell is extremely high level, but thanks to its design choices is able to feature very lightweight green threads.)

Static type checking can also help in optimization. In a dynamically typed, interpreted language, every time one computes x - y, the interpreter often has to check whether both x,y are numbers and (e.g.) raise an exception otherwise. This check can be skipped if types were already checked at compile time.

Some languages always report runtime errors in a sane way. If you write a[100] in Java where a has only 20 elements, you get a runtime exception. In C, that would cause undefined behavior, meaning that the program might crash, overwrite some random data in memory, or even perform absolutely anything else (the ISO C standard poses no limits whatsoever). This requires a runtime check, but provides a much nicer semantics to the programmer.

However, keep in mind that, when evaluating a language, performance is not everything. Don't be obsessed about it. It is a common trap to try to micro-optimize everything, and yet fail to spot that an inefficient algorithm/data structure is being used. Knuth once said "premature optimization is the root of all evil".

Don't underestimate how hard it is to write a program right. Often, it can be better to choose a "slower" language which has a more human-friendly semantics. Further, if there are some specific performance critical parts, those can always be implemented in another language. Just as a reference, in the 2016 ICFP programming contest, these were the languages used by the winners:

1   700327  Unagi                       Java,C++,C#,PHP,Haskell
2   268752  天羽々斬                     C++, Ruby, Python, Haskell, Java, JavaScript
3   243456  Cult of the Bound Variable  C++, Standard ML, Python

None of them used a single language.


Is it undecidable if the language of a given Turing Machine is the set of composite numbers?

Hint 1: Do you know Rice's theorem? It's the go-to result for any version of "Prove it's undecidable whether $L(M) =\,$ something."

Hint 2: You can reduce from "Does this TM accept everything?" You're given a Turing machine $M$ and you want to produce a new machine $T$ such that $T$ accepts the set of composites iff $L(M)=\Sigma^*$. Have $T$ reject its input if it's prime.  If the input is composite, use its factors to decide what input you'll feed to $M$. You need to do this in a way that every possible input to $M$ corresponds to some combination of factors of $T$'s input.

Hint 2.5: Alternatively, go from "Does this TM accept nothing?" Similar idea but now $T$ will accept if its input is composite and you'll use prime inputs to $T$ to code inputs to $M$. Actually, this one might be slightly easier to see.


The importance of the language semantics for code generation and frameworks for code generation in model-driven development

In general when we talk about code generation (or model-to-model transformation in general), clearly defined semantics is quite important, since such transformations usually make sense when both the source and the target model semantically match according to some criteria. For example, programmers might describe the behaviour of a program with a formal specification, which, according to the semantics, defines possible implementations in the target language (i.e. outputs of code generation). Failing to precisely define the semantics might lead to ambiguous or, in general invalid, transformations.

  Is there special kind of semantics of programming languages that is
  usable not only for the analysis of the programs but also for the
  generation of the programs?

In general, there is no need for a special kind of semantics for targeting generation of programs. However, different code generation systems target different domains of code generation and thus leverage different kinds of programming languages and their semantics. (Some overview of code generation in the context of program synthesis can be found in [1]).

There exists a body of work for which a programming language is coupled with language verification and program synthesis (described below). A seemingly well-fitting example of this is the Leon framework, which uses a subset of Scala as the main programming language, that expresses both programs and formal specifications. The framework allows not only verifying that the program matches the given specification (again, strictly defined by the semantics of the language and the interpretation of the logic used in the specification), but also generating code. In the latter case, programmers can only give formal specifications of the program in terms of its precondition and postcondition and the framework, it's code generation part (i.e. its synthesizer), generates the program that matches the given specification [2].

  My guess is that it should be really useful approach for generating
  formally verified code but I can not find research work about this.
  Are there trends of better keywords avilable for this?

One of the fields that seems to be closely matching what you described is software synthesis. Program synthesis is the task of automatically discovering an executable piece of code given user intent expressed using various forms of constraints such as input-output examples, demonstrations, natural language, etc [1].

  In reality I can not find any work that connects semantics of
  programming language with the code generation.

In general, the compiler for many general-purpose modern (high-level) languages perform some form of code generation that has to satisfy the rules of the language semantics (i.e. its language specification). E.g. the compiler for the Scala programming language emits Java bytecode---which can be thought of as a language which elements semantically closer match the instructions of the actual hardware---according to the Scala language specification.

  [About compiler and other tools for] Model Driven Development useful for
  code generation. What is the best pratice or framework for code
  generation?

Although, in my answer, I was focusing on the connection of the semantics of the programming language and code generation in the context of (general-purpose) program synthesis, these concepts are by all means applicable to other domains or practices such as Model-Driven Development. For general pointers on this direction, it might be useful to check out books that try to summarize them [4], [5].

  So - this is more question about application of K framework for code
  generation is that is possible at all?

Although, it might be the most suitable for your problem and intended use, there are other alternatives that might also work and perhaps could work for you as well, such as some of the transformation languages like Stratego or rewriting systems like Maude.

[1] Gulwani, Sumit. "Dimensions in program synthesis." In Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming, pp. 13-24. ACM, 2010.

[2] Kneuss, Etienne, Ivan Kuraj, Viktor Kuncak, and Philippe Suter. "Synthesis modulo recursive functions." Acm Sigplan Notices 48, no. 10 (2013): 407-426.

[3] Scala Language Specification

[4] Brambilla, Marco, Jordi Cabot, and Manuel Wimmer. "Model-driven software engineering in practice." Synthesis Lectures on Software Engineering 1, no. 1 (2012): 1-182.

[5] Milicev, Dragan. Model-driven development with executable UML. John Wiley & Sons, 2009.


It follows directly from the definition of BPP.

The definition says that a problem with a yes-or-no answer is in BPP if there is a randomized algorithm that gets the correct answer with probability $\ge 2/3$ on all possible instances.  This means that on all instances where the correct answer is YES, the algorithm has to output YES with probability at least $2/3$; and on all instances where the correct answer is NO, the algorithm has to output NO with probability at least $2/3$.

Therefore, if a problem $P$ is in BPP, its negation is also in BPP.  Take the algorithm for $P$, and just flip its output.  That will be a valid algorithm for the negation of the problem.


The meaning of discount factor on reinforcement learning

The discount factor does not represent the likelihood to reach the state $s′ $from the state $s$. That would be $p(s'|s,a)$, which is not used in Q-Learning, since it is model-free (only model-based reinforcement learning methods use those transition probabilities).
The discount factor $γ$ is a hyperparameter tuned by the user which represents how much future events lose their value according to how far away in time they are. In the referred formula, you are saying that the value $y$ for your current state $s$ is the instantaneous reward for this state plus what you expect to receive in the future starting from $s$. But that future term must be discounted, because future rewards may not (if $γ < 1$) have the same value as receiving a reward right now (just like we prefer to receive \$100 now instead of \$100 tomorrow). It is up to you to chose how much you want to depreciate your future rewards (it is problem-dependent). A discount factor of 0 would mean that you only care about immediate rewards. The higher your discount factor, the farther your rewards will propagate through time.

I suggest that you read the Sutton & Barto book before trying Deep-Q in order to learn pure Reinforcement Learning outside the context of neural networks, which may be confusing you.


Can this algorithm still be considered a Binary Search algorithm?

I would not call this a binary search.

It is clearly similar to binary search and it's natural to see it as a refinement of binary search.  However it has significantly different algorithm complexity characteristics, Interpolation Search has expected run time of O(log(log(n)) assuming the data is uniformly distributed, however it pays for this by having O(n) worst case run time.

I prefer to say "The worst case run time of binary search is O(log(n))" rather than "Depending on the choice of bounding elements the worst case run time of binary  search is O(log(n))".  This means that I can not classify Interpolation search as a binary search algorithm.


Q1-does it mean that x86-64 is just an alias name of EM64T?

The original name for the architecture is AMD64.
That is also the marketing name that AMD uses for that architecture.
When Intel licensed it from AMD, they first called the feature CT, then IA-32e, then EM64T, and most recently Intel 64. Those are Intel's marketing names. Note that Intel 64 contains extensions on top of AMD64 as well.
x64 is not an official name. It is a marketing name created by Microsoft in order to refer to both Intel's and AMD's (as well as other vendors') implementations without using the name of one of the two main competitors.
x86-64 is not an official name. It is a marketing name used by many vendors in order to refer to both Intel's and AMD's (as well as other vendors') implementations without using the name of one of the two main competitors.
x86_64 is the GNU Autotools architecture designation used in tools such as Autoconf, Automake, and GCC.
IA-32 is, I believe, a term that Intel only introduced after they started working on IA-64. Until then, the architecture was colloquially known as x86, but did not actually have a name.
The bottom line is that you can mostly use the terms AMD64, IA-32e, x86-64, and x64 interchangeably, and people will probably understand what you are talking about. But, the official name for the architecture is AMD64, but that can also refer to AMD's specific implementation of that architecture (which may have AMD-specific extensions). Whereas IA-32e is Intel's specific implementation of the AMD64 architecture, which may have Intel-specific extensions.

Q2- And is IA32 developed by AMD?

No, it isn't.

isn't IA32 designed by Intel and first implemented in the 80386 microprocessor in 1985?

Yes, it is, although the name IA-32 came later.


Knapsack problem with the restriction on the number of items

Iterative solution (recursive is very similar too):

Have a 2d array $mat[W][k]$ and let the columns be $0..k$ and the rows be from $0..W$. Let $mat[x][y] = 0 \;\forall \;0\le x \le W, 0\le y \le k$. Let $mat[0][0] = 1$.

Now run $i$ across $[1,k]$. Within the $i$ loop run another loop iterating $j$ across $[1,W]$. In every iteration of the inner loop, run through the set of elements and calculate this:

$${mat[i][j] = \sum_{l=1}^{|X|} mat[i-1][j-X_l] }\:$$

$mat[W][k]$ will store the final answer. Time complexity = $\mathcal{O}(W.k.|X|)$, and space complexity = $\mathcal{O}(W.k)$.


Is the 2nd parity bit in RAID 6 a simple calculation?

The general case is indeed a bit complicated.

However, in the case of 4 disks you can simplify it a lot; you do not really need to know any fancy math. You only need to know how to store 4 bits redundantly, and then you already know everything; just repeat the same scheme for each group of 4 bits that you need to store.

We can represent the scheme as 4 x 4 tables. The first 2 bits of our data determine the row and the last 2 bits of our data determine the column.

Disk 1: Just store the first 2 bits. That is:

00 00 00 00
01 01 01 01
10 10 10 10
11 11 11 11

Disk 2: Just store the last 2 bits. That is:

00 01 10 11
00 01 10 11
00 01 10 11
00 01 10 11

So far so good. Given disk 1 + disk 2, we can recover our original data: disk 1 tells us the row (the first 2 bits of the original data) and disk 2 tells us the column (the last 2 bits of the original data).

Disk 3: This is what we do on RAID5, just XOR the bits:

00 01 10 11
01 00 11 10
10 11 00 01
11 10 01 00

Again, everything is still fine. You can recover the original data using disk 1 + disk 3 or disk 2 + disk 3. A key observation is that the lookup table for disk 3 forms a Latin square: all elements of each row are distinct, and all elements of each column are distinct. For example, if you know the data on disk 1, you know the right row, and then you can use the data on disk 3 to recover the column. Conversely, if you know the data on disk 2, you know the right column, and then you can use the data on disk 3 to recover the row.

Disk 4: Here we can use the following lookup table:

00 01 10 11
10 11 00 01
11 10 01 00
01 00 11 10

Don't worry how it is constructed; we do not really care about that. The crucial properties are:

The lookup tables of both disk 3 and disk 4 are Latin squares. Therefore if you know 1 + 3 or 1 + 4 or 2 + 3 or 2 + 4, you can recover both row and column (i.e., the original data).
The lookup tables of disk 3 and disk 4 form orthogonal Latin squares, which makes it possible to recover the data if we only have disks 3 + 4.

Let's elaborate on the second point. By concatenating the lookup tables of disk 3 and disk 4, we get this matrix:

0000 0101 1010 1111
0110 0011 1100 1001
1011 1110 0001 0100
1101 1000 0111 0010

Now note that each 4-bit string occurs in this table exactly once. That is, if we know what is stored on disks 3 + 4, we know where we are on this table. We know both the row and the column, and hence we can recover the original data.

If you insist on seeing the connection to Galois fields, consider the field $F = GF(2^2)$. Label the elements of the field with $F = \{0,1,x,x+1\}$; these correspond to 2-bit strings ($0$ ≈ 00, $1$ ≈ 01, $x$ ≈ 10, $x+1$ ≈ 11). Now any 4-bit string can be encode as a pair $(a,b)$, where $a,b \in F$.

A pair $(a,b)$ is now stored as follows:

Disk 1 stores $a$.
Disk 2 stores $b$.
Disk 3 stores $a+b$.
Disk 4 stores $xa+b$.

Now given, for example, just $p = a+b$ and $q = xa+b$, you can solve $a$ and $b$. Using the rule $2 \equiv 0$, you can find

$p + q = (xa+b) + (a+b) = (x+1)a + 2b \equiv (x+1)a$,
$p + xq = (xa+b) + x(a+b) = 2xa + (x+1)b \equiv (x+1)b$.

Then divide by $x+1$ to get $a$ and $b$, etc. But in the end, this approach gives you precisely the same lookup tables as what was presented above.


Computing a partial density matrix from an amplitude vector

It's a matrix multiplication. Not sure how I didn't notice it right away, but the problem is exactly computing $U \cdot U^\dagger$ for a $U$ whose rows are made up of the chunks of amplitude vector.

def density_matrix_of_first_half(amplitude_vector):
  U = new ComplexMatrix(2^n, 2^n)
  for i < 2^n:
    for j < 2^n:
      U[i, j] = amplitude_vector[i + (j << n)]
  P = U * U.adjoint()  // <-- expensive
  return P

Fancy matrix multiplication does asymptotically better than the naive algorithm

Matrix multiplication can be done in time $O(n^\omega)$, where $n$ is the dimension of the matrix and $\omega$ is known to be below $2.375$. It's conjectured that there may be algorithms where $\omega = 2 + \epsilon$, but no one's managed to find any yet.

In the context of the question with $2^n \times 2^n$ matrices, the complexity is $O(2^{n \omega})$. However, because the asymptotically faster algorithms tend to have large constant factors hidden by the Big-O notation, in practice it's often better to stick with naive multiplication or Strassen multiplication. Also there are probably GPU-optimized matrix multiplication algorithms that would be more relevant given the note at the end of the question.

$U \cdot U^\dagger$ is not easier than $U \cdot V$

General matrix multiplication combines two totally independent matrices $U \cdot V$. Given that our density matrix problem only computes $U \cdot U^\dagger$, where the two inputs are totally dependent, one wonders if this "adjoint-squaring" is easier than general multiplication. Turns out it's not.


Does Huffman algorithm generate a minimal weight of a tree?

If you normalize the frequencies so that they add to 1, then the weight of the tree is just the average codeword length, which is exactly what Huffman's algorithm tries to minimize. Check this section of the Wikipedia article you link to.


Minimum number of tree operations to normalize a labeled tree

$O(n \log n)$ operations suffice, as you conjectured.  One can implement something akin to quicksort (using the median as the pivot in each stage).  I'll describe the details below.  For simplicity of exposition, let's assume $n$ is a power of two (though it all works for arbitrary powers of two).  We'll bring the tree into a normal form, which is a complete binary tree (i.e., all leaves are at the same depth, $\lg n$).

Let $\alpha$ be the $n/2$th label (in sorted order of the labels).  We'll first manipulate the tree so it has the form $xy$, where $x$ is a subtree of size $n/2$ containing all items $\le \alpha$ and $y$ is a subtree of size $n/2$ containing all items $>\alpha$.  Call this the partition operation.  Then, we'll recursively apply the algorithm to the left subtree and to the right subtree.

I'll argue below that the partition operation can be done with $O(n)$ operations.  Then it follows that the total number of operations performed by this algorithm obeys the recurrence relation

$$T(n) = 2 T(n/2) + O(n),$$

which has the solution $T(n) = O(n \log n)$. It follows that this algorithm takes $O(n \log n)$ operations.

So how do we do the partition operation?  Well, suppose the tree is originally of the form $uv$.  We'll recursively apply the partition algorithm to $u$, to get a tree of the form $u_0u_1$ where the leaves of $u_0u_1$ are the same as the leaves of $u$, but now $u_0$ has all items of $u$ that are $\le \alpha$ and $u_1$ has the items that are $>\alpha$.  Similarly, we'll recursively apply the partition algorithm to $v$, to get $v_0v_1$.  So after the recursive calls to the partition algorithm, the tree has the form $(u_0u_1)(v_0v_1)$.  Now by a constant number of applications of commutatively and associativity, this can be transformed to $(u_0v_0)(u_1v_1)$.  At this point, the tree has the desired form, as $u_0v_0$ is composed of all of the items of $uv$ that are $\le \alpha$ and $u_1v_1$ is composed of all of the items of $uv$ that are $>\alpha$.

The running time of the partition algorithm is given by the recurrence

$$U(n) = 2U(n/2) + O(1),$$

which has the solution $U(n) = O(n)$.  Thus, the partition algorithm can be done in $O(n)$ operations.


fully homomorphic encryption with information-theoretic security?

You said you don't need to conceal the set of transformations that have been applied.  In that case a simple scheme is

$$T(\text{Enc}(x)) = \langle T, \text{Enc}(x)\rangle,$$

where $\text{Enc}$ is information-theoretically secure encryption (e.g., the one-time pad).  In other words, you simply list in the cipher text which transformations should be applied to $x$ after it is decrypted.


time efficient key value store for fast lookup

Make a table with 2^22 entries to lookup the highest 22 bits of the key. Each entry is responsible for one value on average (but may contain up to 1024).

Entry #i in the table, which is responsible for 0 to 1024 values with keys from 1024i to 1024i + 1023, contains the following: 1. The number of keys in that range. 2. If there are 0 keys, the value of the next lower available key. If there is 1 key, the lower 10 bit of the key in that range, and its value. If there are two or more keys, an index j into a second table.

In the second table, we store the lower 10 bit of the key, plus the value, for every key where there are two or more keys in the range from 1024i to 1024i + 1023. For values in the second table, we use binary search.


How is the concurrent tracking of "state position" in NFA's typically modelled?

The theoretical treatment is just to say "It's what happens: that's what nondeterminism is." The machine accepts if there's any computational path that finishes in an accepting state.

Anything about memory, caches or concurrency is a matter of implementation.  The simplest implementation is to keep a vector of Booleans that records whether or not the machine "could be" in each of the states at the current step of the computation.


If you delete the vertex $v$, then there are no edges left at all, and so there is a vertex cover of size $0 \leq k-1$.

Why is the statement true in the first place? Suppose that $G$ has a vertex cover $C$ of size $k$. Since $(u,v)$ is an edge, $C$ must contain at least one of $u,v$, say $v$. I claim that $C \setminus v$ is a vertex cover of $G \setminus v$, from which the statement immediately follows. Indeed, let $(a,b)$ be any edge of $G \setminus v$. Then $(a,b) \in G$, and so $C$ contains one of $a,b$, say $a$. By construction, $a \neq v$, and so $a \in C \setminus v$.


Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs

Since nobody else answered, here is what I had in mind when I made my comment.  The basic idea behind the proposed amplification algorithm is that expanders are "negatively curved" in the sense that small sets in degree-bounded expanders should have a lot of their volume near the boundary. This then suggests that a ball centered in a small set should quickly "escape" with reasonable probability.

To answer a question from your comment, since the ball around a random vertex isn't a uniformly random set, we wouldn't expect a bound like $2^{-s}$ for the probability of being bad. Instead we get something that depends on $\epsilon$ and $d$ (with bigger $\epsilon$ and smaller $d$ being better if the other parameter is held fixed).

As in my comment, set $X\subset \{0,1\}^n$ to be the random strings where our RP algorithm $A(x,r)$ gives false negatives and $Y$ be the complement.  Since $G$ is a $(N,d,\epsilon)$-expander with $N = 2^n$, and $|X|\le N/2$ by hypothesis, we know that:

at least $\epsilon |X| / d$ different vertices in $X$ have a neighbor in $Y$

Notice that this already gives us something, since if we took $\delta = 1$, the improved algorithm now gives a false negative with probability only $1/2 - \epsilon/d$. The question just asks us to be a bit more ambitious.

To this end, define
$$
X_i := \{r : d(r,Y) \ge i\}
$$
What we just argued was that $|X_2| \le (1-\epsilon/d)|X|\le (1-\epsilon/d)N/2$.  From the way we've defined $X_i$, we the neighborhood of $X_i$ is contained in $X_{i-1}$ for $i\ge 3$.  This lets us replay the same argument to show that, for $i\ge 3$ we get $|X_i|\le (1-\epsilon/d)|X_{i-1}|$.  By induction we then get that  $|X_s|\le (1-\epsilon/d)^{s-1}N/2$.

Finally, observe that the improved algorithm fails when the chosen $r$ is in $X_{s+1}$. For $s=\Theta_{\epsilon,d}(\log n)$ this probability is $n^{-c}$.


Absolutely yes! your arguments are correct. And, as matter of fact, it is very easy to come up with a graph where Bidirectional Dijkstra would expand more nodes than Unidirectional Dijkstra, following your reasoning.

Consider a graph $G(V, E)$ where $V$ is the set of vertices, $E$ is the set of edges and you want to find the shortest path between two vertices $s, t\in V$ (from source and target respectively). Say there is a single path of length $\ell$ from $s$ to $t$, $\pi\langle s, u_1, u_2, \ldots, u_{\ell-1}, t\rangle$. Let us assume further:

$s$ has only one descendant, $u_1$
And, in general, $u_i$ has only one descendant, $u_{i+1}$, $1\leq i<\ell - 1$

However, $t$ has many different descendants: $\{v_1, v_2, \ldots, v_k\}$. For the sake of clarity, let us assume without loss of generality that the cost of all edges is 1 and that the path $\pi\langle s, u_1, u_2, \ldots, u_{\ell-1}, t\rangle$ is the only optimal path.

Now, Bidirectional Dijkstra would expand first $s$ in the forward search and then $t$ in the backwards search. The forward OPEN list contains only $u_1$, whereas the backward OPEN list contains $\{v_1, v_2, \ldots, v_k\}$ and $u_{\ell-1}$. Next, $u_1$ is expanded in the forward search and the forward OPEN list only contains $u_2$. However, the backward search might choose $v_1$ for expansion. This is your case! $v_1$ does not belong to the optimal path, yet it is expanded by Bidirectional Dijkstra (admittedly, this depends on the tie breaking strategy but assume $k$ is too large and ties are broken randomly). In the end, the forward search would go all over $\pi$ whereas the backwards search might be entertained expanding descendants of nodes $v_i$.

However, the Unidirectional search algorithm would have gone all the way through $\pi$, as it is its only choice, finding the goal node in precisely $\ell$ expansions.

To prevent this, Ira Pohl's principle of cardinality is applied often. It dictates to expand nodes from the OPEN list with less nodes. In this case, it would suggest expanding only nodes from the forward search, making Bidirectional Dijkstra to behave like Unidirectional Dijkstra. However, it should not be very difficult to make some maths to find a little bit more involved case where Ira Pohl's principle of cardinality does not help and Bidirectional Dijkstra still expands more nodes than Unidirectional Dijkstra.

In general, we say that Bidirectional Dijkstra expands only $O(b^{d/2})$ nodes whereas Unidirectional Dijkstra has to expand $O(b^d)$ nodes, but this assumes that the branching factor is the same for the forward and backward search.

For a much broader discussion on the topic which also includes the intricacies of applying bidirectional search to heuristic search I do strongly recommend you reading: Robert C. Holte, Ariel Felner, Guni Sharon, Nathan R. Sturtevant. Bidirectional Search that is guaranteed to meet in the middle. AAAI 2016.

Hope this helps,


Versions of NP with different logical unifiers

In the case of XOR or EQUALS, you get the class $\oplus$P, which includes the graph isomorphism problem.

In the case of NAND or NOR, I believe that you get PSPACE. Indeed, PSPACE is an upper bound, and you should be able to solve QBF in this model.


Graph coloring with fixed-size color classes

This problem is NP-hard: it is at least as hard as independent set.  In particular, if you want to know whether there exists an independent set of size $N$, ask for a coloring with as many colors of size $N$; if you find any coloring where a single color occurs $N$ times, you know there's an independent set of size $N$.  So, you should not expect any efficient algorithm for this problem that works on all problem instances.
One plausible approach is to use a ILP solver.  You can define zero-or-one variables $x_{v,c}$, where $x_{v,c}=1$ means that vertex $v$ is assigned color $c$.  Then it is easy to express the requirement that a color $c$ be assigned to exactly $N$ vertices: we require $\sum_{v \in V} x_{v,c} = N$.  The constraint that two adjacent vertices $v,w$ be assigned different colors can be expressed by $x_{v,c} + x_{w,c} \le 1$ for all $c$, and that each vertex $v$ receive a color by $\sum_c x_{v,c} = 1$.  Without loss of generality, to test whether it is possible to have $k$ colors be assigned to $N$ vertices, you can constrain the first $k$ colors to have $N$ vertices and put no constraints on the remaining colors.  Then, use binary search on $k$ to find the largest $k$ for which a solution exists.
Another plausible approach is to use a SAT solver.  You could define variables $x_{v,c}$, where if $x_{v,c}$ is true then vertex $v$ is assigned color $c$, and express your constraints in SAT.  You can require that color $c$ be assigned to exactly $N$ vertices, by requiring that $N$ out of the variables $x_{\cdot,c}$ are set to true (see Encoding 1-out-of-n constraint for SAT solvers and links for methods).  Otherwise, this is similar to using an ILP solver.
These might work if $N$ is small enough and the graph is small enough, but eventually will run into exponential behavior once the problem gets large enough.


Algorithm to convert undirected connected graph with no bridges to strongly connected directed graph

Well the idea of dfs is quite good all you need to orient all edges away from the vertex that discovered them.

You will have a path from the root to each  vertex since the graph is connected and the dfs will visit all vertices.

Claim. From each vertex you can reach the root.

Proof. Let $\mathcal{C}$ be the strongly connected components of the resulting graph. Let $\mathcal{G}$ be the DAG resulting from contracting the vertices in each component in $\mathcal{C}$. Also, let $C_0 \in \mathcal{C}$ be the strongly connected component containing $r$. We have to prove that $C_0$ is the only component in $\mathcal{C}$ and hence, it contains all the vertices in the graph. Assuming otherwise, all components must be reachable from $C_0$ in $\mathcal{G}$, since all vertices are reachable from $r$ in $G$. choose $C$ to be a component in $\mathcal{C}$ that is the end of a longest path $P$ from $C_0$ in $\mathcal{G}$. Let $C'$ be the component previous to $C$ on that path. There is an edge from a vertex in $C'$ to a vertex in $C$. But this edge is not a bridge, hence, there must be an edge leaving $C$ and directed from $C$ to outside $C$ (since such an edge must have been discovered the first time we visited $C$). If this edge goes to a component $C''$ not on $P$, we could have extended $P$ to $C''$ resulting in a longer path wich is a contradiction. On the other hand, if it goes to a component on $P$, it forms a cycle, which contradicts the assumption that $\mathcal{G}$ is the DAG over the SCCs of the graph we build from $G$ and hence cannot have cycles. Hence, $\mathcal{C}$ cannot have more than one component, namely $C_0$.


Confused with the proof that Edmonds-Karp always monotically increases the shortest-paths

Answer to Question 1:

Because of how we chose , we know that the distance of vertex  from the source  did not decrease, i.e., ′(,)≥(,)
Why the shortest-path from  to  after the augmentation of flow  must be greater than or equal to the distance before the augmentation ? How it is possible to have greater distance that it was ? The augmentation only removes the edge (,). But, the vertex  still in place, isn't it must be strictly equal ?

Because in the Proof, "We will suppose that for some vertex $v \in  V - \left \{  s, t\right \}$, there is a flow augmentation that causes the shortest-path distance from $s$ to $v$ to decrease". So, if we consider $u$ is the opposite type compared to $v$, that is to say, the shortest-path distance from $s$ to $u$ does not decrease: equation (26.13)  $\delta _{f'}\left ( s,u \right )\geq \delta _{f}\left ( s,u \right )$ holds.
Of course, if you suppose that $u$ is same type as $v$, which has decreasing shortest-path distance from $s$ to $u$, then we can take $u$ to replace the $v$, and find the path, $p:s\rightarrow x \rightarrow u$, where $\delta _{f'}\left ( s,x \right )\geq \delta _{f}\left ( s,x \right )$ holds. In this case $x$ takes the place of $u$ in eq(26.13).
Answer to Question 2:

If we had (,)∈, then we would also have (,)≤(,)+1
This looks like ok for me to have such case. We claim that distance from  to  is less than or equal to the distance from  to  plus 1. But in the graph before the first augmentation this case must be true. It is false for less than case, but true for equal case.

If the shortest path from $s$ to $v$, $p_v: s\rightarrow u \rightarrow v$ overlaps with the shortest path from $s$ to $u$, $p_u: s\rightarrow u$, the equal case happens.
$\delta_f(s,v)=\delta_f(s,u)+1$.
If the two paths $p_v$ and $p_u$ are not overlapped, the shortest path from $s$ to $v$, $p_v: s \rightarrow v$ would not contain the node $u$. Since $p_v$ is the shortest path, obviously the length of $p_v$ should be shorter than the length of $p_u$ + $(u,v)$ (another path from $s$ to $v$). Therefore the less than case happens: $\delta_f(s,v)<\delta_f(s,u)+1$.
Answer to Question 3:

How can we have (,)∉ and (,)∈′ ? The augmentation must have increased the flow from  to . The Edmonds-Karp algorithm always augments flow along shortest paths, and therefore the shortest path from  to  in  has (,) as its last edge.
The edge set $_$ is before the first augmentation and $_{′}$ is after it. The first augmentation must remove the edge (,) and put the reverse edge (,) into the edge set $_{′}$, but not the same edge (,). That is why how we can have (,) in $_{′}$ ?

$(u,v)\notin E_f$ and $(u,v)\in E_{f'}$ mean that the newly augmentation augments flow (a cancellation flow for $(u,v)$) along the edge $(v, u)$. Recall that, augmentation happens on the shortest path, which means that $(v,u)$ is on the shortest path $p$ from $s \leadsto v \rightarrow u \leadsto t$. If $p$ overlaps with the shortest path from $s \leadsto u$, $\delta _{f}\left ( s,v \right ) =  \delta _{f}\left ( s,u \right )-1$ holds. However I am not sure now that the overlapping does happen.


In a simple path, no node can be traversed more than once. However, paths in general can. The SSSP asks for single-source shortest paths, without specifying that the paths need to be simple. This allows the paths to contain cycles. Thus, negative cycles are a concern as they may allow arbitrarily "short" paths, and so the definition of a "shortest" path falls apart. This is because if a path contains a node on a negative cycle, we can always lower the cost of the path by going around the negative cycle.

Of course, this also depends on how you define a path, and how the SSSP has been presented to you. The above explanation assumes typical definitions of both, so if you have different definitions, please leave a comment.


How to prove that a binary heap can't be sorted with complexity that better than O(nlogn)

A binary heap with $n$ elements can be built in time $O(n)$. If there was a (comparison based) sorting algorithm capable $A$ of sorting the elements in a heap in time $o(n \log n)$ then you could obtain a (comparison-based) sorting algorithm $A'$ that works for arbitrary sequences $S$ of $n$ elements. Algorithm $A'$ is as follows:

Construct a heap $H$ from $S$.
Execute $A$ with input $H$.

Such an algorithm requires time $O(n) + o(n \log n) \in o(n \log n)$ and hence it contradicts the $\Omega(n \log n)$ lower bound on comparison-based sorting algorithm. Therefore, algorithm $A$ cannot exist.


I will focus on questions 2 and 3, mainly by recalling a little bit of history of the Relational Data Model.

The first foundamental paper on the Relational Model was published in 1970 by the Turing Award Edgar F. Codd, Codd, E. F. “A Relational Model of Data for Large Shared Data Banks.” Communications of the ACM 13, no. 6 (June 1, 1970): 377–87. (bibliographic description, search pdf).

In that paper it is expressed clearly that relations are sets:

  The term relation is used here in its accepted mathematical sense. Given sets S1, S2, ... , Sn, (not necessarily distinct), R is a relation on these n sets if it is a set of n-tuples each of which has its first element from S1, its second element from S2 , and so on ...

So, the requirement of the unicity of the tuples precedes each possible definition of normal form.

Noting that the Codd’s definition leaves open the possibility that the elements of the domains (the Si) can be complex, for instance repeated, Codd introduced the first normal form (1NF) in a 1972 paper:  “E. F. Codd (Oct 1972), Further normalization of the database relational model, Courant Institute: Prentice-Hall, ISBN 013196741X,”. In such paper it is said that:

  A relation is in first normal form if it has the property that none of its domains has elements which are themselves sets.

As you have noted, this has nothing to do with functional dependencies, neither with other forms of dependencies (multivalued, join, etc.), and for this reason, it has been considered an essential requirement of the “normal” Relational Data Model. Other data models, the so called non-1NF model, abandon this requirement, and constitute a sort of bridge towards late object-oriented data model (but this is another subject...)

Only later, C.J. Date, a collaborator of Codd, wrote in the paper: “What First Normal Form Really Means,” in “Date on Database: Writings 2000-2006. Berkeley, Calif., Apress (2006)”:

  A table is in first normal form if and only if it is "isomorphic to some relation" ... There are no duplicate rows...."

The emphasis is mine, note that he’s talking about tables, not relations, specifying what are the characteristics that tables should have to be considered relations.

So, to summarize:

The relational model is based on the mathematical concept of relation, which is a set.
The 1NF has nothing to do with functional dependencies, and in the original definition has only to do with complex values (i.e. relations) inside tuples.
The other normal forms are defined ony in the context of the relational data model, in which relations are set.
Relational Database Management Systems (RDBMS) manage “tables”, which are loosely modeled on the mathematical concept of relation as defined in the Relational Data Model, but the normalization theory (functional dependencies, other kind of dependencies, normal forms, etc.) is only partially applicable to them, since it is defined only on the Relational Data Model.


This explanation is wrong. In principle you could prove that $K_{3,3}$ is not planar by enumerating all types of planar embeddings, and show that some paths must cross. If I remember correctly this is the path chosen in some lecture notes, so if you look around you might be able to find this argument. Another route, taken by your lecture notes, is to use Euler's formula.

When your notes say that $K_{3,3}$ isn't planar since it "has a cycle", they were trying to provide you some intuition, not too successfully I reckon. The claim requires a proof which is indeed given later in the notes.


The complexity of BDD Synchronous Composition

I'm not aware of such a result in any paper, but that may be because it is relatively clear that this operation is non-polynomial.

And here is why. Assume that we have a satisfiability problem with $n$ variables and $c$ clauses. We allocate variables $v_1, \ldots, v_n$ and $v'_1, \ldots, v'_c$ in the BDD manager, build a BDD

$$B = \bigwedge_{i \in \{1, \ldots, c\}} v'_i$$

and also BDDs $x_1, \ldots, x_c$ that encode the clauses over $v_1, \ldots, v_n$. Note that all BDDs are of size $O(c)$ or $O(n)$, which is even independent of the variable ordering.

Now computing

$$C = B[x_1/v'_1,x_2/v'_2, \ldots, x_c/x'_c]$$

gives us a BDD that represents the set of all solutions to the SAT problem (where [...] is the application of the synchronous composition operator). If we could compute $C$ in time polynomial in the size of the SAT instance, that would give us a polynomial time algorithm for SAT. Even more, with $C$, we can count the number of solutions, which lies in a higher complexity class that finding them. Also, making use of a fixed variable ordering of the BDD, the argument can be extended to talk about the QBF problem, which is PSPACE complete.

Obviously, this does not answer your question to 100%. But in the light of this line of reasoning, I would find it surprising if the algorithm actually implemented in BDD libraries was polynomial-space (or even polynomial time).


How to simplify sum of products boolean expression?

From a Karnaugh map you can get a one group of 4s and three group of 2s. So you can reduce sum of 4 term in which three will have 3 literals and one with 2 literals. By doing it use K-map you will use few 1s for more than one terms so if you don't want to use a K-map just use idempotent rule($x = x + x$) and then simplify.


Where to start on SJF Cpu schedualing homework problem?

Alright, so after reviewing with the professor, this is how this actually works.

The default of 2 means they all have an equal priority and just get run in order; process P1, P2, and P3.

Now, once we see P1 run for 3 quantums after the first burst, then we calculate its new prediction.

(0.6) * 2 [original default] + (0.4) * 3 [last run] = 1.2 + 1.2 = Prediction of 2.4

Same thing with P2 & P3 (both have a first burst of 2 quantums.)

(0.6) * 2 [original default] + (0.4)* 2 [last run] = 1.2 + 0.8 = Prediction of 2.0

So for the next quantums' order, it would be P2, P3, THEN P1.

Then after that run you would just do;

(0.6) * [2nd to last burst] + (0.4) * [last burst] = new prediction to figure out which proces would run next.

So the actual order would be;

Quantum: Process

Q3: P1:3

Q5: P2:2

Q7: P3:2

Q8: P2:2 (FINISHES)

Q12: P3:3

Q14: P1:2

Q19: P3:5

Q24: P1:5 (FINISHES)

Q30: P3:6 (FINISHES)


How to speed up finding a subset of a given set?

if you map every element in set in S into a bit in a binary number. For set with n elements, we have n bit binary number. the $i$-th number takes 1 if the subset has that element. Then we can use a binary number from $00,...,00$ to $11,...,11$  to represent all the subset.

If you map all your subset into binary numbers, then you are searching in the number space.


A query regarding the hierarchy of monotone Complexity Classes

Raz and McKenzie, Separation of the monotone NC hierarchy, showed that the monotone NC hierarchy is strict, and separated it from monotone P. In all of these separations, the upper bound holds for the uniform class while the lower bound holds even for the non-uniform class (so by monotone P, they really mean monotone P/poly).

Monotone P is easy to separate from monotone P/poly since the latter contains uncomputable functions. For example, the language $\{w : |w| \in K\}$ is in monotone P/poly for any $K \subseteq \mathbb N$, but isn't in monotone P if $K$ is uncomputable.

(By the way, there are several reasonable ways to define monotone P, and I'm not sure they are all equivalent. However, all of them should satisfy what I wrote in the preceding paragraph.)


"Archiving" byte sequence into human-readable set of chars

A common encoding used for such tasks is Base64. It is easy to implement and it has been implemented multiple times in many main-stream languages. However, it is not exactly suited for being read by humans.

The basic underlying idea is that a character of Latin alphabet is encoded in ASCII using 6 bits. The encoding alphabet is completed by few punctuation symbols to make it the exact multiple of 8.

Here is a nice even if somewhat light-hearted proposal http://www.crockford.com/wrmg/base32.html for alternative Base32 encoding (it also tries to prevent occasional appearance of expletives in the produced encoding, at least if it is interpreted as English language).

Unfortunately, you won't be able to make it much shorter using only Latin alphabet, unless you have more information about the nature of the data being encoded. Text compression algorithms would try to discover such information about the text being encoded and use variable length encoding, assigning shorter sequences in the output to the more common sequences in the source text. For a simple example of such encoding you can look into Huffman coding

Another, obvious way to shorten the output length is to use a larger alphabet.


Why does the following function distribute things in a binomial distribution?

The second function is easier to explain: it sends tract $t$ to position $t + h \pmod{n}$, where $h = hash(g)$. The function $t \mapsto t + h \pmod{n}$ is injective (one-to-one), and so every index $i$ gets mapped exactly once (in fact, by $i - h \pmod{n}$).

For the first function, we can think of $t \mapsto hash(g+t)$ as a random function (this is a common assumption whenever hash functions are involved; the fact that we use SHA-1 is completely irrelevant). Therefore for each fixed index $i$, the probability that $t$ is mapped to $i$ is $1/n$, and the total number of $t$s mapped to $i$ is distributed $\mathrm{Bin}(1/n,1) \approx \mathrm{Po}(1)$, that is it has binomial distribution which is approximated well by a Poisson distribution with mean $1$.


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

XY + /XZ + YZ

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

(removing two redundant terms)

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

= XY + /X.Z


Relation between digraph and NP-Complete problem

When a problem is NP-complete, it doesn't necessarily mean that all instances are hard to solve. It just means that enough instances are hard to solve that, if you could solve this problem efficiently, you could do the same for all problems in NP. Enough, in this case, does mean infinitely many1 and that should lead you towards looking at large inputs if you want to find hard cases.2

For example, the fact that 3-SAT is NP-complete doesn't mean that you would have any difficulty telling me whether the formula $(X\vee Y\vee Z)$ is satisfiable. In your example, you've observed that, for a graph with a single edge, that edge is a Hamiltonian path. That doesn't mean that it's hard to tell whether a graph has a single edge, or that it's easy to compute Hamiltonian paths on all graphs.

1 Probably infinitely many, anyway. If P = NP, there wouldn't be any "hard" instances of NP-complete problems.

2 Note that, strictly speaking, there's no such thing as a single "hard case" since, if we restrict to that single input, the problem can be solved in constant time. Properly, I mean a whole infinite class of instances such that it's "hard" to write an algorithm that answers the problem on that whole class of inputs.


Is it possible to solve the halting-after-$n$ steps problem more efficient than just execute $n$ steps?

The time hierarchy theorem, or rather its proof, gives some answer to this question. If you look at the proof, you should get a lower bound of $\Omega(n/\log n)$.

In more detail, consider the language $L$ of all triples $\langle M,x,1^t \rangle$ such that $M$ halts on $x$ after at most $t$ steps. Suppose that this can be solved in time $f(n)$, where $n$ is the input length (which is $t + |M| + |x|$). Then you can construct a Turing machine which on input $\langle x,1^t \rangle$ determines whether $\langle x,x,1^t \rangle \in L$, if so runs into an infinite loop, otherwise halts. When run on itself as input, this machine either halts in time $f(t + O(1)) + O(1)$ or never halts. Hence if $f(t + O(1)) + O(1) \leq t$, we reach a contradiction. This shows that $f$ has to essentially be at list linear.


When should I learn artificial intelligence?

You will need some discrete mathematics. Graphs, trees, and so forth. These are the structures underlying AI.

You will need some programming skills, especially in languages such as Prolog and LISP.
A lot of AI systems are programmed in these languages.

You will need some logic. Propositional and predicate calculus. Their syntax and semantics. Perhaps some modal logic. This will form the basis for learning about knowledge representation, which is at the basis of AI.

During the first two years of a regular computer science degree you usually obtain enough background to start studying AI .

But there is no limit to how complex AI can be. To get deeper into it, you'll need statistics, calculus, matrix algebra, and probably much more. Statistical learning theory (or more simply machine learning) depends on these areas.

My advice. Buy a book on Artificial Intelligence to read in your own time.
A good one is Artificial Intelligence: A Modern Approach by
Stuart Russell and Peter Norvig. Whenever you don't understand something, try to work out what background knowledge you are lacking. Then fill those gaps.


Weak hashing function for memorable IPv6 addresses

Take the IP address and a wordlist. Then turn the IP address into a list of words from the wordlist based on the digits of the address, base {length of wordlist}.

So, for instance, taking the diceware wordlist and your example, I get: 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 -> mew hades cup viii 72 grit photo pick raid dey (or potentially the other way around, and/or padded on the other end).

Note this isn't lossy. Although you can relatively easily apply any lossy techniques to this. You may just wish to truncate the IP address, or only select every second bit or something before running it through this mapping.


How to prove that a system is real-time?

It depends on your definition of "real-time system".  A standard definition is: a system is real-time if it will respond within $T$ seconds, with probability at least $P$.  Here you need to fill in the parameters $T,P$; e.g., it might be $T = 1$ millisecond and $P = 0.999$.

How do you prove that this condition is met?  One way is to find a way to generate random workloads, from the same distribution as the system will be exposed to in practice, and count how often the system meets the deadline and how often it doesn't.  Another way is to prove a theorem (e.g., with formal methods) about the maximum time it might take to respond; see the literature on worst-case execution time analysis.  The latter might be particularly challenging in many cases.

There's an entire literature on this topic, that you can read more about.


Your problem, as stated, is already the independent set problem, as defined e.g. on Wikipedia.
A very similar NP-Complete problem is Clique, which is part of Karp's original 21 NP-complete problems, where, given a graph $G$ and an integer $k$, you try to find a complete subgraph of size $k$. It is easy to see that looking for an independent set in a graph is the same as looking for a clique in its complement graph.
In Karp's paper one can also find a straightforward reduction from SAT to Clique, and the reduction does not depend on whether the graph is connected or not. Hence it does not matter whether your graph is connected or disconnected.


Proof of equivalence of parse-trees and derivations

Theorem.
Let $G = (V, T, P, S)$ be a Context-free Grammar. Then $\forall A \in V, A \rightarrow^* \alpha \Leftrightarrow \exists$ a parse-tree $T'$ rooted at node $A$ with yield $\alpha \in (V \cup T)^*$.

Meanings of symbols:

$V$ is the set of non-terminals
$T$ is the set of terminals
$P$ is the set of productions
$S \in V$ is a designated start symbol.

A parse-tree $T'$ for a derivation is defined as follows:

The root is labeled with a symbol $\in V$
If $T'$ has a node labeled $A$ whose children are labeled $X_1, X_2, \dots, X_n$ such that $X_i$ is to the left of $X_j$ for all $i \lt j$, then $A \rightarrow X_1X_2\dots X_n$ is a production $\in P$.

proof. We prove $\forall A \in V, A \rightarrow^* \alpha \Rightarrow\exists$ a parse-tree $T'$ rooted at $A$ with yield $\alpha \in (V \cup T)^*$ and vice-versa. We will refer to a node with label $L$ as node $L$.

First we show the ($\Leftarrow$) part.

Assume there is a parse-tree $T'$ rooted at $A$ with yield $\alpha$. If the tree has $1$ internal node, then $A \rightarrow \alpha$ is a production in $P$ (by definition of a parse-tree). Since $A \rightarrow \alpha \Rightarrow A \rightarrow^* \alpha$, we are done.

Assume that the ($\Leftarrow$) part holds for all parse-trees with fewer than $n$ internal nodes (induction hypothesis). If the parse-tree has $n \gt 1$ internal nodes, let $X_i, i = 1, 2, \dots, m$ (be it a non-terminal or a terminal) denote the label of the $i^{th}$ child of the root-node $A$. Each of the $X_i$ nodes has fewer than $n$ nodes. By the induction hypothesis, each of the $X_i$ nodes is the root of a parse-tree with yield $x_i$. Knowing that all the descendants of $X_i$ are to the left of all of the descendants of $X_j$ for all $i < j$, we can write $\alpha = x_1x_2\dots x_m$. $A \rightarrow X_1X_2\dots X_m$ is a production in $P$ and a derivation looks like:  $A \rightarrow X_1X_2\dots X_m \rightarrow^* x_1X_2\dots X_m \rightarrow^* \dots \rightarrow^* x_1x2\dots x_m = \alpha$.

Now we show the ($\Rightarrow$) part.

Assume $A \rightarrow^* \alpha$ for some $A \in V$. If $A \rightarrow \alpha$, then the tree in Fig. 1 is a parse-tree with yield $\alpha$ and we are done.

Assume that the ($\Rightarrow$) part holds for all derivations with fewer than $n$ steps (induction hypothesis). If $A \rightarrow^* \alpha$ is a derivation with $n$ steps, let $A \rightarrow X_1X_2\dots X_n$ be the first step in the derivation-chain. Let $V' = {X_1, X_2, \dots, X_n} \cap V$. Each of the elements of $V'$ derives a sub-string of $\alpha$ with fewer than $n$ steps. By the induction hypothesis, there is a parse-tree rooted at node $V'_i$ with yield $v'_i$. We form a parse tree rooted at $A$ with yield $\alpha$ as follows:

Add a root-node labeled with $A$
Add a link between $A$ and every node labeled with a symbol $\in V'$
Add a link between $A$ and every node labeled with a symbol $\in \{X_1, X_2, \dots, X_n\} \cap T$

This ends the proof.


Why is "accepted by Turing Machine with even number of states" a trivial property?

All recognisable languages are recognised by a TM with an even number of states, so the property is trivial.

If a language is recognisable, there is (by definition) a TM that recognises it. If it happens to have an even number of states, then you're done. If it has an odd number of states, add another state that doesn't do anything (or duplicates an existing state), then you have a new TM with an even number of states, and are done.


The context-free languages are not closed under complement. For example, $\overline{\{a^nb^nc^n : n \geq 0\}}$ is context-free, but its complement isn't.


Benefit of Petri Net Transition as Separate Object

The state transition graph underlying a Petri Net model is called the Reachability Graph. Yes, it exists, and it is the foundation of Petri Net semantics. However, it is possible to define simple, easily understandable Petri Net models that have reachability graphs of a size and structure that no human could make sense of. They might also be graphs with an infinite number of states.

It's similar to programming languages: every conceivable algorithm or program could be written in assembly language. But there are dozens, if not hundreds, of higher level programming languages that make it easier, simpler, and faster for humans to write and understand programs, to express the algorithms and the processing they need to implement. And then a compiler or interpreter turns the high-level program into a stream of processor instructions.

Petri Nets are meant as a way for humans to create meaningful, understandable models, without drilling down to individual states and transitions. Then Petri Net tools handle the simulation and/or analysis of the models.


Ideal number of participants for evaluation of development approach / software architecture

"Is there any scientific research or paper that suggests a certain number of evaluators for such a rather theoretical approach?"

There is a statistical method to calculate the correct sample size for an experiment.
This method is called a "power analysis" [1]. It calculates the minimum sample size needed to verify that an experiment's results are statistically significant.  This approach assumes that you have at least two groups.  A control group and an experimental group (i.e. control group uses the platform without your modifications, experimental group uses the platform with your modifications).

Thus, while there is a scientific process to calculate the correct sample size this approach is probably overkill for your study. Nielsen [2] states that heuristic evaluation is just a "cheap and quick" method for easy evaluation. As such, I believe you can justify a sample size of 5 by citing Nielsen.  However, if you do want to standardize your evaluation process and use a statistical approach I encourage you to look into power analysis.

You may be interested in this online tool for calculating power.

http://en.wikipedia.org/wiki/Statistical_power
http://www.nngroup.com/topic/heuristic-evaluation/


Are there some real-world optimization problems with very cheap objective functions?

If you don't consider the Traveling Salesman Problem to be "real-world" enough, maybe take a look at its close cousin the Vehicle Routing Problem (VRP). In particular, consider all the variations of VRP, many of which clearly have their origins in real-world situations (e.g.: time windows, backhauls, etc...). This survey (pdf) by Eksioglu et al. details many of these variations. And, as far as I can tell, VRP objective functions are not much more difficult to evaluate than those of TSPs.


Handling untrusted string input in printf in C

Since you asked on a computer science site, I'll give you a computer science answer. This might not be the most directly helpful from a programmer's point of view, though understanding this will definitely make you a better programmer.

The first argument to the printf function is a char *, i.e. a pointer to a byte¹. However, not all pointers to bytes are valid arguments to printf. The type system of C is not precise enough to express the type of the argument.

It's well-known that the first argument to printf must be a string. A string, in C, is a zone of memory (i.e. a region of bytes with contiguous addresses) which is not empty and where the last byte has the value 0. The string is designated through a pointer to its first byte. A string is isomorphic to an array of nonzero bytes.

A null pointer, or a pointer value that does not point to a valid object, are not valid first arguments to printf. C does not offer any guarantees when a program is invalid. If you pass an invalid argument to printf (or any other function), **the behavior is undefined--. That means the behavior of the program is at the whim of the implementation. It may cause your program to crash. Or to print nonsense. Or to make demons fly out of your nose². Or to execute some code which was specially chosen by the attacker who specified the first argument — in a security context, undefined behavior is typically whatever the attacker has decided it to be (that's what exploit writing is all about).

Not all strings are valid first arguments to printf. The most obvious restriction is that the string must be a format string. In a format string, the character³ % has a special meaning. For example, "%B" and "%0s" are not valid format strings in standard C. A string which isn't a well-formed format string isn't a valid first argument to printf.

It gets worse. Not all valid format strings are valid first arguments to printf. For example, the call printf("%s") is not well-formed: the format specifier %s consumes an argument, but there is none; the behavior of this call is undefined. In practice, in many implementations, printf will grab the value at the top of the stack and assume that it's a valid string; this may crash, print out confidential information, print out data that whatever is reading the output of the program won't understand, or any combination thereof.

The type of printf is really a dependent type: the number and type of subsequent arguments depends on the value of the first argument. This is very far beyond the capabilities of C's type system⁴. Like just about everywhere in C, the onus is on the programmer to write a correct program.

Conceptually, a call like printf(buffer) is wrong, because a buffer is an arbitrary string, whereas the argument to printf must be a printf format. All printf formats are strings (the type of formats is a subtype of the type of strings), but not all strings are printf formats. The call printf(buffer) is only valid if the string buffer happens to be a printf format with zero arguments. This means no format specified other than %%, in standard C; in other words, the valid values of buffer in printf(buffer) are the strings where every % is followed by another %.

If you have a string lying around, how do you know whether it's a valid printf format? If the string is a literal written syntactically within the printf argument list, then it is very easy for the programmer or a code reviewer to check whether the format is correct. Any good compiler can check the format string and report a compilation error if it is incorrect, too. If the string comes from a variable, verifying that it is correct is a lot more difficult.

The correctness of the printf call becomes more and more difficult to ascertain as the value of the format string is specified further and further from the point of use. This is where trust comes into play. In order for the program to behave as desired, the format string must be valid for the call. When you claim that your program behaves as desired, you rely on the format string being valid — in other words, you trust the format string. This is only valid if you trust the entity where the format string originates to provide a valid format string. If the format string comes from a source that is external to your program, that source is often untrusted. Even when it is trusted, tracing that source is a heavy burden, which makes relying on such an external source bad engineering practice.

As a parting piece, why is printf("%s", buffer) valid? The %s format specifier expects a string, so this call is valid if and only if buffer is a valid string. This is as safe as it gets in C.

¹  It's in fact a little more complicated, because char isn't exactly a byte, but for our purposes here it's close enough.
²  Sadly, many computers lack the hardware device that would make this very educational behavior possible.
³  By “character”, I mean the byte whose interpretation in the execution character set is the % (percent) character.
⁴  There are languages where printf is provided and has a type that describes its behavior. The obvious way to do it is in dynamically typed languages like Lisp, Perl, etc., where the behavior of printf if the arguments are not well-formed is to signal an error. OCaml typechecks printf statically; it requires that the format string be known at the compile time, as the compiler parses it and deduces the type of the remaining arguments.


Yes, the number of final states in a DFA is at least the number of final states in its minimal DFA. Your proof is correct at some level of formality.

Intuitively, as you have noticed, any DFA for $L$ can be reduced to the minimal DFA for $L$ by merging states, which must merge any final states to a final state.

Here is how to make your proof mathematically more formal. Let $L$ be a language over $\Sigma$ and $D=(Q,\Sigma,\delta,s,F)$ be a DFA that accepts $L$. Let $M$ be the set of Myhill-Nerode equivalence classes with respect to $L$.

Define a map $m:Q\to M$ such that $m(q)=[w]$, where $w$ is any input that will drive $D$ to state $q$ and $[w]$ is the Myhill-Nerode equivalence class that contains $w$. We can verify that $m$ is well-defined, i.e., $[w_1]=[w_2]$ if both $w_1$ and $w_2$ drive $D$ to $q$.

We can verify or recall the following claims, thus completing this proof.

$m$ maps a final state in $D$ to a Myhill-Nerode equivalence class that contains a word in $L$.
all final states in the minimal DFA of $L$ are in one-to-one correspondence to all Myhill-Nerode equivalence classes that contain a word in $L$.

Here is a simple related exercise.

Exercise. The number of non-final states in a DFA is at least the number of non-final states in its minimal DFA.


Separate all leaves of a weighted tree with minimum weight cuts

For each node $v$ with height 1 (all its children are leaves): If $v$ has degree $d$ and $d - 1$ children, then the $d-2$ smallest edges are added to the cut. These cuts are required to separate the children of $v$ from each other. Now, all but one child (leaf) of $v$ has been separated from the rest of the tree.

Now consider all the nodes $v$ with height 2.  Each of these nodes with degree $d$ has a single parent edge (assuming that $v$ is not the root), and $d - 1$ paths of length at most two connecting it to the leaves in its subtree. We must remove the minimum edge from exactly $d - 2$ of these paths in order to disconnect these leaves from each other. Add these edges to the cut. Now all but one leaf in $v$'s subtree has been separated from the rest of the tree.  This leaf is connected to the parent of $v$ and the rest of the tree by a path of length at most $3$. Later on, we will be required to remove at most one edge on this path, so we don't need to track all edges, just the one of minimum weight.

Now consider all nodes $v$ with height $h$. Each of these nodes with $d - 1$ children has exactly $d - 1$ leaves connected in its subtree. Each of these leaves are connected to $v$ by a path of length at most $h$, but have also stored the minimum weight edge on this path. We must cut the smallest $d - 2$ edges in order to separate these leaves from each other. The remaining leaf is connected to the rest of the tree via a path of length at most $h + 1$, and in constant time we store its new minimum weight edge by comparing the old minimum with the weight of the edge (v, v.parent).

By working through the nodes in height order, we maintain the invariants that:

In each subtree, we have selected the minimum cut to separate the leaves in that subtree.
Each subtree has exactly 1 leaf connected to the root of the subtree.
Each subtree maintains the minimum weight edge on the path to that leaf.
Each subtree with $k$ leaves has selected exactly $k-1$ edges for its cut.
Each subtree is processed in $O(d)$ time, where $d$ is the degree of the root of the subtree.

Correctness and a running time of $O(n)$ follow from these invariants.


Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation?

I see two ways of interpreting this question, but the answer is essentially trivial either way.

Interpretation 1: Can every hypercomputation model decide some language that cannot be decided by a Turing machine?

Yes, because that is the definition of a hypercomputation model.

A caveat: Technically, you could have a hypercomputation model that (as Wikipedia puts it) "can provide outputs that are not Turing-computable", yet cannot actually accept any nonrecursive language according to the definition of language acceptance for the model. This is because accepting a language is not the same thing as computing a function. This would probably require a contrived definition of language acceptance, though. For example, take any standard hypercomputation model and say that the acceptance criterion is that the machine rejects on all inputs.

Interpretation 2: Can some hypercomputation model decide every language that cannot be decided by a Turing machine?

No for any reasonable definition of a "model of computation", because the set $\mathrm{ALL} \setminus \mathrm{R}$ of all languages not decidable by a Turing machine is an uncountable set. So for almost every undecidable language, there is no way to write down a program that decides that language, no matter how powerful your model of computation is, as long as you require programs to be written using a finite number of symbols.


the corresponding grammar you gave would accept aaaabcbc. A better grammar for this problem would be

$X \rightarrow aXc$

$X \rightarrow aYb$

$X \rightarrow \lambda$

$Y \rightarrow aYb$

$Y \rightarrow \lambda$

where $\lambda$ is empty string.


Get every possible (connected) subgraph containing x number of nodes

A standard brute-force method should suffice: enumerate all ${50 \choose 4}$ ways to choose 4 out of the 50 states, and for each such combination, check whether it meets your requirements.  There are only about 230,000 combinations to check, so this should run in a fraction of a second on a computer.

If you wanted to optimize it, there are various methods, such as choosing a state $u$, then choosing another state $v$ that is a neighbor of $u$, then choosing another state $w$ that is a neighbor of $u$ or $v$, then finally one more state $x$ that is a neighbor of one of $u,v,w$, and then checking whether that meets your conditions.  This would be faster.  But why bother?  It's hardly worth spending an extra hour or two programming a complicated algorithm to spend a fraction of a second of CPU time.


Difference between regular language and context free language

No, those are not quite correct.

For any alphabet $\Sigma$, the language $\Sigma^*$ is regular. The set difference between that and any CFG with the same alphabet is the complement of the CFG, and CFGs are not closed with respect to complement. So your first claim is incorrect.

However, CFGs are closed with repect to intersection with a regular language and regular languages are closed with respect to complement. Thus, your second claim is correct.


Every finite language is recursive.

Every language can be written as an infinite union of finite languages.

Some language isn't recursive.


Algorithm for estimating lossless compression factor

In general the only way to know what the compression factor with a particular compression method is to compress the data using that compression method and see what the compression ratio is.

Some compression algorithms have different levels of compression (e.g., 0-9), which allow the algorithm to spend a lot more CPU time to try to get a bit better compression.  You might be able to use the compression factor at a lower compression level as a predictor of the compression factor at a higher level, though this won't be perfect.


Theory of Computation, as practiced in the US, focuses mainly on two areas: algorithms and complexity. For algorithms, the standard textbook is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein, also known by its acronym CLRS. For complexity, there's the advanced textbook Computational Complexity: A Modern Approach, but it might be too much for a beginner.


No. of disk blocks writes required for writing the file

The correct answer is: greater or equal to K/D, depending on the fact that K can be a multiple of D or not. So, the answer is actually c), which differs from the other three answers.

Note that if there were an answer “ceil(K/D)”, that would have been the correct answer.


Quicksort doesn't swap the pivot into its correct position in that way, but it lies on the hypothesis that each recursive call sorts the sub-array and then merging sorted sub-arrays would provide a completely sorted array:

let $V$ be the array to sort
$pivot \leftarrow pick()$ picks a pivot, in your case it's always the first element in $V$
let $V_{\lt}$ be a list $s.t. \forall a \in V_{\lt} \  a \in V \ \wedge \ a \lt pivot$
let $V_{=}$ be a list $s.t. \forall a \in V_{=} \  a \in V \ \wedge \ a = pivot$
let $V_{\gt}$ be a list $s.t. \forall a \in V_{\gt} \  a \in V \ \wedge \ a \gt pivot$

Quicksort then proceeds recursively calling itself on $V_{\lt}$ and $V_{\gt}$, thus assuming to get those two back with their values sorted.

The final step is then to return the concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$, in this order.

Providing a numerical example:

$V = [17, -10, 7, 19, 21, 23, -13, 31, 59]$

Steps:

Initial run

$pivot = 17$

$V_{\lt} = [-10, 7, -13] $

$V_{=} = [17] $

$V_{\gt} = [19, 21, 23, 31, 59] $
Recursion on $V_{\lt} = [-10, 7, -13] $

$pivot = -10$

$V_{\lt} = [-13] $

$V_{=} = [-10] $

$V_{\gt} = [7] $

skips recursion on $V_{\lt}$ and $V_{\gt}$ since they're of size 1, thus already sorted

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[-13, -10, 7]$
Recursion on $V_{\gt} = [19, 21, 23, 31, 59] $

$pivot = 19$

$V_{\lt} = [] $

$V_{=} = [19] $

$V_{\gt} = [21, 23, 31, 59] $
Recursion on $V_{\gt} = [21, 23, 31, 59] $

$pivot = 21$

$V_{\lt} = [] $

$V_{=} = [21] $

$V_{\gt} = [23, 31, 59] $
Recursion on $V_{\gt} = [23, 31, 59] $

$pivot = 23$

$V_{\lt} = [] $

$V_{=} = [23] $

$V_{\gt} = [31, 59] $
Recursion on $V_{\gt} = [31, 59] $

$pivot = 31$

$V_{\lt} = [] $

$V_{=} = [31] $

$V_{\gt} = [59] $

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[31, 59]$
Back from recursion in 5.

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[23, 31, 59]$
Back from recursion in 4.

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[21, 23, 31, 59]$
Back from recursion in 3.

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[19, 21, 23, 31, 59]$
Back from recursion in 2.

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[-13, -10, 7, 21, 23, 31, 59]$

As you can see, from the step 3 and onwards, the chosen pivot isn't an optimal one, since there only are elements at its right, preventing the algorithm to run in optimal time of $\mathcal{O}(n log_2 n)$

EDIT: following Kai's comment, I fixed the definitions of $V_{\lt}$, $V_{=}$ and $V_{\gt}$. I also acknowledge this is the simpler and less efficient Lomuto's partition.


Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

Yes, it's possible. You can simulate the program by using an interpreter for the language it's written in. Now, the program (the interpreter) is fixed and the thing that used to be a self-modifying program is now the interpreter's data.

In particular, you could perfectly well have a universal Turing machine that allowed the TM it's simulating to modify its own description.  (The description of the simulated machine, I mean; not the UTM.)


Priority Queue - When Prioritizing Take Place?

The underlying data structure is usually a heap, and the elements are partially ordered when it's initialized. At that point, the highest priority element is at the root of the heap ready to be popped next. When a new element is added to the heap it is added at the end and partial ordering is done bottom up; and when an element is removed the last element moved to the root and the partial ordering is done top down. So when implemented using a heap, the prioritization is maintained by partial ordering when initialized and when an element is added or removed.


Clarification with Kuhn-Munkres/Hungarian Algorithm

You are right that $G_{l'}$ is not necessarily a superset of $G_l$. However, you can still prove that the algorithm runs in strongly polynomial time. You have the following invariants:

all edges in $M$ remain edges of $G_{l'}$
we don't remove vertices from $S$ and $T$ until we increase the size of the matching $M$, at which point $S$ and $T$ are reset (step 1); so the size of $S$ and $T$ is monotonically increasing until the size of $M$ is increased by 1
after updating the labels to $l'$, the size of $T$ is increased by at least 1 in the next step

What can you conclude from this? The size of the matching $M$ never decreases. At each iteration we either increase the size of $T$, or we update the labels, which will cause us to increase the size of $T$ in the next iteration. So after $2n$ iterations, the size of $T$ will be $n$. Since $T$ cannot grow anymore, we will have to increase the size of $M$. But the size of $M$ is at most $n$, so the algorithm will finish after at most $O(n^2)$ iterations. An iteration can be executed in time $O(m)$, so the total running time is bounded by $O(n^2m)$.

BTW the sets $S$ and $T$ are a bit mysterious in this description of the algorithm. Here is how we usually think about them. Orient all edges in $G_l$ as follows: the edges in $M$ go from $Y$ to $X$ and all other edges go from $X$ to $Y$. Then $x$ is an unmatched vertex, $T$ is computed to be the set of vertices in $Y$ reachable from $x$ by a directed path, and $S$ is the set of vertices in $X$ reachable from $x$ by a directed path. If $T$ contains an unmatched vertex, we have found an odd-length alternating path, and we can augment the matching (increase its size by reversing the direction of the edges along the path). Otherwise, we can change $l$ so that the size of $T$ increases.


number of comparisons in searching algorithms

When measuring comparisons, we usually only charge comparisons of elements of the array (more accurately, we charge comparisons for the datatype of array elements, but not of array indices). In the example of linear search, at each iteration you are comparing one element of the array to the input element being searched. So in total, you are making exactly $n$ comparisons in the worst case.

For binary search, at each step you are making a 3-way comparison between the middle element of the current segment of the array and the input element. The number of 3-way comparisons satisfies the recurrence $T(n) \leq T(\lceil \frac{n-1}{2} \rceil) + 1$, with base case $T(1) = 1$ (when $n = 1$, you are making a 2-way comparison). If you are only allowing 2-way comparisons, then each 3-way comparison has to be simulated using two 2-way comparisons, which might be the reason why the recurrence has $+2$ instead of $+1$.

For ternary search, you are making two 3-way comparisons (comparing the two middle thirds to the input element), which translates to four 2-way comparisons.

(A 2-way comparison is one which has two outcomes: for example, "$x = y$?" is a 2-way comparison, as is "$x \leq y$?". A 3-way comparison is one which has three outcomes: given two elements $x,y$, the comparison tells you whether $x < y$, or $x = y$, or $x > y$.)


$\eta$ conversion is not a mean to reduce a term to $\beta$-normal form, but a tool to show equivalence regarding the (future) application; to express that 2 terms “are the same function”; that they will reduce to the same term when applied to arbitrary term(s).

If you want to also do $\eta$ conversions, you can do it anytime because you still have the same term (application-wise) after performing it. Having $\eta$ conversion in the theory will not enrich nor deplete the theory regarding existence of $\beta$($\eta$)-normal forms.


Is there a program that will tell you the optimal algorithm for ANY problem if the problem is decidable?

As discussed in the comments, the question is not well-defined, since it's unclear what the input is.

However, under any reasonable assumption, no such program exists. One way to see this is through context-free languages: assume we can solve your problem even to the very restricted class of context-free languages. Thus, we have a program $P$ that given a grammar $G$, outputs a TM $M$ whose runtime is optimal (which is also not clearly defined, but let's ignore that for now) and recognizes the same language as $G$.

We can use this program $P$ in order to decide, given a CFG $G$, whether $L(G)=\Sigma^*$, by running $P$ and checking if it outputs a TM which is just a single accepting state (which is the only optimal TM under a reasonable optimality definition). Since this problem is undecidable, then $P$ cannot exist.


This notation is quite common in EE works:
If $S=S_1S_2S_3\cdots$ is a string (of some length), then

$S_i^j$ is the substring between places $i$ and $j$, that is, $S_i^j=S_i\cdots S_j$.

I didn't looks at the paper, but I guess that $[X]$ is a string (of expectations? of $X$ directly? this should be defined in the paper), and they just look at a prefix of length $T$ of that string.


If you mean by "the number of $x$ that have points" that the number of distinct values $x$ such that there is a point $(x, y)$ such that $y$ has not been removed is at most $X/2$, then your problem is extremely similar to Set Cover, which is $\mathbf{NP}$-complete.

Your problem would be the variant in which you ask for the minimum number of sets needed to cover half the elements of your universe. I would be very surprised if this was not $\mathbf{NP}$-complete. I'll think about it some more and update this if I think up a proof of $\mathbf{NP}$-completeness.


Because the set $\{1,x,\ldots,x^{n-1}\}$ is a base for polynomials with degree $<n$, by definition of base, no element in this set can can be expressed as a combination of others, i.e. no element can be “ignored”.

Therefore, we know that our algorithm needs to at least read all the coefficients corresponding to $n$ elements of the base, thus making at least $n$ steps.

On the other hand, you found that adding/subtracting polynomials can be simulated by element-wise adding/subtracting lists of their coefficients, which is $O(n)$, meaning it requires less than $c \cdot n$ steps for some constant $c$.

Now we know that your algorithm needs to make some number of steps that is between $n$ and $c\cdot n$, and as @Yuval pointed, this is $\Theta(n)$ time complexity.

(this is all for general case and I don’t know if there exists some special space of polynomials that can be represented more compactly, thus making it possible to add/subtract them faster, but also I think that you are in fact interested in a general case)


How to describe an algorithm whose input size diminishes by 1 for each iteration

On recursive algorithms, you need first to obtain the recurrence relation. Then you solve the recurrence to get the total time required by the algorithm.

Let $n$ be the input size. Let $f(n)$ be the time required in each recursive call. Let $b$ be the input size for the base case. A general recurrence relation might look like this

$$
T(n) = T(n-1) + f(n)  \quad \quad \textrm{if } n > b \\
T(n) = c \quad \quad  \quad \quad \quad \quad \quad \quad \;\ \textrm{if } n = b
$$
where $c$ typically is a constant (because typically the base case takes constant time).

So, you need to figure it out the function $f(n)$, which is specific for each algorithm. For example, if $f(n)=n$ (e.g. a simple pass on a array), and assuming $b=1$ and $c=1$ (it is not a problem to assume $c=1$ if you are working with assymptotic notation) then

$$
T(n) = T(n-1) + n  \quad \quad \textrm{if } n > 1 \\
T(n) = 1 \quad \quad  \quad \quad \quad \quad \quad  \textrm{if } n = 1
$$

Solving this recurrence, you have that $$T(n) = n + (n-1) + \ldots + 2 + 1 = \frac{n(n+1)}{2} = O(n^2)$$.


partial (and non deterministic) functions in dependently typed lambda calculus

It is possible to take a typed lambda calculus and add general recursion or fixed points. See for instance Plotkin's PCF, or HOFL in Winskel's formal semantics book.

In that way, one keeps the type system but introduces partiality. This is a very common approach for Turing complete typed programming languages.

Of course, now the logic associated to the calculus via Curry-Howard is no longer consistent, since every type is inhabited (by non terminating terms). This is not a serious problem for programming.

If wanted, in the type system one could distinguish between terms involving general recursion (which might not terminate), and terms involving no recursion or some known-to-be-terminating one, like (higher-order) primitive recursion. Note that this will not separate the programs between "halting" and "non-halting", which is undecidable, but only between "statically known to halt" and "statically unknown to halt -- they might or might not".

I have not thought much about that, but intuitively a non-termination monad would fit nicely in such type system. With a non-deterministic monad, one can also address non-deterministic functions.

A final comment: after reading the question, I am actually more concerned about the posted automaton-based example than termination. With dependent types, one can use the $\Pi$-type of a selection function (as the one which was posted), which given an automaton return one of the accepted strings (or a "empty-language" token). However, let's keep in mind that when a dependent type system checks a term against such $\Pi$-type, the term must contain the recipe to generate the string, as well as a proof that such string is accepted by the automaton. The posted question, in my view, seems to forget about that -- as if the type system could check any algorithm correct (in the sense of returning an accepted string). This is not possible.


DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$

In order to verify whether the string is of the form $1^ky$ with $y\in \{0,1\}^*$ and $|y|_1\le k$ you want to determine whether a symbol $1$ in the prefix belongs to the $1^k$ part, or starts $y$.

Now imagine $1^k \cdot 1y$ is of the correct form, i.e., $|1y|_1 \le k$, then certainly $1^{k+1}\cdot y$ is also correct, as $|y|_1< |1y|_1 \le k < (k+1)$.

So, keep reading $1$'s while possible.


Can Turing Machines solve non-decision problems?

Usually, Turing machines are explained to calculate functions $f:A \rightarrow B$, of which decision problems are a special case where $B = \mathbb{B}$.


How to deal with character set in regular expression?

Theoretically, NFA or RegEx minimization is PSPACE-complete [1]

Practically, you can throw as many optimizing features to your online regex visualizer websites as current websites do, as long as it does not consume all your server's resources.

[1] Minimizing nfa’s and regular expressions, Gregor Gramlich,, Georg Schnitger


Strassen's algorithm is for multiplying square matrices, not vectors. Your algorithm already runs in (asymptotically) optimal time $O(n)$ (where $n$ is the dimension of the vector), and also uses the optimal number of multiplications.


First some questions:

Can $k$ only take on 10 possible values?
From what you've said above, the measure of the 'quality' of a given value for $k$ would be an n-tuple e.g. $(accuracy,memory, time, storage)$, right?

So 'dynamically learning a value for $k$' involves learning a good choice based on $L$, the list of n-tuples for previous values of $k$.

Here are two very simple schemes:

If your problem is genuinely multi-objective, then you can always just pick the associated $k$ at random from the Pareto-front of $L$.

If your multiple objectives can be combined into a single quality value, then fit a differentiable curve (e.g. a polynomial) to these values, then symbolically determine the optimum of that curve and the associated value of $k$. Most computer algebra packages support the functionality for this, as does the Apache Commons Math library for Java.