Deciding which logical proposition is stronger I am studying propositional logic and I am trying to solve some exercise related to the following definition:

Given two logical propositions $\alpha$ and $\beta$, we say that $\alpha$ is stronger than $\beta$ if and only if $(\alpha \implies \beta)$ is a tautology. Determine which of the two propositions is stronger in the following cases:

1) True, False

2) True, True

3) False, False

I am a bit confused with this problem. I've seen that for True we always assign the value $1$ and for False, the value $0$. So, (True $\implies$ False) has always value $0$ (actually, there is one possibility) and (False $\implies$ True) has always value $1$ (there is also one possibility). This means that (False $\implies$ True) is a tautology, so False is stronger than True.

I am not sure if what I've said above is correct and I am lost in 2) and 3), I would appreciate some help. Thanks in advance.

The notion of strength of a proposition comes from its power to constrain the model. For instance the proposition $P1 : x = 2$ is stronger than $P2 : x \geq 2$ in Arithmetic. And in propositional notation this can be written as $P1 \Rightarrow P2 $.

The stronger the proposition the harder it usually is to prove. On the other hand, if proven it provides more corollaries.

For instance for a signature with 2 propositional symbols $P$ and $Q$ we have the following partial diagram for the Strength relation.

Now to your examples. $\textrm{False}$ happens to be an extreme case. It can never be satisfied. If you are using propositions to constrain your search space for an answer, then $\textrm{False}$ says: "Call off the search and start again". The other extreme is the proposition $\textrm{True}$. It is trivial. It gives absolutely no information on where to look for the answer.

Now we shall use this intuition to tackle your questions:

1) True, False

Since $\textrm{True}$ is a trivial constraint, you would not be able to derive anything non-trivial out of it, this certainly means that you would not be able to derive the extreme constraint $\textrm{False}$.

  $\not\vdash \textrm{True} \Rightarrow \textrm{False}$

2) True, True

The propositions have exactly the same strength, they are equivalent

  $\vdash \textrm{True} \Rightarrow \textrm{True}$

3) False, False

The propositions have exactly the same strength, they are equivalent

  $\vdash \textrm{False} \Rightarrow \textrm{False}$

And an extra case

4) False, True

  $\vdash \textrm{False} \Rightarrow \textrm{True}$

Note: there is an issue with saying that proposition $P$ is stronger than $Q$ if $P \Rightarrow Q$ is a tautology since intuitively the relation of being stronger is strict. It would better align with the intuition if we were to say that proposition $P$ is stronger than $Q$ or of equal strength if and only if $P\Rightarrow Q$.


How to efficiently use an AVL tree to store partial sums? Let $a_{1} , ... , a_{m} $ be real numbers $\geq 1$, where $m$ is at least 1. I am supposed to store them in an augmented AVL structure with the following operations:

-PartialSum (i): Return the $i_{th}$ partial sum.

-Change (i, y): Change the $a_{i}$ element for y.

I need this structure to retain the AVL properties and both of these functions to be in $O(logn)$. The problem is that my approach doesn't let me have that asymptotic bound on CHANGE.

My approach goes like this: Let i be the key, and also store the relative $i_{th}$ partial sum in each node, the value for a as well.

Thus each of my nodes has:

Key = The $i_{th}$ element of the series input.
Sum = The $i_{th}$ partial sum so far.
Val = The value of $a_{i}$ for this node.

By doing that, the operation PartialSum will be identical to Search, thus being in $O(logn)$.

Unfortunately my approach doesn't work so well with change. By storing the partial sums in every node, if a lower node changes, all of the tree's sums are to be recomputed, being in $O(n)$.

I am trying to take a different approach but I'm confused. Can someone HINT me here?

Instead of storing the whole $i_{th}$ sum in each node, just store the partial sum of the left sub tree.


Solving recurrence equation $T(n)=T(n^{2/3})+17$ How can the following recurrence equation be solved by one of three main ways:

$$T(n)=T(n^{2/3})+17$$

I have tried solving it by the iteration way. However it does not work for me since I can't find the equation with $i$, i.e the generic equation.

This post answers the original version of the question, where the recurrence relation is

$$T(n)=T\left(\frac{n^2}{3}\right)+17$$

The recurrence relation is somewhat unconventional. Here is an outline to solve it.

Suppose $n\ge 6$. Let $n=3\cdot2^{2^{m}}$, where $m=\log_2(\log_2\frac n3)\ge0$.

$$\begin{align}
T(n)
&=T\left(3\cdot2^{2^{m}}\right)
 =T\left(\sqrt{3\cdot\left(3\cdot2^{2^{m}}\right)}\right)-17\\
&=T\left(3\cdot2^{2^{m-1}}\right)-17
 =T\left(\sqrt{3\cdot3\left(\cdot2^{2^{m-1}}\right)}\right)-2\cdot17\\
&=T\left(3\cdot2^{2^{m-2}}\right)-2\cdot17
 =T\left(\sqrt{3\cdot\left(3\cdot2^{2^{m-2}}\right)}\right)-3\cdot17\\
&=\cdots\\
&=T\left(3\cdot2^{2^{m-\lceil m\rceil}}\ \right)-\lceil m \rceil\cdot 17
\end{align}$$

Since $-1\lt m-\lceil m\rceil\le0$, $3\sqrt2\lt3\cdot2^{2^{m-\lceil m\rceil}}\le6.$ So
$T(n)\sim -17\log_2(\log_2 n)$ when $n$ goes to $\infty$.

Here are two related exercises.

Exercise 1. What is the recurrence relation for function $S$ such that $S(n)=T(3n)$?

Exercise 2. What is the asymptotic behavior of $T(n)$ if $n$ goes to 3 from above, assuming $T$ is continuous?


deadlock caused by a cyle of locks ? unprobable event causing it or just a false intuition Thanks a lot for your help.

I want to understand what really causes what I suppose to be a deadlock:

I have standards objects, let's call it 'Words' that contains 3 letters and a key; (it doesn t really matter for my problem)

I have a container (list) of Couples, where a Couple simply is: 2 Words and 1 couple-Key.

I have a function that is suppose to do some calculation on the list of Couples,  it might modify the letters and the key during the calculation , but when the calculation is finish we can stock the result and reset it to the initial values.

Considering a code that uses a parallel for loop to get the results of all my couples. This uses a lock on the first word and then a lock on the second word before calling the getResult() function, why could a deadlock happen ?

My first idea was that if we have :

Couple 1 : A B

Couple 2 : B C

Couple 3 : C D

Couple 4 : D A

Couple 5 : A E.

If a thread takes the Couple 5, the thread taking the couple 4 will lock D and wait, etc... to Couple 2.

My intuition is that, someway deadlock might occur if a cycle pattern appears in my list of Couples. On the other hand, I am unable to build an example that explains a deadlock appearance without considering one of these event:

simultaneously 2 different thread have the Couples A B and B A, and each thread lock the other word at the same moment (quite unprobable to me).
a thread takes the priority to a former one (example:well I can't find any, finally I thinks it s equivalent to simultaneously 2 different thread have the Couples A B and B A, and each thread lock the other word at the same moment. It's just that, considering a big cycle, the probability that it happends is as high as the proportion of time required for a calculation over the number of threads.

Am i right with my analysis ?

If the cause of the eventual deadlock is not due to the "simultaneously " event, I'd be glad to know what causes it, or happy if more precision to deadlock probability appearances depending on number of threads or length of cycles etc... are discussed .

Actually, I kind of have 10^5 Couples 10^4 Words.

Thanks,

Guillaume

If a thread takes the Couple 5, the thread taking the couple 4 will lock D and wait, etc... to Couple 2.

Couple 1 tries to start and is waiting on A, couple 4 tries to start but is also waiting on A.

After couple 5 finishes one of the waiting couples will be able to lock A. If it is couple 1 then it will need to lock B before it can continue, however that is held by couple 2 and that is waiting on couple 2 which is waiting on couple 3 etc. until couple 4 which is now waiting on couple 1. There is no way to make progress $\implies$ deadlock.

It's important to keep in mind that between locking one word and locking the next a process can be interrupted or another can simple be faster and lock the second word.

You can avoid the lock by always locking the words in alphabetical order, that way couple 4 will lock A before it will try to lock D and couple 3 is then able to make forward progress and a deadlock is impossible.


The communication complexity of the distance between two strings Assume that Alice and Bob are respectively given two strings $x \in \{0,1\}^n$ and $y \in \{0,1\}^n$ such that the hamming distance between $x$ and $y$ is either $> n/2+\sqrt{n}$ or $< n/2-\sqrt{n}$.

Alice picks a set $A \subseteq \{1,...,n\}$ of size $k$ uniformly at random, and sends to Bob the set $\{(i,x_i) \mid i \in A\}$. Bob compares $x_i$ with $y_i$ for every $i \in A$ and accepts iff the majority of these indices agree. What is (asymptotically) the minimal $k$ for which this protocol succeeds (i.e. Bob accepts iff the distance is $< n/2-\sqrt{n}$) with probability at least $2/3$?

I guess that $k$ should be $\Omega(n)$, and that in order to show this we should bound the tail of the distribution (e.g. by using the Central limit theorem or something similar), but I don't see how this can be done.

Suppose that the Hamming distance between $x$ and $y$ is $n/2 - \sqrt{n}$. Suppose that you sample $m$ indices with replacement, and let $S$ be the number of indices on which $x$ and $y$ disagree. Then $S$ has expectation $mp$ and variance $mp(1-p)$, where $p = 1/2 - 1/\sqrt{n}$. According to the central limit theorem, for every fixed $t$ we have
$$
\Pr\left[ \frac{S-mp}{\sqrt{mp(1-p)}} \leq t \right] \longrightarrow \Pr[N(0,1) \leq t].
$$
We are interested in the event $S \leq m/2$, which is the same as $S - mp \leq m(1/2-p) = m/\sqrt{n}$, or equivalently
$$
\frac{S-m/p}{\sqrt{mp(1-p)}} \leq \frac{1/2-p}{\sqrt{p(1-p)}} \sqrt{m} \approx \sqrt{\frac{m}{4n}}.
$$
In particular, if $m = cn$ then (following a short argument) the probability of error tends to
$$
\Pr[N(0,1) > \sqrt{c/4}].
$$
For small enough $c$, this would be more than $1/3$, giving an $\Omega(n)$ lower bound for this version of your algorithm.

In your case, you choose indices without replacement. A similar argument works, using the central limit theorem for hypergeometric random variables, see for example Lahiri and Chatterjee, A Berry–Esseen theorem for hypergeometric random probabilities under minimal conditions, Theorem 2.1.


Why does a graph traversal algorithm is initialised with visited[s]←true I just had a course on algorithm, we just started to study graph traversal. the teacher wrote analgorithm but I think there is a mistake:
I'm a bit shy so I didn't asked her why so...

EXPLORE (s:sommet, D:dictionnary of the following vertexes or ahed of vertexes,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    Else LISTE←LISTE-{i}

I'm not sure about this line:

visited[s]←_true_;

What does that mean? shouldn't it be false? At the begining, we haven't visited any vertexes yet?

Suppose you don't mark the start vertex as visited. As you explore the graph, you might come back to the start and begin to explore from there again. Since the first thing you do is visit the start, it's marked as visited at the start of the algorithm.

However, the given algorithm clearly doesn't perform a graph traversal. It adds the start node to the list, then marks all its neighbours as visited, one at a time, then deletes the start node from the list, then terminates. The line

visited[j]←true;

should be

visited[j]←true; LIST←LIST+{j};


What algorithm is appropriate for a thermostat controlling the heating of a room with floor heating? I built my own thermostat that controls the boiler heater for the radiant floor heating in my house and I would like to develop / implement a smarter temperature control algorithm. What I am specifically interested in is the ability to predict when to turn on the heating so that a certain temperature is achieved according to a schedule.

Suppose I want the temperature at 7 am to be 22 degrees Celsius. During the night I want it to be at 18C. Currently, I set the schedule up so that the heating is started at 6 am but depending on how cold it is during the night, an hour may be too little and the temperature does not rise to 22C or it may be to much and the temperature overshoots. I would like an algorithm that would automatically calculate the appropriate time at which to start heating.

I keep searching online and most results are for industrial uses and/or for heating systems that can be modulated such as electrical heaters. The heating system in my house consists of a boiler that heats the water in the floor tubing and I cannot modulate the output, I can only tell it to start or to stop via a mechanical relay that opens or closes a solenoid valve. This, I believe, renders a PID algorithm inappropriate. Fuzzy logic and just PI control may be suitable but can they be made to work with varying set points?

Supervised machine learning is overkill for my needs and I don't want to spend weeks to train it.

What other options would I have?

Maybe approach it from a "BTU's needed over time" standpoint. I don't know the exact maths off the top of my head, but consider:

What is the temperature differential?
What is the heating capacity (BTU's) of the radiant flooring system?
How long does it take to start rendering 68% of that heat to the room?
What is the heating load of the room in BTU's?
How efficient is the heat generated?

Then do some math on these numbers. Something like...

$t_{hours}=\dfrac{(T_{end}-T_{start})\cdot H_{demand}}{H_{supply}}\cdot \mathrm{eff}^{-1} + t_{delay}$

So for an end temperature of 22°C and a start of 18°C, heat of 50kBTU, demand of 20kBTU, 90% efficiency, and 15 minutee delay:

$\begin{align*}t_{hours} &= \dfrac{(22°C-18°C)\cdot 20k_{demand}}{50k_{heat}}\cdot 0.90_{\mathrm{eff}}^{-1} + 0.25h_{delay}\\
&= \dfrac{80\mathrm{k}}{50\mathrm{k}}\cdot 1.\bar{1}+ 0.25\mathrm{h}\\
&= 2.02\bar{7}\mathrm{h}
\end{align*}
$

Some analysis and experimentation will be needed to arrive at realistic values but hopefully this is a start.


Is it possible to create a chatbot that doesn't fall into an infinite loop under some restrictions? Consider a chatbot that runs on a turing machine. It has some restrictions:

It must talk to itself 1 sentence at a time.
It is forced to use English words to reply. (so only around say 80 k different words to pick from)
A sentence cannot be longer than N words (say N=100)

Is it possible to create such a bot (computer program) such that it will not repeat itself over and over, i.e. fall into an infinite loop?

I think that yes, it's possible. For example the sequence: "Hello, how are you? > Good, and you? > Not so good, and you? > Good and you? > Good and you? > Good and you? > Not so good, and you? >..."

I could write the above as 10110111011110111110... where 1 represents "Good, and you?" and 0 represents "Not so good, and you?".

But a friend is telling me that the example does not work because "it's not a cycle, so it's not possible on a finite state machine".

Edit: I'm asked whether the TM can maintain state during inputs. My answer is "yes if a common household computer can, no otherwise."

Edit for the bounty: I'd like the answer to be clear on whether a common household computer can run such a program, i.e. a program that never cycles under the above restrictions.

Thus far, on one hand Anrej Bauer's answer explain that it's impossible. On the other hand, in the comments I am told by D.W. that "Or, to put it another way: yes, a common household computer can retain state if you invoke it in a way that allows retaining state; it can't retain state if you invoke it in a way that doesn't allow it to retain state." and by David Richerby that "Is the Turing machine allowed to maintain state between inputs? If so, you can implement your 10110111011110... sequence exactly as you describe.". Which would make the answer as "yes, it is possible even when the TM is a common household computer". This is why I am reluctant to accept the answer and bounty so far.

EDIT 2: To make the question well definied, I must pick whether I want the TM to retain state between inputs. Since it is possible to do so on a household computer with say Python as a programming language, I pick that yes, the TM can retain state between inputs.

If the computer can retain state between inputs (e.g., you're using an interactive Turing machine), then yes, you can avoid an infinite loop.

For instance, the machine can just have a counter that counts 1,2,3,4,5,...; it can then map the counter to a sentence.  When the counter is $i$, it can look up the $i$th bit of the binary expansion of pi; if this bit is even, it outputs "Not so good, and you?" and if it is odd, it outputs "Good, and you?".  Since the bits of pi never repeat, this will never repeat either.  There are other ways to do it as well; this is just one example.

To respond to the original version of the question: If invoke the Turing machine separately on each input string, then it will have no way to retain state across sentences.  In that case, no,  It's not possible.  By the pigeonhole principle, there will exist a loop.  The set of possible sentences is finite, so this will eventually enter a loop.

If you take any function $f:S \to S$ where $S$ is a finite set, and you pick a single starting point $x \in S$ and then compute the sequence $x,f(x),f(f(x)),\dots$, eventually some value must appear twice.  In particular, once you've looked at $n+1$ different values, each of which is selected from a set of size $n$, by the pigeonhole principle, there must be some value that appeared at least twice.  In other words, $f^i(x)=f^{i+r}(x)$ for some $i,r$.  This means that $f$ has entered a cycle: $f^{j+r}(x)=f^j(x)$ for all $j\ge i$.

Here $S$ represents the set of all sentences (there are finitely many of them), and $f$ represents the function computed by your chatbox (which accepts a single sentence on its input, and outputs a single sentence, and is deterministic).

Of course, with an appropriately constructed algorithm, it may take longer than the lifetime of the universe to enter a loop.  Nonetheless, mathematically, it will eventually loop.

Your specific example doesn't work: it can't be implemented by a deterministic function.  If on input "Good, and you?" it outputs "Not so good, and you?", then that's what it will always output on that input.  Thus, you can't have a Turing machine that on input "Good, and you?" will sometimes output "Not so good, and you?" and sometimes output "Good, and you?".  Code running on a Turing machine is deterministic and memoryless.


Constructing Tree (forest) from Ancestor function Question:

Suppose I have a

set of male people, and
a function isAncestor(person1,person2) that checks whether person1 is an ancestor of person2 in O(1) time. Eg, isAncestor(grandfather, grandson) would return true.

What are some fast algorithms for constructing a complete "family tree"  by using only this information? (or "family forest" as not everyone may be related to a single common ancestor).

Comment:

This is not homework or from a book. It is derived from some issues I'm having coupling an adaptive finite element code to some blackbox mesh generation software, boiled down to the core problem and expressed in an analogy that shares the same mathematical structure. Right now I have a brute-force $O(n^3)$ method that seems horribly inefficient.

Thank you for any help.

Results:

I've implemented Gilles suggestion in Matlab and tested it. Here is the pseudocode, code, and unit test script. I release it all to the public domain.

Pseudo-code:

function buildAncestorForest
    roots = empty list
    for each person p
        roots = graft(p, roots)

    subfunction new_roots = graft(q, old_roots)
        descendents = empty list
        nondescendents = empty list
        for each person t in old_roots
            if q is an ancestor of t
                append t to descendents
            else
                append t to nondescendents

        if descendents is still empty
            q_is_incomparable = true;
            for each person t in old_roots
                if t is an ancestor of q
                    new_roots = old_roots;
                    new children of t = graft(q, old children of t)
                    q_is_incomparable = false;
                    break for loop
            if (q_is_incomparable)
                new_roots = append q to old_roots;
        else
            new_roots = append q to nondescendents;
            for each person t in descendents
                children of q = graft(t, children of q);

Matlab code:

https://github.com/NickAlger/MeshADMM/blob/master/buildAncestorForest.m

Unit test script:

https://github.com/NickAlger/MeshADMM/blob/master/test_buildAncestorForest.m

Assumptions

We have a finite set $\mathscr{D}$ of persons and a relation $\prec$: $x \prec y$ means that $x$ is an ancestor of $y$. This relation has the following properties:

Transitivity: if $x \prec y$ and $y \prec z$ then $x \prec z$ (the ancestor of my ancestor is my ancestor).
Antisymmetry: if $x \prec y$ then $y \nprec x$ (I am not my ancestor's ancestor).
Chain: if $x \prec z$ and $y \prec z$ then either $x \prec y$ or $x = y$ or $y \prec x$ (my ancestors form an ordered chain).

Data structures

Let it be given a set data structure on which the following operations are defined:

empty set
add an element to a set
splitting a set according to a property: iterate over the elements, compute a property on each element, and build two subsets, the set of elements for which the property is true and the set for which the property is false. This operation is assumed to be linear in the size of the set.

We will also use a tree data structure, in which each node contains a person and the set of its children. If $t$ is a tree, write $t_R$ for the person at the root node and $t_C$ for the set of children. A forest is a set of trees.

Algorithm

We start with an empty forest and add persons one by one. At each step, the parent-child relationship in the forest is the parent-child relationship for the ancestor relation. We define a recursive function graft that inserts a tree into a forest.

Input of graft: a forest $F$, and a tree $s$ such that none of the elements of the tree is related to any of the persons in $F$. Let $x = s_R$.

First, check whether $x$ is the ancestor of any of the existing persons: split the set $F$ according to the property $x \prec t_R$ for $t \in F$. Let $C$ be the subset of $F$ consisting of descendants of $x$ (if the root of a tree is a descendant of $x$ then all elements are also descendants by transitivity), and $F'$ be the remaining subset. By antisymmetry, none of the persons in $C$ is an ancestor of $x$. None of the elements of $s_C$ are related to any of the persons in $C$ by assumption. Let $u$ be the tree where the root person is $x$ and the set of children of the root is $C \cup s_C$.

By the chain assumption, $x$ can have ancestors in at most one of the trees in $F'$. Iterate over the trees $t \in F'$, and determine which one if any has an ancestor of $x$ at its root (this is a splitting operation where one of the sets is guaranteed to contain at most one element).

Output of graft:

If no tree in $F'$ has an ancestor of $F'$ at the root, then add the new node to the remaining forest: return $F' \cup \{u\}$.
If there is a tree $t$ in $F'$ such that $t_R \prec s$, then we need to insert the new element with its descendants into that tree. Let $G = \text{graft}(t_C, u)$. Return $(F' \setminus \{t\}) \cup \{t'\}$ where $t'$ has $t_R$ at the root and $G$ for children.

Main algorithm: Start from an empty forest, and iteratively graft the persons in $\mathscr{D}$ (grafting a person means grafting the tree with this person at the root and no children).

Correctness

From the remarks of this algorithm, it should be easy to prove that the recursive calls to graft are valid (all relatives of the nodes in the tree being inserted are inside that tree), and that $x$ is an ancestor of $y$ in the tree iff $x \prec y$.

Complexity

$\textrm{graft}(F,t)$ performs at most $2 n$ ancestor tests, where $n$ is the number of persons in $F$: one test per root of $F$, one test per root that is not a descendant of the new node, and tests performed by the recursive call if any which applies to a subset of $F$ not including any of its roots. The complexity of other operations is linear in the number of ancestor tests performed.

Therefore the forest construction algorithm performs at most $2 + 4 + 6 + \ldots + 2(n-1) = n (n-1)$ ancestor tests where $n$ is the total number of persons. In fact, it is easy to see that it never performs the same test twice. The overall complexity is therefore $O(n^2)$.

In the worst case, all possible $n (n-1)$ tests are performed. This happens when no two persons are related, and it is unavoidable in this case.


Is there any practical application for arrays that contain themselves? I'm reading the introduction to Godel, Escher, Bach and and there's heavy discussion of mathematical sets which contain themselves. Being a far better programmer than mathematician, I put it into terms I'm more comfortable with and started to think about arrays which contain/reference themselves.

I know that recursion is a very powerful concept in CS but that it's typically manifested through functions which call themselves. I see recursive functions in algorithms all the time, but I've never before run across an array that has itself as an element. I was just wondering if there's any particular "usefulness" or practical application for arrays which contain themselves (as there is for functions which call themselves).

If you represent a (directed) graph in an adjacency "list" representation, i.e. each node has an array of (pointers to) its immediate successors, then any cyclic graph would arguably be an example of an array that "contains" (really references) itself. In practice, the "object graph" of references between the objects in a program will often be an example of this albeit not quite so cleanly

Indeed, for non-well-founded set theories with an anti-foundation axioms stating that sets can contain themselves, cyclic graph models are quite natural.


Regex to NFA to complement So I've found out that a regular expression $n$ symbols long converts to an NFA with $O(n)$ states, it is linear.

Now to go from that NFA to the complement of the NFA, since I can't just flip accept and reject states, this means turning the NFA into a DFA.

If $n$ is the number of states in the NFA, the DFA simulating the NFA can have $2^n$ states.

So would the process of regex to NFA to complement of the NFA be $O(2^n)$?

Trying to figure out what big-O notation it would be.

No.  As you said, the NFA can have $m=O(n)$ states, and the DFA can have as many as $2^m$ states, so the DFA can have as many $2^{O(n)}$ states.  Consequently, converting a regexp to a NFA and then complementing the NFA can yield an automaton with $2^{O(n)}$ states.  $2^{O(n)}$ is larger than $O(2^n)$: notice the difference between $2^{cn}$ vs $c \cdot 2^n$.


Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol? Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol? Say f is the transition function, why does having

f(qi, 1, 0)       -> (qj, 0)
f(qi, epsilon, 0) -> (qj, 0)

cause nondeterminism?

I would understand that if I had

f(qi, 1, 0) -> (qj, 0)
f(qi, 1, 0) -> (qz, 0)

it would cause nondeterminism, because looking at the same input symbol I can choose to move to either qj or qz, that's nondeterminism to me. However the former doesn't make sense at all... This is what Michael Sipser says in his book.

Nondeterminism, means the machine has a choice. In both your examples, it indeed has a choice.

Let's assume the stack has an 1 on its top, and the next input symbol is 0.
The PDA can choose whether to take the transition $f(q_i,1,0)\to(q_i,0)$ or  $f(q_i,\epsilon,0)\to(q_i,0)$. Note that the effect is different: in the first it deletes the 1 in the stack and puts a 0 instead of it. In the second it adds a 0 on top of the 1 without removing it.

Therefore, there are two (different) paths the machine can go from this points, hence the nondeterminism.

Just to clarify: the definition for Deterministic-PDA is clear-cut: at any moment, and for any input/stack/state configuration there is only one possible transition. If this is not the case, the PDA is non-deterministic even if multiple transitions lead to the same configuration. It's just a matter of definition.

However, in the question above, the two transitions may actually lead to different configurations, which makes the nondeterminism even more clear.


How is the concurrent tracking of "state position" in NFA's typically modelled? Conceptually, to track the multitude of "state positions" arising in an NFA while it is processing a given input string, a quantitative notion of memory/cache/storage is required per "fork" of execution over the automaton, for keeping track of the states where the computation is currently "at".

What is the typical theoretical treatment, regarding the complexity of this degree of concurrency?!

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.


Lower limit on the number of check bits needed to correct single errors I was going through Andrew S. Tannenbaum's computer networks book, and on page 206 of it, he has derived the number of check bits needed to correct single bit errors. The derivation goes as follows:

For m data bits, there are 2^m legal messages. Each of these messages has n illegal codewords at a distance on 1 from it. These are formed systematically by inverting each of the n-bit codeword formed from it. Thus, each of the 2^m legal messages requires n+1 bit patterns dedicated to it....

Can someone please explain the last line to me? For an n-bit codeword, we can only flip n bits to get illegal codewords. When does that additional 1 come from?

I am very new to coding theory, so please excuse if this is a very naive question.

Thanks!

The comment by @gnasher is right. Moreover, if the code was $k$ error correcting with $m$ data bits, each of the $2^m$ legal messages would require
$$
1+n+\binom{n}{2}+\cdot+\binom{n}{k}=\sum_{j=0}^k \binom{n}{j}
$$
bit patterns dedicated to it, where $\binom{n}{j}$ is the number of words at Hamming distance $j$ from a given word.


Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression? I have an input number c of n bits and its prime factorization. I want to find a divisor of c with certain fixed bits "f". For example:

INPUT:
c=1100011 (99) (n=7)
prime factorization = 11,11,1011 (3,3,11)
f=0??1?0?

OUTPUT:
o=0001001 (9)

Unfortunately, it's no use to check all divisors, because according to http://en.wikipedia.org/wiki/Divisor there may be up to O(sqrt(2^n)) divisors, which is exponential.

Here is one special case that is solvable a bit more efficiently than brute force.  Suppose all of the fixed bits are consecutive and in the least significant bits.  For instance, we are given the desired value for the low $k$ bits.  Then this problem amounts to asking whether there is a divisor $d$ of $c$ such that $d \equiv f \pmod{2^k}$.

In other words, if $T$ is the multiset of prime factors of $c$, we are looking for a submultiset $S \subseteq T$ such that

$$\prod_{x \in S} x \equiv f \pmod{2^k},$$

where $f,k,T$ are given.  Let me sketch an algorithm for this special case.

How can we find a solution to this equation without enumerating all $2^{|T|}$ submultisets?  One way is to take discrete logs and reduce this to a subset sum problem.  In particular, the multiplicative group $(\mathbb{Z}/2^k\mathbb{Z})^*$ is isomorphic to $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2^{k-2}\mathbb{Z})$.  Let $\varphi$ be an isomorphism that maps $(\mathbb{Z}/2^k\mathbb{Z})^* \to (\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2^{k-2}\mathbb{Z})$.  Then, we search for a $S$ such that

$$\sum_{x \in S} \varphi(x) = \varphi(f).$$

So, if we can compute $\varphi$ efficiently, this basically reduces to a subset sum problem modulo $2^{k-2}$.  And it turns out that $\varphi$ can be computed efficiently using Hensel lifting (basically, you find the discrete log of $x$ modulo 8, then modulo 16, then modulo 32, and so on; at each step there are only two possibilities for the discrete log, so you try them both).  So, you compute $T^* = \{\varphi(x) : x \in T\}$ and $f^* = \varphi(f)$ and then try to find a submultiset $S^* \subseteq T^*$ such that

$$\sum_{y \in S^*} y = f^*.$$

This is a subset sum problem modulo $2^{k-2}$ (if you allow me to handwave over the $\mathbb{Z}/2\mathbb{Z}$ part of the range of $\varphi$).

And finally, there are algorithms for the subset sum problem that are more efficient than brute force trial-and-error of all subsets.  This then gives you an algorithm for your original problem, in the special case where all the fixed bits are consecutive and in the least least significant bits.

This connection also suggests that your problem is probably not in P.  In particular, it appears that we can show that your problem is at least as hard as subset sum, which is known to be NP-hard.  Therefore, it looks like your problem will be NP-hard, too.


Restriction of SAT to CNF I have spent a lot of time understanding these two issues. If you can help me, please.

Prove that the restriction of SAT to CNF formulas in which each variable xi appears at most twice is solvable in polynomial time.
Prove that the restriction of SAT to CNF formulas in which each variable xi appears
at most three times is NP-complete by showing $SAT \leqslant_p SAT_3 $
(hint: find a way to
create “clones” of each variable with different names.)

Thanks.

You can apply Davis-Putnam procedure and note that with the given restriction applying resolution rule will not be increasing formula size exponentially (in fact, it will be decreasing it). Thus, every iteration of procedure will have polynomial time complexity.
Read about Tseytin transformation and try to exploit the same idea. You can replace variable $x$ with $y$ and add $x \leftrightarrow y$ to the formula. With a proper replacement strategy you will be able to obtain an equisatisfiable formula in which every variable occurs at most three times: one in the original formula, one as the left part of equivalence, one as the right one.


Problems whose decidability status is unknown but known to be less hard than the halting problem Are there problems the decidability of which is unknown but it is known for certain that the problems are less hard than the halting problem.

Assuming that by "less hard" you mean "reducible to", then any problem that is known to be in $RE$ but not known to be in $R$ satisfies this condition.

For example, take the PCP problem with 4 tiles, whose decidability is open. It is an easy exercise to reduce the problem (or any other problem in RE) to HALT.


Find most stable combination of a vector with itself at different periods I receive a vector of varying length such as [0, 1, 2, 3, 2]. The value corresponds to the yield and its position to a time slot. Hence, at the first time slot the yield is zero, at the second period it is 1, etc.

I need a procedure that can combine this vector with itself at varying periods in order to ensure that the sum of the yields are the "most possibly" stable. Ideally it will be completely but I doubt that it is always possible.

I also need to make sure that it is indeed a periodic solution.

Below 2 examples that I solved by hand and a list of other example I don't know how to solve:

First one:

     [0, 1, 2, 3, 2]   [0, 1, 2, 3, 2]
           [0, 1, 2, 3, 2]   [0, 1, 2, 3, 2]
                 [0, 1, 2, 3, 2]   [0, 1, 2, 3, 2]
sum = 0  1  2  4  4  4  4  4  4  4  4  4...
In this example after an initialization period of length 3, we get a stable
pattern with a yield of 4

Second one:

     [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
        [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
                       [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
                          [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
sum = 0  0  0  1  1  1  1  1  1  1  1  1  1  1  1  1  1...
In this example after an initialization period of length 3, we get a stable
pattern with a yield of 1

However I could not find a pattern for the following vectors and I am searching for an algorithm that could identify the best pattern for any such one:

[0, 0, 2, 3, 2]
[0, 0, 2, 0, 3, 0, 4, 0, 2]

Precision 1: The vector will always start with at least a zero, but there can be many more, and it will always finish with a value above zero.

Precision 2: The solution should be the shortest periodic design that allows a stable sum of yield.

Retry at the problem specification: We have a production mean 'A' to grow plants. Each plant has specs as to how it grows, represented by a given vector as presented above. For a given 'A', once a plant production cycle is over, you can start a new one. We want to model a stable plant production with as few 'A' as possible.

Made up rule nr 1: Every number has to be part of the sum. Therefore the sum cannot be x, if there is a number b, such that no combination of numbers can add up to x-b.

So for [0, 0, 2, 3, 2]:

the sum cannot be 2 (because 3 cannot be part of that)
it cannot be 3 (because 3 - 2 = 1 and there is no combination of numbers that add
up to 1 (rule 1))
it cannot be 4 (because 4-3 = 1 again, (rule 1))
it cannot be 5 (because there are twice as many 2-s as 3-s)
it cannot be 6 (because in case of 3-s, only two rows in exactly the
same place can make up that number, and the 2-s would then form 4-s,
which cannot sum up to 6)

Therefore for the specific case of [0, 0, 2, 3, 2], the simplest solution is to have the value of 7

Perhaps this complicated reasoning helps to consider the future vectors as well :)

[0, 0, 2, 0, 3, 0, 4, 0, 2] is more difficult though. While not considering too thoroughly, it looks like for that as well, there isn't anything better than the trivial solution.

Trivial solution:

[a, b, c ....]
   [a, b, c ....]
      [a, b, c ....]
      ...


Choosing a shortest representative number from interval in arithmetic coding In arithmetic coding a word is coded as the binary encoding of a number in a certain interval. The interval is determined from a sequence of nested intervals according to the probability distribution on the letters of the word.

This encoding and decoding process is totally clear to me, but what wonders me is how an encoder chooses the optimal number (i.e. the one with shortest length if written in binary)?

For example, in the above linked wikipedia article in the paragraph Sources of Inefficiency in the example they choose 0.538 as the message, which is not optimal as it has quite a long (way longer than 8 bits) binary expansion when written in binary, as also noted choosing 0.5390625 would be much better.

Also, if we change the probability model with a uniform distribution we get $(5/27, 6/27)$ as an interval, as shown in the paragraph the binary codings of the boundaries are quite long, much longer then the $~5$ bits, but if we choose $0.1875$ then this could be coded with $0.0011$ which requires five bits if we submit $00110$ (the final $0$ seems to be necessary for the decoder as discussed in the paragraph).

So choosing the right number in the interval is in my understand the key of the compression algorithm (also backed up with the intuitive understanding that if we have a larger interval; which is given by higher probabilites from individual tokens, then we have more possibilites to choose numbers from to find one with a short binary expansion), but every textbook or notes I find just concentrates on describing the interval nesting procedure, but not how to choose a shortest representative?

So, if my understanding is correct this seems to be an essential part? So how to achieve this?

While you are encoding symbols between the ranges, you are not choosing which to use for the specific symbol. You are narrowing down the possible chooses there are.  You can arbitrarily choose them per symbol, but how would you adjust the ranges to make that the actual choice. It is true that the LAST symbol you can make a choice to make it fit within the rounding error , so long as it is within the range for that symbol.

The point of the example was that the incorrect distribution gives poor or worse compression. Choosing a better statics gives better results.  Hoffman encoding is at most within 1 bit per symbol of encoding, where arithmetic coding is within a fraction of a bit per-symbol, if the correct statics are used.  You can choose how accurate you do the encoding. Increasing the length of the RANGE's precision allows for more accurate representation of the given statics, thus  less error.   Choosing the wrong distribution for the specific message, regardless of the how accurate the encoding process is will get very poor compression or make it larger than the original message.  So.. think of it is an error rate.  The smaller you can make the error rate the, closer to the real limit you can achieve.  choosing a "static" distribution for all text files, will never give you the smallest compressed file this specific method can give you.

JUST A NOTE: "Optimum" is misunderstood. It simple means that the best a specific method can be.  Not that it is the highest compression available.


Finding the required value of an algebric expression I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.

I want to find the largest integer value such that it is less than $T$ and not satisfied by $Ax+By+Cz$, how can I do it without using brute force.

This is classical Integer Linear Programming. You have the following problem:

$$\begin{align}
Ax+Bx+Cx & \to \max \\
\text{s.t} \quad x,y,z &\ge 0\\
Ax+Bx+Cx &\le T \\
x,y,z &\in \mathbb{Z}\\
\end{align}$$

There are several algorithms available for such problems. Google "branch and bound" or "branch and cut" and you will get to them.

You can picture your problem as follows. Your variables $x,y,z$ decode a grid point in 3d. The constraints cut of hyperplanes, which keeps you left with a  set of candidate solutions. In your example this set is finite. You could basically test out all cancidates brute force. But it is more practical to add additional constraints to make the candidate set smaller - or in other words you filter out points. If you relax the condition that $x,y,z$ are integers, then the problem becomes much easier (Linear Programm), because then you know that the optimal point you are looking for is on some "corner" of your candidate set.


Combinations of set unions I have a set $S = \{0,1,2,3,4,5,6,7,8,9\}$. $S_i \subset S$ for $i = {1,2,3,4,5}$. Any three $S_i$ has the same union, that is $S_1
\cup S_2\cup S_3 = S_1\cup S_2\cup S_4 = ...=S_3\cup S_4\cup S_5 = A$ and no $S_i\cup S_j = A$. What is lexicoraphical least of such $S_i$s?
I have to write a Python code for this and I would appreciate any help that could direct me to find a solution. What should I know to be able to solve this problem in the shortest possible period? Also, if there's a better way to formulate this problem please do leave me comments with your suggestions. If the information is not sufficient I can clarify further.

I understood the problem as that we can select any $S_i$ satisfying these conditions. Then the answer is $\{0, 1, 2, 3, 4, 5\}$. The construction is unique in a certain sense.
Wlog we can assume that $S=A$ (otherwise, just remove redundant elements from $S$). I'll use $A, B, C, D, E$ instead of $S_i$. One way to arrive at a solution is to draw a Venn diagram for $A, B, C$ and to think about it:

What can we say about it:

$A \setminus (B \cup C) \ne \emptyset$. Otherwise $B \cup C = A \cup B \cup C = S$. Similarly for $B$ and $C$.

For $D$ we must have $A \setminus (B \cup C) \subseteq D$. Otherwise, $B \cup C \cup D \ne B \cup C \cup A = S$. Similarly for $B$ and $C$.

For $D$ we must have $A \cap C \setminus B \not \subseteq D$. Otherwise (just look at the diagram),
$$B \cup D = B \cup (A \setminus (B \cup C)) \cup (C \setminus (A \cup B)) \cup (A \cap C \setminus B) = S$$

What we said for $D$ also holds for $E$. I.e. it must contain the symmetric difference but must not contain $A \cap C \setminus B$ and similar.

We must have $D \cup E \cup X = S$ for $X = A,B,C$. Therefore, $D \cup E \cup (A \cap B \cap C) = S$. In particular, it means that $A \cap B \cap C \not \subseteq D \cup E$, since otherwise $D \cup E = S$.
Also, $S \setminus (A \cap B \cap C) \subseteq D \cup E$. Therefore, forgetting about symmetric difference:
$$((A \cap C) \cup (A \cap B) \cup (B \cup C)) \setminus (A \cap B \cap C) \subseteq D \cup E$$
Therefore, while $A \cap C \setminus B$ doesn't belong to either $D$ or $E$, it belongs to their union.

Note that conditions above are necessary and sufficient. Putting this together:

$A \setminus (B \cup C)$ must have at least one element, which also belongs to both $D$ and $E$. The same for $B, C$.
$A \cap C \setminus B$ must have at least two elements: one belongs to $D$, another belongs to $E$. The same for other pairwise intersections.
$A \cap B \cap C$ has at least one element, which doesn't belong to either $D$ and $E$.

Note that we've used all $10$ elements from $S$. All sets $A,..,E$ have $6$ elements, so we just select one of them to be $S_1$, and arrange elements in the sets so that $S_1 = \{0,..,5\}$


Spanning tree with chosen leaves I'm working on the following problem:

  Suppose that we're given a connected, undirected graph $G = (V, E)$ with
  edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find
  the lightest spanning tree in which the nodes of $U$ are leaves (they
  may be other leaves as well). We want to do so in $O(|E|\log(|V|))$ time.

Here's my thinking: since every node $v \in U$ must be a leaf, there must exist a vertex $u \in V \setminus U$ that is the source (i.e. each leaf in $U$ is connected to $u$). However, I'm having trouble find a way to do this that doesn't involve running a polynomial time algorithm. Can anyone help?

Hint for idea: Consider the subgraph $G'$ induced by the vertices in $V \setminus U$. Compute its MST $T'$. Then how should you attach the vertices in $U$ to $T'$?

Hint for implementation: To achieve $O(|E| \log |V|)$, you still run ordinary MST on the original graph $G$, but pay special attention to the vertices in $U$.


Explain why a language can be generated by a context free grammar I have a problem where I am asked to explain why the language that has words made of $a$ and $b$ such that the number of $a$'s is equal to the number of $b$'s, can be generated by a context free grammar. I am not sure of what is asked here, will finding such a grammar work? What should I do?

Usually, to prove that some language is a CFL (which is equal as asking whether it is generated by some CFG) you can show:

It is generated by some CFG. Proving is usually done by induction, where one direction is an induction on the number of derivation steps, and the other direction is usually an induction on the length of the word.
Showing a PDA that accepts the language.
Using closure properties of CFL, and generate the language from some finite number of CFL/regular languages using closure properties (like concatenation, union, etc..)


How Do You Design an Algorithm for This Graph Introduction
I'm not really understanding my algorithms class. One of our HW assignments is to design an efficient algorithm for this graph

Questions

Give an efficient algorithm to find the
fastest route for Alice to leave home, reach some gas station, then get to work.

On her way home, Alice wants to visit both a grocery store and a hardware store (in some
order). Give an efficient algorithm to find the fastest route for Alice to leave work, visit both
stores, and get home.

Thoughts
I was thinking something along the lines of A* search and make Gas Stations have a 0 heuristic, or something like create a list of the shortest paths and choose the shortest path with a gas station?
Honestly, I don't know how to implement this. How do I go about reasoning about this?
For example, how would I implement my second solution?

Both questions can be solved in time $O(m + n \log n)$, where $n$ and $m$ are the the number of vertices and edges of the input graph graph $G$.

For question $1$: Create a directed graph $G'$ consisting of two copies of  $G$ (you can think of $G$ as directed by replacing each undirected edge $\{u,v\}$ with the two directed edges $(u,v)$ and $(v,u)$).

For each vertex $v$ that represents a gas station in $G$, let $v_1$ and $v_2$ be the vertices corresponding to $v$ in the first and second copy of $G$ in $G'$, respectively, and add the directed edge $(v_1, v_2)$ to $G'$. The weight of $(v_1, v_2)$ is $0$.
Finally, find the shortest path $P$ from home (in the first copy of $G$) to work (in the second copy of $G$). The length of $P$ is exactly of the shortest route from home to work that passes through a(t least one) gas station.

Question $2$ can be solved similarly. First, guess the order in which the stores are visited (there are only $2$ possible choices). Then, create a graph $G'$ with 3 copies of $G$.
Intuitively, going from the first copy to the second copy means visiting the first store, and going from the second copy to third copy means visiting the second store.


Introduction to computer science for ML I have learned python syntax (from books like fluent python or python cookbook etc.) and I want to learn the underlying concepts of computer science (in an abtract way), do you have some books/courses to suggest to me (others than algorithms and data structures' resources)

I've found a book called Python Programming. An introduction to computer science by John Zelle, but I am worried about the potential huge overlap between the above-mentionned books and this one.

Some books found while brwosing the web, but I don't have an idea about its usefulness :

Structure and Interpretation of Computer Programs  by Harold Abelson, Gerald Jay Sussman, and Julie Sussman
Compilers: Principles, Techniques, and Tools by Alfred V. Aho
How to design computer programs by  by Matthew Flatt, Matthias Felleisen, Robert Bruce Findler, and Shriram Krishnamurthi
Theory of Computation by Michael Sipser

PS: My backgraound is a Bachelor degree in Mathematics. My goal is to gain sufficient knowledge of CS concepts.

Thanks

Computer science is a very broad field - see this Wikipedia outline. Machine learning is just one topic within the field, and there are other parts of computer science that have little or no overlap with machine learning. For example, the theory of compiler design is unlikely to be of much use to you when studying machine learning.

My suggestion is to approach this from the opposite direction. Start with a text that provides an introduction to machine learning. An introductory text should include an overview of other computer science topics that are pre-requisites. If you want to or need to dig into any these wider topics in more detail, then you have a more focussed goal than trying to understand the whole of computer science.


Weighted Average of Neural Networks with Cross Entropy Cost Function What is the best way to create an ensemble of neural networks utilising weighted averaging when these networks were trained to minimise cross entropy error function?

The literature I found (e.g. [1]) seems to be talking only about weighted averages of neural networks that employ mean square error (MSE) cost function. Anything other than that seems to require a modification of the training algorithm. Is there an analytic extension of [1]'s generalized ensemble method (GEM) algorithm to compute neural networks' weightings when cross entropy error function is used? Or some entirely different algorithm would be required? Or maybe it can only be done by numerically estimating those optimal weightings?

[1] M. P. Perrone and L. N. Cooper, "When networks disagree: Ensemble methods for hybrid neural networks," in Artificial Neural Networks for Speech and Vision. Chapman and Hall, 1993, pp. 126-142.

Disclaimer: In most situations, I would expect that a single neural network will be at least as good as an ensemble, so there's typically probably not much reason to bother with an ensemble.  In particular, if we compare an ensemble of $n$ small neural networks to a single big neural network that is $n$ times as large, I would expect that typically the big neural network will perform at least well as the ensemble.  So in most situations you're probably better off skipping the ensemble and training a big neural net. That said, here's how you can train an ensemble.

Unweighted average: The simplest way to train an ensemble is to use an unweighted average of the softmax outputs of the individual networks.  Let $F_1,\dots,F_n$ denote the networks in the ensemble, $F_i(x)$ denote the vector of softmax outputs of the $i$th network on input $i$, and $F_i(x)_c$ denote the softmax output for class $c$ from $F_i(x)$.  Define $F$ by

$$F(x) = (F_1(x) + \dots + F_n(x))/n,$$

i.e.,

$$F(x)_c = (F_1(x)_c + \dots + F_n(x)_c)/n.$$

This is the unweighted average of the individual networks.  You can train $F$ in two ways: either train each network individually, or train the whole ensemble end-to-end.

To train the ensemble end-to-end, you treat $F$ as a big model whose parameters are all of the parameters of all of the networks, and you optimize cross-entropy loss applied to the output of $F$.
Alternatively, you can train each network individually.  Train $F_1$ using cross-entropy loss on the output of $F_1$; then train $F_2$; and so on.

In principle, end-to-end training should yield performance at least as good as training each network individually.  However, training each network individually is simpler and requires less memory on the GPU.

Weighted average: We can generalize these ideas to train an ensemble that is a weighted average of the outputs of the individual neural networks.  Define $F$ by

$$F(x)_c = {\alpha_{1c} F_1(x)_c + \dots + \alpha_{nc} F_n(x)_c \over \alpha_{1c} + \dots + \alpha_{nc}},$$

where the $\alpha_{ic}$ are the weights.  There are two ways to train such an ensemble:

You can train it end-to-end.  You have a big model for $F$, whose trainable parameters are the parameters of the individual networks as well as the weights $\alpha_{ic}$.  Then, apply an optimizer to minimize cross-entropy loss applied to the output of $F$.
Alternatively, you can train each network individually, then fix the networks and train the weights $\alpha_{ic}$ subsequently.  Once you've trained the individual networks, compute new feature vectors $v_{ij} = F_i(x_j)$, where $x_j$ is the $j$th element of the training set.  Now you can throw away the $x$'s and work only with the $v_{ij}$'s, as we have
$$F(x_j)_c = {\alpha_{1c} v_{1jc} + \dots + \alpha_{nc} v_{njc} \over \alpha_{1c} + \dots + \alpha_{nc}}.$$
Finally, user an optimizer to learn the parameters $\alpha$ that minimize the cross-entropy loss on $F(x_j)$'s, using the above equation to relate this to the (trainable) $\alpha$'s and the (fixed) $v$'s.  Any stochastic gradient descent based optimization method should work fine.  You might want to initialize all the $\alpha$'s to $1/n$, and renormalize the $\alpha$'s after each iteration to prevent them from growing without bound.

The same tradeoffs between end-to-end training vs training each network individually apply.

I'm not expecting an ensemble based on a weighted average to do significantly better than an unweighted average, in most cases; and I'm not expecting an ensemble to do significantly better than a single large network, in most cases.  But there could always be exceptions, and hopefully this gives you a reasonable way to train such ensembles.


Shortest path in a incomplete graph I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. Retrieving the shortest path of a dynamic graph

My question is a little different.

  Given the entry node $S$, while the entire graph $G(V, E)$ is unknown at the beginning. There's a function public List<Edge> get(Node node) to figure out the outgoing weighted edges at each node. Also, there's another function public boolean isExit(Node node) tells you when to stop if the node is an exit node.

The question is a lot like the shortest path finding problem in a maze, where you're at the entry, you only know the next moves of the current node and past nodes, you'd like to find the exits (multiple) in the shortest path. In this analogy, we care more about how to find the "exit" quickly, rather than finding the global optimal shortest path.

I'm wondering if the normal Dijkstra algorithm (Greedy + Relaxation) still applies in the case.

  Because we don't know the full graph, the shortest path to a node might haven't been explored yet, and exist in the unknown part. (That's my biggest concern).

I hope my explanations are clear enough, thank you very much!

Algorithms don't care whether you find out what edges lead from a vertex by looking them up in an array, by calling a function called get() or by waiting for divine revelation.

The only problem with Dijkstra's algorithm is that, as it is usually described, it starts by setting the distance estimate of every node to infinity and adding every node to a queue. You can't do that if you don't know the nodes at the start of the algorithm.  However, Dijkstra doesn't need to do this and, even if you do know the graph before you start, it's not very efficient.  It's enough to add the nodes to the queue as you discover them.  This variant of the algorithm is often called "uniform-cost search" (especially in AI), though some people argue that it's just Dijkstra's algorithm and that Dijkstra never really intended to add all the nodes to the queue at the start.

If you look at the two algorithms/versions of the algorithm, you'll see that a node that classical Dijkstra thinks is at distance infinity is a node that has not yet been added to the queue in uniform-cost.

Ariel Felner gave a good analysis of the relationship between classical Disjkstra and uniform-cost in Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Disjkstra's Algorithm (Proc. 4th Intl. Symposium on Combinatorial Search (SoCS 2011), AAAI Press, 2011; PDF).


How to deal with Multiple Logs? (Big O) So I couldn't figure this one out, what do i do when i have multiply logs as the running time of an algorithm.

For example:

f(n): loglogn
g(n): logloglogn

Does f = Omega(g) in this case? as in g is a much slower growing algorithm than f?

The starting point is the limit
$$
\lim_{n\to\infty} \frac{\log n}{n} = 0,
$$
which can also be stated succinctly as $\log n = o(n)$. If $f(n)$ is any function such that $\lim_{n\to\infty} f(n) = \infty$, it then follows that
$$
\lim_{n\to\infty} \frac{\log f(n)}{f(n)} = 0,
$$
or more succinctly, $\log f(n) = o(f(n))$. In particular, taking $f(n) = \log n$ we get $\log\log n = o(\log n)$, taking $f(n) = \log\log n$ we get $\log\log\log n = o(\log\log n)$, and so on.

More generally, if $a(n) = o(b(n))$ and $f(n) \to \infty$ then $a(f(n)) = o(b(f(n))$. (The case above was $a(n) = \log n$ and $b(n) = n$.) There are similar rules for big O, which I leave for the reader to discover.


How to find partition set of a Partition Problem using its decision problem I understand Partition Problem is NP-complete.

Given we have a magic black box that can answer Yes or No for the partition problem. I was wondering how to come up with a polynomial time algorithm to find the actual set using this black box.

Thank you.

Here is what you would do if instead of PARTITION you had SUBSET-SUM. Given a set $S$ and a target $T$, repeat the following process:

Pick some $x \in S$.
If $S \setminus \{x\}$ has a subset summing to $T$, remove $x$ from $S$ and go back to 1.
Otherwise, remove $x$ from $S$ and replace $T$ with $T - x$. Mark $x$ and go back to 1.

The set of all marked elements at the end of the algorithm is an answer.

This approach doesn't work for PARTITION (why?), but perhaps it helps figuring out how reductions of this sort work. One idea to try for PARTITION is merging elements (replacing $x,y$ with $x+y$). I'll let you work out the details.


Longest Repeated (Scattered) Subsequence in a String Informal Problem Statement:

Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right yields the same result as reading only the blue letters.

In the example we could colour them like this: $A\color{blue}{C}\color{red}{CAB}B\color{blue}{AB}$

Therefore, we say $CAB$ is a repeated subsequence of $ACCABBAB$. It is also a longest repeated subsequence (which is easy to check).

Can we compute longest repeated subsequences efficiently?

Formal Question:

Is it NP-hard to decide for a string and some $k$, whether a repeated subsequence of length $k$ exists in the string?

If so: Which problem can be reduced to this problem?
If not: What is an efficient algorithm? (obviously, this algorithm can then be used to compute a longest repeated subsequence)

Bonus Question:

Will their always be a repeated subsequence of length $n/2 - o(n)$ if the size of the alphabet is bounded by a constant?

(This is known to be true for binary alphabets.)

Edit 2: The negative answer to the Bonus Question is already known for alphabets of size at least $5$. In fact for alphabets of size $Σ$, there are strings with longest repeated subsequences of a length of merely $O(n · Σ^{-1/2})$. Random strings suffice to show this. The result already existed, but I overlooked it.

Edit:
Note:

Some people mean "substring" when they say "subsequence". I don't. This is not the problem of finding a substrings twice.

The special case of $k = n/2$ is the same problem as this CST.SE question How hard is unshuffling a string? asks.
Buss and Soltys proved NP-completeness of this problem [1] by reducing 3-Partition problem to this problem.

[1]: Buss, Sam, and Michael Soltys. "Unshuffling a square is NP-hard." Journal of Computer and System Sciences 80.4 (2014): 766-776.


Formal definition on graph levels I'm looking for a formal definition of "graph levels" on a DAG. This example should illustrate what I mean by this.

The node 0 has no edges directed towards it, therefore this has level 0. Next is is 3 and 4 which will have level 1 and so on.

Level 0 : node 0

Level 1 : node 3, node 4

Level 2 : node 1, node 2

Level 3 : node 5

A DAG (or poset) is ranked or graded if it is possible to assign nodes a rank function $r$ such that if $(x,y)$ is a directed edge, $r(y) = r(x)+1$. We usually choose $r$ so that $\min r = 0$. See for example the Wikipedia article on graded poset.


Two regular languages over the same alphabet, regular or not regular? TRUE or FALSE:
Let $L_1, L_2$ be any two regular languages over the same alphabet $\Sigma$, then the language $L=\{w\in\Sigma^* \mid w\in L_1 \text{ or } w\notin L_2\}$ is regular.

So we have to determine whether $L_1 \cup \overline{L_2}$ is regular or not.
Proof:
First attempt:
First we have to prove that a complement of a regular language is also regular: the complement of a language $L$ with respect to an alphabet $\Sigma$ such that $\Sigma^*$ is $\Sigma^*-L$. Since $\Sigma^*$ is surely regular the complement of a regular language is always regular.
Let's prove that the union of two regular languages is also regular: For example, let $\Sigma = \{a,b\}$. Assume $L_1 = \{a\}$ and $L_2 = \{b\}$ so they are regular language. Then the union: $\{a\} \cup \{b\} = \{ab\}$ is also regular. Since $\{a\}$ is regular , $\{a\}^*$ is also a regular language.
After these two proofs we can say that the statement above is True.
Second attempt:
A regular language is regular iff there is a finite state machine recognizing it. Let $L_1 = \{S_1,\Sigma,\delta_1,s_0^1, F_1\}$ and $L_2 = \{S_2,\Sigma,\delta_2,s_0^2, F_2\}$ be two automata. First we have to take the complement of $L_2$. The complement of $L_2$ is the set of states without the set of final states: $\overline{L_2} = \{S_2,\Sigma,\delta_2,s_0^2, S_2-F_2\}$. Then we can create the product automaton of the two languages which is: $L = \{S_1 \times S_2,\Sigma,\delta_1 \times \delta_2,s_0^1 \times s_0^2, F_1\ \times (S_2-F_2)\}$. The final states of the language $L = L_1 \cup \overline{L_2}$ is the set of states where $F_1$ or $S_2 - F_2$ is final. Since there exists a finite state machine that recognizes the language $L$, we can say that $L$ is a regular language.
Can somebody please correct me? Maybe I made a mistake.

I see several problems.

In your first part you say that, given a regular language $L$, $\overline{L}$ is regular since  $\Sigma^*- L$ is also regular. This is true, but it is implicitly using the fact that regular languages are closed under difference. It is not clear if you're allowed to use that fact as a black box (since it is a more general statement than the one you're trying to prove).

In your second part you are not giving a proof. You are just showing that $L_1 \cup L_2$ is regular when $\Sigma=\{a,b\}$, $L_1 = \{a\}$ and $L_2 = \{ b \}$. What if $\Sigma \neq \{a,b\}$? What if $L_1 \neq \{a \}$?
Your proof needs to work for all possible choices of $\Sigma, L_1,$
 and $L_2$.

Moreover, $L_1 \cup L_2 \neq \{ab\}$ contrarily to what you claim.

Finally, you say that since $\{a\}$ is regular then so is $\{a\}^*$. This is true but it is unclear why you need this.


Relationship between circuit size and formula size in Sipser text The Sipser text (3rd edition) contains a proof that 3-SAT is NP-Complete based on Boolean circuits. Part of the proof contains the remark that the reduction from the circuit to the Boolean formula can be done in polynomial time.

First question: is it correct to say that if a circuit C of polynomial size exists, then there must exist a formula $\varphi$ of polynomial size where C is satisfiable if and only if $\varphi$ is satisfiable?

Second question: is the Boolean formula $\varphi$ still of polynomial size if C is of polynomial size and C is derived from a deterministic Turing machine M? This seems to be described in the proof of the earlier theorem in Sipser where (by building C from a tableau of M) it is shown that if $\mbox{A $\in$ TIME$(t(n))$ for $t(n) \geq n$ and $n \in \mathbb{N}$}$ then A has circuit complexity $O(t^2(n))$.

Yes, that's correct.  See the Tseitin transform, which describes how.  It doesn't matter how the circuit $C$ was constructed.


Aren’t most constraining variable and least constraining value the exact opposite? So aren’t MCV and LCV the exact opposite?MCV tries to choose the variable with the most constraints on
remaining variables but LCV is opposite: it tries to rule out as least values for other variables as possible

Yes, these two heuristics does sound like inconsistent. Most Constrained Variable (MCV) (also called MRV for Minimum Remaining Values) tries to reduce the size of the next branch to search while Least Constraining Values tries to enlarge the size of the next branch to branch.
However, if you take a close a look, they both serve the same goal, which is, given a Constraint Satisfaction Problem (CSP), to find a solution as fast as possible and, if there is no solution, declare that fact as fast as possible.
Firstly, these two heuristics are applied in different stages of the search. MCV is about choosing which variable to assign value to and then, given a variable, LCV is about choosing which value to assign.
Here is a quote from a lecture note on Constraint Satisfaction
Problems by Max Welling, slighted edited.

In all stages of the searching for one solution, we want to enter the most promising branch, but we also want to detect inevitable failure sooner.
MCV: the variable that is most likely to cause failure in a branch is assigned first. The variable must be assigned at some point, so if it is doomed to fail, we’d better found out soon.
LCV: tries to avoid failure by assigning values that leave maximal flexibility for the remaining variables. We want our search to succeed as soon as possible, so given some ordering, we want to find the branch that is more likely to succeed.

In term of the search tree, MCV help pruning bigger branches more often and earlier, thus makes the searching end faster, whether it ends with a solution or no solution possible. LCV help make backtracking less often in case there is a solution, but it does not help when there is no solution since every value has to be searched. In other words, if the goal is to find all solutions instead of one solution, then MCV still help effectively while LCV does not help at all.
I would like to use planning a party as an example. The variables are who should attend, when to hold it, where to hold it and how much to spend (why and what is another question). The object is to see if there is a party plan that is viable.
Suppose you are almost running out of money. Then the first thing to check is to set a tight limit on spending. You do not want to plan all the other parts in great beautiful detail only to find there is not enough money to support them later. Then within your budget you want to set a limit as high as possible so that there is more room to make the party plan attractive enough to be held. Note that you are applying the principle of MCV and LCV.
Consider another situation. You are planning a birthday party for one of your friends and you are not so constrained much by the money. Then you probably do not want to consider your budget first. The first thing you want to decide is probably when to hold the party since there are usually not many choices. It is expected usually to be held just before that birthday. Then in order to have most of remaining choices you want to pick a time such as the night on the birthday instead of in the afternoon when many people are still working or having classes. Only in case the night on the birthday does not work, for example because some people cannot attend, will you backtrack to the less likely choice of the afternoon on the birthday. Note again that you are using the approach of MCV and LCV.
We can see that MCV and LCV are working together to enable you to find a viable party plan faster. You can also imagine what might happen if you use the opposite approaches, the approach of least constrained variable first and maximum constraining values first
Although far from rigorous, this example of party planning might aid your conceptual understanding of MCV and LCV working together. (You can also view the example as an application of principles of artificial intelligence to guide our decision making process in real life.)
For more related material, you can check chapter 6, "Constraint Satisfaction Problems" in the leading AI book Artificial Intelligence: A Modern Approach (3rd Edition) by by Stuart Russell and Peter Norvig.


Recommendations for machine learning book? I am a microbiologist and I am currently self-studying machine learning from some open lecture videos. I am finding it pretty difficult to understand proofs that are somewhat "obvious", my poor mathematical knowledge is to blame for that. Can you please recommend a text-book that deals with the mathematical proofs of the theorems? Or approaches machine learning from the mathematical side?

MOOC Course on Machine Learning: https://www.coursera.org/course/ml

Guide to Mathematical Proofs from berkeley: https://math.berkeley.edu/~hutching/teach/proofs.pdf

Enjoy!


what are meta variables in this static analysis book's explanation about types? At page 21 of this book: https://cs.au.dk/~amoeller/spa/spa.pdf I found this:

I started reading everything and understanding it pretty well, until this.
It's defining the possible types of a language. I'm very confused about what theta and alpha mean. What are those meta-variables? What is ua.t and t[ua.t/a]?
Could someone give me some context? I'm not into computer science, this may be something specific that I have never seen before. I'm from a math background.

A metavariable is a variable that denotes some hypothetical chunk of a program. This distinction is important in the theory of programming languages, where we need to distinguish variables representing program fragments from the variables contained in those programs.
The terminology, I think, comes from logic: if you're defining a logic, you need to define it in some language that's distinct from the thing you're defining. This is the "meta-language", and the variables it uses are metavariables. The history of formal logic and programming languages are deeply intertwined via the Curry-Howard correspondence, so the terminology carried over.


Update labels of a tree depending on ancestors of nodes in linear time You are given a tree $T=(V,E)$ along with a designated root node $r \in V$.The parent of any node $v \ne r$, denoted $p(v)$, is defined to be the node adjacent to $v$ in the path from $r$ to $v$. By convention, $p(r) = r$.

  For $k > 1$, define $p^k(v) = p^{k−1}(p(v))$ and $p^1(v) = p(v)$ (so $p^k(v)$ is the $k$-th ancestor of $v$).

  Each vertex $v$ of the tree has an associated non-negative integer label $l(v)$. Give a linear-time algorithm to update the labels of all the vertices in T according to the following rule: $$l_{new}(v) = l(p^{l(v)}(v)).$$

This is problem 3.20 in Dasgupta's Algorithm.

My thoughts so far:

The problem comes down to how you find the $l(v)$-th parent of a node $v$, for all $v \in V$, in linear time.
Since chapter 3 is about depth first search, I'm trying to use it. The only way to get the parent once we have the child is to do something in the post-visit routine

explore(v):
  v.visited = true
  previsit(v)
  for all u adjacent to v:
    if u.visited == false:
      explore(u)
  postvisit(v)

If $l(v) = 3$ then somehow we need to send this information up 3 levels in the recursion. But depth first search only moves one level at a time. I don't know how we can preserve the information across multiple calls.

how we can preserve the information across multiple calls.

Excactly; we use a standard trick of functional programming and add additional parameters to the recursion.

Idea: Store (a copy of the) call stack in an array. Then, all ancestors of the current node are accessible in $O(1)$ time. You can do BFS or DFS.

Details: The main procedure starts at the root and creates an empty array of sufficient size:

relabel(T : Tree) {
  relabelH(T, 0, new Tree[T.size])
}

The second parameter stands for the current index in the array (i.e. recursion depth) which we use to determine the index of the $k$th ancestor. The actual work is done here:

relabelH(T : Tree, level : Int, ancestors : Tree[]) {
  ancestors[level] = T
  T.label = ancestors[max(0, level - T.label)].label

  for c in T.children {
    relabelH(c, level + 1, ancestors)
  }
}

Correctness: You can show by induction that ancestors[0..level-1] always contains the current node's ancestors in order from root to parent. Hence, the label update is correct. All nodes are reached (we do DFS) so the procedure is correct.

Running time: Every line in relabelH is executed once per visited node. Every individual line runs in constant time, assuming a reasonable implementation of Tree. The main call relabel(T) takes linear time (array initialization) plus the cost of the call to relabelH. In total, we get a running time in $\Theta(n)$ with $n$ the number of nodes (T.size).


Solving $T(n)=4T(n/4)+\log n$ using master theorem $T(n)=4T(n/4)+\log n$

I'm solving this recurrence relation by master theorem.

$a=4, b=4$ , $n^{\log_b a}=n^{\log_4 4}=n$

$f(n)=\log n=O(n^{1-\epsilon})$

when $\epsilon<1$, it is correct. So, $T(n)=\Theta(n)$.

But I'm confused how can $n$ be an asymptotically tight bound of $\log n$?

I'm not sure my solution is correct.

Let's use the other method to solve recurrences, namely, repeated substitution, assuming that $n$ is a power of 4:
$$
\begin{align*}
T(n) &= \log n + 4T(n/4) \\ &=
\log n + 4 \log(n/4) + 16T(n/16) \\ &= \cdots \\ &=
\log n + 4 \log(n/4) + 16 \log(n/16) + \cdots + (n/4) \log (n/(n/4)) + n T(1) \\ &=
(n/4) \log 4 + (n/16) \log 16 + \cdots + (n/n) \log n + nT(1) \\ &=
n \log 4 \left(\frac{1}{4^1} + \frac{2}{4^2} + \cdots + \frac{\log_4 n}{n}\right) + nT(1) \\ &=
\frac{\log 4}{9} (4n - 3\log_4 n - 4) + nT(1) \\ &=
\left(\frac{4\log 4}{9} + T(1)\right)n - \frac{\log n}{3} - \frac{4\log 4}{9}.
\end{align*}
$$
In particular, we see that $T(n) = \Theta(n)$.

Intuitively, what happens is that, roughly speaking, the dominant terms are $(n/4)\log(n/(n/4)) = (n/4)\log 4$ and $nT(1)$, which are both $\Theta(n)$; in the former term the logarithm is applied to a constant, and so the fact that the recurrence has $\log n$ rather than, say, $\log^2 n$ only affects the resulting hidden constant, but not the asymptotic complexity.


Add type checking/inference to my programming language I am currently creating my own compiled programming language, and I have come to a point where I would like to start working on the type system and introduce some type checking. Ideally I would like to introduce type inference.

Right now I'm using the Visitor pattern to traverse the AST produced by the parser. I started implementing a pretty naive and ugly solution, but wasn't very happy with it. It seemed pretty hacky. Type checking that fits with this pattern would be great, but not critical.

I have looked into algorithms like the Hindley-Milner. I'm developing the programming language in Swift, so I found this GitHub gist that shows how it can be implemented, but opening the lid on this code immediately gets me to Lambda Calculus, which seems like a beast. I know Swift uses a variant of the Hindley-Milner type inference, so that would be incredibly sexy to implement, but it's way over my head at this point.

Since this is my first programming language, what's a good first attempt at a type system with type checking, possibly with type inference?

You could start with the simple cases of Swift. Literals have type “Literal”, for example, and known variables have their known types. When you evaluate an expression you may know what type you want and evaluate accordingly, or you don’t know and get the type from the expression.

(Anyone not knowing the language: let x: Int = 7/2 assigns 3. let x: Double = 7/2 assigns 3.5 because assignment to Double wants a Double expression, therefore / wants two Double operands, therefore the literals 7 and 2 are Double).

Keep in mind you can always report an error if you can’t handle a situation, as long as the code can be changed to work without complaints.


Why is my proof wrong for $L = H_{TM} \cap \overline{A_{TM}} $ $A_{TM} = \{<M,w> | $ M  is a TM and M accepts w $\}$

$H_{TM} = \{<M,w> | $ M  is a TM and M halts on w $\}$

I thought that $L = H_{TM} \cap \overline{A_{TM}} \in R$

But I saw the proof for why $L \in RE \setminus R$

But I don't understand why this is wrong:

$H_{TM} \in RE$ and $\overline{A_{TM}} \in Co-RE $

We know that $RE \cap Co-RE = R$

So why is this wrong $L = H_{TM} \cap \overline{A_{TM}} \in RE \cap Co-RE = R$ ?

$RE$ and $co-RE$ are sets of sets of strings. $H_{TM}$ and $\overline{A_{TM}}$ are sets of strings. You correctly have that $H_{TM}\in RE$ and $\overline{A_{TM}}\in co-RE$. However, you cannot then conclude that
$$
H_{TM}\cap\overline{A_{TM}}\in RE\cap co-RE
$$
For a simple example, let
$$
A=\{\{1\},\{2\}, \{1, 3\}, \{2, 3\}\}\text{ and }B=\{\{1\},\{3\}, \{1, 2\}, \{2, 3\}\}
$$
So $A$ will serve as $RE$ and $B$ will serve as $co-RE$. Then we have $A\cap B=\{\{1\},\{2,3\}\}$. Now let $x=\{1,3\}\in A$ and $y=\{2,3\}\in B$ (here $x$ serves as $H_{TM}$ and $y$ serves as $\overline{A_{TM}}$). Then $x\cap y=\{3\}\notin A\cap B$.


Is the language of binary strings that contain a substring of the form $ww$, where $w \in (0+1)(0+1)^*$ regular? Consider the language:
$L=$binary strings that contain a substring of the form $ww$, where $w
   \in (0+1)(0+1)^*$.
I am convinced this language is not regular, as $w$ can have arbitrary length due to the $(0+1)^*$ term, and whatever is generated by this term must be remembered for the next occurrence of $w$ immediately thereafter. So, a DFA cannot accept this language. Is this correct? Perhaps, I could show this more formally with the pumping lemma, but I just want to make sure the intuition is correct.
Now, do you agree that the way I have defined the language above implies that the first occurrence of $w$ must be the same as the second occurrence of $w$? For example, $w$ cannot equal $01$ in its first instance, but $011$ in its second instance.
Now, consider the language:
$T=$binary strings that contain a substring of the form $wy$, where $w,y
   \in (0+1)(0+1)^*$.
T is regular. Because $(0+1)^*(0+1)=(0+1)(0+1)^*$, the regex representing $T$ can be written as $(0+1)^*(00+01+10+11)(0+1)^*$. Is this correct?
Now, back to language $L$. This was defined in some exercises I was doing exactly as it is above. The solution said that $L$ is regular and can be represented by regular expression: $(0+1)^*(00+11+0101+1010)(0+1)^*$.
Lastly, If my thinking about $L$ is incorrect for some reason, does the regular expression $(0+1)^*(0+1)(0+1)^*(0+1)(0+1)^*(0+1)^*$ equal $L$?
I hope I have communicated my thoughts clearly on this matter. Please help me understand.

Your language is regular.
Let's see which words do not belong to $L$. If a word contains $00$ or $11$ as a substring that it does belong to $L$, hence any word not in $L$ must have alternating $0$s and $1$s. If such a word has length at least $4$ then it must start with $0101$ or $1010$, and so again it is in $L$. We are left with the following words, which comprise $\overline{L}$:
$$ \epsilon, 0, 1, 01, 10, 010, 101. $$
Since $\overline{L}$ is finite, it is regular, hence so is its complement $L$.
What this argument shows is that any word in $L$ contains one of $00,11,0101,1010$ as a substring. This explains the given regular expression.


Whats the difference between an oracle and a decider in Computational Theory? I'm learning about Turing reductions at the moment and I'm just wondering is there any difference between an oracle and a decider, As they seemingly do the exact same thing. I understand the point of a oracle is that we don't have to know how it gets its answer but it will always give us the right answer.

  An oracle for a language B is an external device that is capable of reporting whether any string w is a member of B

which is the exact same thing as what a decider does. Is there any sort of difference between the two?

Oracles are entities capable of deciding even undecidable problems. Deciders, on the other hand, are essentially Turing machines (without an oracle) and therefore cannot solve undecidable problems (e.g. Halting problem).

  I understand the point of a oracle is that we don't have to know how it gets its answer but it will always give us the right answer.

This is in fact the key difference.

An oracle doesn’t have an implementation, it is just a black box giving answer to any particular question (most importantly, the ones we cannot answer), whereas a decider has to be well defined Turing machine. In other words, we must know how a decider gets the answer, meaning it cannot answer any question.


Data structure for handling intervals I am trying to create a data structure for handling the subsets of the real line of the form $[x,y)$. That is, suppose $X \subseteq \mathbb{R}$ and the data structure supports two types of operations: $add(X, [x,y))$ and $remove(X,[x,y))$. Each of these two queries return the number of disjoint semi-intervals in $X$. For instance,

> add(X, [2, 10))
> 1
> add(X, [3, 9))
> 1
> add(X, [-1, 1))
> 2
> remove(X, [2, 10))
> 1

I suspect that this can be realised with binary search tree, however I could
not properly invent the behaviour. I still suspect this can be done in such a way that each query works in $O(\log n)$ time, where $n$ is the total number of queries. Can you please suggest anything?

Since all intervals are non-overlapping, the use of an interval tree is unnecessary. We will store our intervals in an AVL tree $T$ sorted by start points and use the fact that bulk deletion of a set of contiguous keys $q_i,...q_{i+k-1}$ can be done in $O(\log n + \log k)$ amortized time (see non-open access and open access).

Let $x=[a,b)$ be an interval and  $begin(x)=a$, $end(x)=b$. We define $pred(x)$ and $succ(x)$ to be the previous and next intervals. Both functions have $O(\log n)$ complexity, where $n$ is the number of intervals in the tree. The number of disjoint intervals is the number of leaves in $T$.

Insertion

Let us first examine what happens when we insert an interval $x$ into the tree. When inserting $x$, we can determine the range of intervals it overlaps with in $O(\log n)$ time by performing predecessor and successor queries. When inserting $x$, we need to perform one of the following three operations on $T$

Add a new disjoint interval.
Extend an existing interval.
Combine and potentially extend $k$ existing intervals.

(1a) The first case happens if the inserted query $q$ doesn't overlap with any of the intervals in our set i.e. $
end(pred(x)) \leq start(x) \land begin(succ(x)) \geq end(x)$ Since no intervals need to be updated, we simply insert $x$ into $T$.

(2a) The second case happens if $x$ overlaps with or contains one other interval $q$. In order to update the interval, delete $q$ and reinsert $q'$ where $$q'=[\min(start(x), start(q)), \max(end(x), end(q)))$$

(3a) In the third case, let $Q=\{q_i, q_{i+1}, ... q_{i+k-1}\}$ be all $k$ of the intervals that $x$ intersects. $Q$ can be obtained by finding the predecessor and successor of $x$. We can again update the tree by deleting all of $Q$ from $T$ and reinserting an interval $$q'=[\min(start(x), start(q_i)), \max(end(x), end(q_{i+k-1})))$$

The first and second cases have $O(\log n)$ time complexity. The third case at first looks like $O(k\log n)$ time which is undesirable as $k=O(n)$. However, it has been shown that bulk deletion of a set of keys in the range $[L, R]=\{q_i, q_{i+1}, ... ,q_{i+k-1}\}$ can be done in amortized $O(\log n + \log k)$ time. Therefore, for insert we have amortized $O(\log n)$ complexity. Note that the number of leaves (disjoint intervals) in the tree can be updated after each insertion in constant time.

Deletion

By deleting an interval $x$, we either

Split an interval into two
Shorten 1 or 2 intervals and delete those in between (if any).

(1b) The first case happens if $x$ is nested within an interval $q$ i.e.
$$start(q) \leq start(x) \land end(x) \leq end(q) $$ Therefore, we delete $q$ and insert the two resulting intervals $[start(q), start(x))$ and $[end(x), end(q))$

(2b) In the second case, let $Q=\{q_i, q_{i+1}, ... q_{i+k-1}\}$ be the intervals that $x$ overlaps with. We can delete all of $Q$ from the tree and update and reinsert the the trimmed versions of $q_i$ and $q_{i+k-1}$ if they were not completely nested in $x$. As in case (3a), this is a bulk deletion that can be done in amortized $O(\log n + \log k)$ time.

Similar to insertions, we can keep track of the number of leaves after each deletion in constant time.

Amortized Complexity of Bulk Updates in AVL-Trees

Bulk Updates and Cache Sensitivity in Search Trees


What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable? Definitions:

positive CNF is a conjunctive normal form formula, where all literals are positive, i.e. the unary connective ¬ does not exist in the formula.

negative CNF is a conjunctive normal form formula, where all literals are negative, i.e. the unary connective ¬ appears next to each literal.

My question is:

Given a CNF, which is a conjunction of positive CNF and negative CNF, what is the complexity of the problem to determine that this special case of CNF is satisfiable?

Does exist polynomial time and space algorithm to solve this problem?

EDIT: Another name for "positive CNF" is "fact CNF", where all clauses are fact and another name for "negative CNF" is "goal CNF", where all clauses are goal.

... clause with no negative literals is sometimes called a fact

... clause without a positive literal is sometimes called a goal clause

Quoted from: this wikipedia documentation

Given a CNF, which is a conjunction of positive CNF and negative CNF, what is the complexity of the problem to determine that this special case of CNF is satisfiable?

The problem is provably NP-complete by reduction from CNF satisfiability.

Each negative literal $\lnot{x}$ in a CNF SAT instance can be converted to a positive literal by replacing all occurrences of it with a new variable $z$ plus the following two CNF clauses: $x \lor z$ and $\lnot{x} \lor \lnot{z}$.  The clauses force $z$ to act as the same constraint as $\lnot{x}$.  Once all the original negated literals have been replaced, you are left with clauses that contain either all positive or all negative literals.  Since any CNF SAT instance can be reduced to this form and since CNF SAT is NP-complete and since your problem is trivially in NP, your problem must be NP-complete.


What would be the appropriate learning path given these circumstances? I've recently been trying to learn to program in python but I’ve been experiencing this overwhelming feeling of a desire to understand the underlying structure behind everything I’m doing. I want to be able to understand how computers work from the ground up, how hardware and software relate to one another and develop an intuition for their potential. I'd also like to know how all these languages that build on top of each other all rely on the same fundamentals and what those fundamentals are. Only then do I think I’ll feel comfortable and satisfied learning and working on a more superficial abstraction which I consider python to be.

Can any of you recommend a path I should take in order to satisfy this need? Whether that be a particular order of learning certain topics or more specifically any book, video, course that you might consider appropriate given my situation.

Thank you,

Mango164

A project I would recommend is the NandToTetris Project. It takes you from understanding the basic logic gates through VonNeumann architecture to how Operating Systems work.


TSP genetic algorithm: what mutation function for adjacency representation? When implementing TSP GA I decided for adjacency representation (i.e. $j$ value in $i$-th index means that node $j$ goes right after node $i$), as it enables interesting heuristical crossover operation (see Greffenstette, 1985). However this source, like many others, is silent about a sensible option of mutating solutions written in this way.

Traditional approaches (taken from path representation) usually result in incorrect solutions. For example, let's take permutation 5 4 1 3 2 (path rep. 1 5 2 4 3) and try swapping second and third position, namely giving 5 1 4 3 2. Path representation would start with 1 5 2 1 and oops, we're stuck. Another methods are similaringly disappointing.

So, is there an elegant and fast (emphasis on the latter) idea to mutate? Of course, I can switch between representations, but it might strongly impact performance (a switch is linear complexity, though I believe there's a chance of finding something with $O(1)$) and it's a worst-case scenario.

The core of your problem is this: you want a simple mutation operator that sends any $n$-cycle to another $n$-cycle.

Recall that every permutation on $n$ symbols can be decomposed into cycles.  To count as a TSP tour, you need the permutation to be a single cycle, i.e., it to be a $n$-cycle.  So given a TSP tour (a permutation that is a $n$-cycle), you want your mutation operator to give you another TSP tour (another $n$-cycle).

Here are multiple approaches you could take:

Don't represent the tour in your adjacency representation.  Instead, represent it as a $n$-cycle: represent it as a list of the vertices visited, in the order they are visited.  Then, you can swap any two elements in the list and get another tour (another $n$-cycle).  For instance, you'd represent your example path as the list [1,5,2,4,3].  Swapping the second and third position gives you [1,2,5,4,3], which is another valid path.
Represent the path in adjacency representation.  Do the same operation as above, but now apply it directly to the adjacency representation: emulate its effect on the adjacency representation.  So, given 5 4 1 3 2, you decide you're going to swap the order that 5 and 2appear in.  This can be done by replacing the5with a2, and replacing the2with the second element (4), and replacing the second element with2`.
Pick a suffix of the path, then splice that into the middle of the path.  For instance, suppose you can decompose the path into $A \to \dots \to F \to G \to \dots \to P \to Q \to \dots Z \to A$.  Then you could change this to $A \to \dots \to F \to Q \to \dots \to Z \to G \to \dots P \to A$ by splicing the $Q \to \dots \to Z$ part right after $F$.  You can take any suffix and splice it in, at an earlier position, like this.  This can be done via a not-too-complex transformation on the adjacency representation, by changing only three elements in the adjacency representation (in this example, you change the successor for $F,Z,P$).


Transform in linear grammar i have the following regular grammar :
$$S \rightarrow aS | cS | bQ_1$$
$$Q_1 \rightarrow bQ_2$$
$$Q_2 \rightarrow aQ_3 | cQ_3 | bQ_1$$
$$Q_3 \rightarrow aQ_4 | cQ_4$$
$$Q_4 \rightarrow \varepsilon$$

The question is to transform that into a linear grammar with less nonterminals than the regular grammar and my idea was:
$$S \rightarrow aSa | cSc | aSc | cSa | bQ_1a | bQ_1c$$
$$Q_1 \rightarrow b$$

and the rest i don't know. Could you help me to solve this problem?

Judging from the wording of your question you are still confused about what it means for a grammar to be linear but I wont address that here. If you want to make the grammar smaller you could do the following: remove $Q_4$ from the right hand side of all production rules and remove all rules which start with $Q_4$. You can do this because $Q_4$ doesn't generate anything so it is effectively useless. Next, notice that $Q_1$ serves only to increase the number of $b$'s by one, so you can remove that, too. We can also do a similar trick to remove $Q_3$ as now all $Q_2$ does is give us one of the following strings by rewriting $Q_3$: $$aa, ac, ca, cc$$.

So the resulting grammar looks like this:

$$S \rightarrow aS | cS | bbQ_2$$
$$Q_2 \rightarrow aa | ac | ca | cc | bbQ_2$$.

I'm not claiming that this is the fewest number of non-terminals for this language, maybe you could/should prove that it is/isn't?


How are matchings a lower bound for an approximate vertex cover? I am reading Algorithms by Dasgupta et al and they mention maximal matchings as approximations for vertex cover.
They mention that the 2-approximation ratio is a lower bound. How is a maximal matching a lower bound? Does it mean that it is the lowest approximation value we can get compared to $\log n$ of the greedy algorithm that is polynomial?
The images below show the optimal vertex cover = 8 but and a maximal matching of 12.

I decided to find another matching which I later discovered is called a maximum matching from Wikipedia. Since a maximum matching is also a maximal matching, I assume that this the worst that we can get, a maximum matching of 16 vertices.

How can one improve on the edges picked then? My 16 vertices versus the book's 12?

Let $M$ be a maximal matching, that is, $M$ is a matching which is not contained in a larger matching. Note that $M$ need not be a maximum matching, which is a matching of maximal size.
If $M$ contains $m$ edges, then:

Any vertex cover contains at least $m$ vertices. This is because any vertex covers at most one edge of the matching.

There exists a vertex cover containing $2m$ vertices, namely, all vertices of the matching.  Indeed, if the vertices of the matching $M$ do not form a vertex cover, then there is some edge $e$ which is not covered by the vertices of $M$, and so $M$ is contained in the larger matching $M \cup \{e\}$, contradicting the definition of $M$.