Determine Intersection given only a hyperrectangle and a point-contained-in-shape-Predicate Given only an n-dimensional hyperrectangle by its corner-point-values and an n-dimensional Predicate that corresponds to an arbitrary shape and tests whether a point is contained in said shape,

is it possible to calculate whether the box intersects the shape?

If all you have is a black-box function to test containment in your shape $S$, then the answer is no in general. For example, take $n=2$, let your rectangle $R$ have corners $(\pm1,\pm1)$ and let $S$ be a disk. Note that $S$ can have exactly 1 point of intersection with our rectangle and this can be any point on the boundary of the rectangle. So, since we work over $\mathbb{R}^2$, we have to test an infinite number of points and hence it is impossible. (obviously, if we have a discretized space, the rectangle has a finite number of points and we can simple test all of those.)

So, if you can have an intersection with only 1 point at an infinite number of places, it is impossible. This can happen for a large class of shapes. The first counter-example I can think of is when $S$ is an axis-parallel rectangle with a minimum side-length $w>0$. $S$ can intersect at one point only in the 4 corners. If $S$ does intersect $R$, but not intersect in a corner $S$ must intersect a segment of length $w$ on the boundary of $R$, so we can test $\approx \frac{4}{w}$ values on the boundary of $R$ to find the intersection.

Note that even in this case, you need $O(\frac{1}{w})$ tests to determine intersections. I think this means that unless you make some strong assumptions about $S$ or relax your condition of intersection, this problem is not solvable.


Do modern operating systems use memory control blocks? I was taught in my operating systems class that sections of memory in the heap are marked as free/occupied through the use of memory control blocks (MCB). The generalized definition of an MCB that was given to us is that they hold two memory addresses (one for the next MCB and one for the previous MCB), the size of the block of memory attached to the MCB, and a flag stating whether that block is occupied or not.

When a chunk of memory is requested, the OS finds an unoccupied MCB, marks it as occupied, and creates a new MCB at the end of the now occupied block.

This seems like a sensible way to do things, and yet I cannot find any mention of the term "memory control block" outside of explanations of how DOS tracks memory allocations, even in the textbook Operating Systems Concepts (Silberschatz et al).

I'm confident that some sort of administration is going on, via a simple C++ program that creates several pointers to ints and then prints out the addresses stored by the pointers, which are consistently not consecutive (although I guess this doesn't prove anything for sure).

What's going on behind the scenes? Are MCBs simply called something else nowadays?

This is really a question about memory allocators and doesn't have much to do with operating systems. "Memory control block" does seem to be a DOS specific term for a node in a free list.  I'm not aware of any broadly used term for those nodes. They are usually just called "free blocks" or "unallocated blocks" or some such.

An operating system kernel usually has memory management concerns of its own.  A popular choice for Unix-like systems is slab allocation.  In Linux, there's a variation that is possibly the default nowadays called SLUB, and there is another option called SLOB which stands for "simple list of blocks" which does correspond to a free list approach.

At the lowest levels though, most popular, general-purpose CPUs organize allocation of physical memory with a page table. (More accurately, page tables manage the physical to virtual address mapping.) The kernel still must keep track of which pages of physical memory are allocated and to which process, but the page table structure makes this a bit less flexible. The main point being that pages come in fixed sizes which allows memory allocation techniques built on fixed sized blocks.  In particular, according to Wikipedia, Linux uses a zoned buddy allocator.

So the overall picture looks like this: at the lowest level you have an allocator to keep track of physical pages of memory; above that you have an arena-like allocator motivated by the fact that you often want to allocate many smaller-than-a-page objects and you obviously don't want to allocate a page to each; above that a programming language runtime may have its own memory allocator that may exploit details of the programming language to perform better; finally, an application may do some memory allocation of its own, often also using arenas but now usually motivated by time-cost issues like the costs of allocating/deallocating and data locality.


PAC learning: success of learning when receiving a sample from a different distribution I've come across this question and I think I'm on the right track with the idea I just don't really know how to formalize it properly or understand why everything said in the question is required for the proof. The question is as follows:

Let $\mathcal X$ be a finite example domain and let $\mathcal Y = \{0, 1\}$. Let $H ⊆ \mathcal Y^ \mathcal X$ be a finite hypothesis
class. Let $\mathcal D$ be a distribution over $\mathcal X \times \mathcal Y$. Let $\mathcal G$ be a different distribution over $\mathcal X × \mathcal Y$, such
that $G_{Y |X} = D_{Y |X}$. Suppose that an ERM algorithm $\mathcal A$ receives a sample from $\mathcal G$ instead of
a sample from $ \mathcal D$, that is: $S \sim \mathcal G^m$.
Prove that if $\mathcal D$ and $\mathcal G$ are realizable by $\mathcal H$, and $supp(\mathcal D_\mathcal X) ⊆ supp(\mathcal G_\mathcal X)$, then for every
$\epsilon, \delta \in (0, 1)$, there exists a sample size $m$ (that can depend on $\mathcal D, \mathcal G, \mathcal H, \epsilon, \delta)$ such that
$\mathbb P_{S\sim \mathcal G^m}[err(\mathcal A[S], \mathcal D) \geq \epsilon)] \leq \delta$.

My idea was that since the conditional distributions are equal and the realizability assumption holds it must be that the labeling function for each distribution, say f and g, are the same as well.
Now since the support of D is contained in the support of G, any example that can be observed in the sample drawn from D can also be observed in a sample drawn from G, hence enough examples drawn from G will suffice to achieve a training set S that contains all of the support of D. However, I can't quite formalize this idea.
Thanks in advance!

Let $x_1,...,x_N$ denote the elements of $\mathcal{X}$ and consider the marginal distributions $D_\mathcal{X}=(p_1,...,p_N)$ and $G_\mathcal{X}=(q_1,...,q_N)$. Recall that $p_i>0$ implies that $q_i>0$, hence the ratio $R=\max_i\frac{p_i}{q_i}$ is well defined. Also denote the output of the algorithm on a sample set $S$ by $h_S$, then:
\begin{align*}
err_G(h_S)&=\sum\limits_{i=1}^N q_i\Pr\limits_{(x,y)\sim G}[h_S(x_i)\neq y | x=x_i]=\sum\limits_{i=1}^N q_i\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\\
&=R^{-1}\sum\limits_{i=1}^N q_iR\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\ge
R^{-1}\sum\limits_{i=1}^Np_i\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\\
&=R^{-1}err_D(h_S)
\end{align*}
Thus, to show $err_D(h_S)$ is small with high probability when given samples from $G$, it suffices to show that $err_G(h_S)$ is small and using the bound $err_D(h_S)\le R \cdot err_G(h_S)$ where $R$ is a constant depending on the distributions. This is the standard problem of showing that the ERM is able to learn a finite hypothesis class, so I leave the details to you.


Highest Response Ratio Next (Scheduling Algorithm) In CPU scheduling HRRN(Highest Response Ratio Next) algorithm chooses the next process to be scheduled using the formula (W+S)/S  where W-> waiting time &
S->Service Time. Can someone share their intuition behind this formula? How does this calculate Highest Response Ratio?

It's a variation on Shortest Job Next (SJN) and is an attempt to avoid the starvation problems for estimated long running jobs on busy systems with many short running jobs.

When a job has just hit the scheduling queue it's wait time is zero and it's priority is 1.  As the wait time increases it's priority is increased by a factor weighted by it's ESTIMATED* run time.  Consider 2 processes, one with an estimated run time of 5, the other with 10.  Assuming they are placed in the run queue at the same time, both will have an initial priority of 1.

Process A (s=5)  priority = 1 + 0/5 = 1

Process B (S=10) priority = 1 +  0/10 = 1

As the processes wait, their priority increases proportional to their expected run time, let's say both have waited an interval of 10:

Process A (S=5) priority = 1 + 10/5 = 3

Process B (S=10) priority = 1 + 10/10 = 2

As you can see the priorities of each process increase, but at different rates. After the initial scheduling interval, process A is going to be picked to run before process B.  Once a process is picked to run, its wait time is reset to 0.
Let's assume that process A was picked to run after the previous wait period, but process B had to wait another 10 intervals, and process A became computable again.  The new priorities would be:

Process A (S=5) = 1 + 0/5 = 1

Process B (S=10) = 1 + 20/10 = 3

Assuming other processes with higher priority blocked both processes for another interval of 10 the new priorities become:
Process A = 1 + 10/5 = 3
Process B = 1 + 30/10 = 4

And again both wait 10:
Process A = 1 + 20/5 = 5
Process B = 1 + 40/10 = 5

At this point both processes again have equal priority and either COULD be picked, but on a busy system it's not guaranteed.  If they wait again the new priorities would become:

Process A = 1 + 30 / 5 = 7

Process B = 1 + 50/10 = 6

Again process A becomes the higher priority, but B is still increasing it's priority.  A will be picked first and it's wait again reset to 0, but since B is still accumulating wait time it's priority will keep increasing until it becomes the highest priority on the system and all other processes will have to wait for it to run.

Opinion time:
This seems like a better algorithm than straight SJN, but in practice it could still provide unsatisfactory perceived user response on a busy general purpose system.  Users would perceive a "bursty" system which sometimes gave quick answers, but with long pauses.  I prefer preemptive style scheduling for interactive systems.  For non-interactive systems, this may provide better overall throughput since it reduces expensive context switches.

Note that these are all ESTIMATED run times either based on a default initial value or on the average of the previous estimate and the actual last run time.  This leads to a scheduling problem if the estimate is wildly inaccurate or has a series of short run times followed by a very long run.


Language to regular expression Having difficulty grasping the concept of how a language and a regular expression are related. For example:

(In all cases, the alphabet is $\{0,1\}$)

The language $L = \{100,10,011\}$ ------> Regular expression.

So far, I have:

$(0+1)$ since you can have either $0$ or $1$ in the first part...but...I'm not sure what would follow after that...I've tried making a DFA for it but I feel like I'm overcomplicating it. Any help would be great since I'm fairly confused. Thanks!

If the language is finite like you have given in the question then regular expression is simple just write all string separated by $+$(union).
So $$r = 100 + 10 + 011$$
further you have something common in first two string so
$$r= 10(0+\epsilon) + 011$$

  I feel like I'm overcomplicating it.

For that You need to learn three operators $*$ , $+$ and $.$ properly & understand the language given then It will be easy for you to make a regular expression without making a D.F.A..


Cubical type theory for dummies? I read one of those popular papers on cubical type theory, but no wonder I could only see formulas and diagrams without being able to recognize them at all.

So here's what I want. I want a deep enough explanation of what composition, Kan filling and gluing have to do with homotopy type theory. I don't expect there could be an ELI (insert age) for it but instead define the word dummy in the title as someone having some basic understanding of HoTT and category theory (perhaps, but not necessarily optionally).

A year after and I'm writing one myself.


Are "TM M accepts some string of length greater than 100" and "TM M accepts some string of length at most 100" decidable? I have two questions as in the title:

TM M accepts some string of length greater than 100
TM M accepts some string of length at most 100

Since 1. is infinite, we can rephrase question as "does TM accept a string", which is clearly undecidable and there are many proofs for that.

2nd question on the other hand is finite and all finite languages are decidable.

Is my reasoning correct? I can't find any confirmation of my theories.

I might be wrong ( ignore if you understand it correctly, I am beginner myself ), but I think you are misunderstanding the Rice Theorem. Broadly speaking any non-trivial property of the languages recognized by Turing machines is not decidable. A property is trivial if it holds for all or for none of the languages recognized by Turing machines. There are various posts explaining/regarding the theorem. For example I referred to the answer here How to show that a function is not computable? while learning the theorem. ( Skip to end if you only needed hint )
Coming to your case,  the languages are  $L_1=\{\langle M \rangle \;| \; \text{M accepts some string of length greater than 100} \}$ and $L_2=\{\langle M \rangle \;| \; \text{M accepts some string of length less than equal to 100} \}$
It is not difficult to see that in both the cases you are trying to decide non-trivial properties and thus both $L_1$ and $L_2$  are undecidable. As for your reasoning it is flawed as I commented, because knowing that size of a language is finite and being able to construct a Turing machine deciding it, is different from being able to decide whether an arbitrary Turing machine recognizes a language of finite size.
On a side note you could have approached the problem by first seeing that if both of the languages were decidable, the  halting problem would become decidable which we no is not true.


How do I compute the address of the next element? I have to work on something , but I am making an error that I can not identify. Propably, it is going to sound simple to you but it's my first course on computer architecture and there is nothing in my slides or book.
"We are given a memory, where the smallest chuck of information that can be adressed is 1 byte, and we use 32 - bit memory adresses. Arrays , contain doubles, and each elememnt is an 8 - byte one."
&x[0]=0x0000A100 ."
I want to compute the adresses of &x[i] , i=1,2..
What I did thought was the right approach is:
Since, we have a memory that is byte - adressable then we can do it as such :
&x[i] and &x[i+1] have a dc offset which is  8 -byte and since it is byte adressable then :
&x[i+1] = &x[i] + 8
And I used an online calculator to get these results :

But they are wrong...

The offset should be 4 bytes, since 1 byte is 8 bits and 32 bits contain 4 bytes.


Space and time complexity of $L = \{a^nb^{n^2} \mid n≥1\}$ Consider the following language:
$$L = \{a^nb^{n^2} \mid n≥1\}\,$$

When it comes to determining time and space complexity of a multi-tape TM, we can use two memory tapes, the first one to count $n$, and the second one to repeat $n$ times the count of $n$. Thus, because of the way we’re using the second tape, it should have a $\Theta(n^2)$ space complexity, and I would say the same concerning the time one. I thought it was correct, but the solution is $TM(x)=|x|+n+2$, where, $x$ is, supposedly, the length of the string, hence $\Theta(|x|)$. It seems correct to me, so is my reasoning completely wrong, or just a different way to express it?

Could we have reasoned about it differently, and say, for example, for every $a$ we write down a symbol on the first tape, and then count the $b$'s, by scanning the symbols back and forth $n$ times? This time, the space complexity should just be $\Theta(n)$, while the time complexity should remain unchanged. What would change if we had a single-tape TM?

Your confusion stems from a double use of $n$. Let's write $L$ differently:
$$
L = \{ a^i b^{n-i} : n-i = i^2, i \geq 1 \}.
$$
Here $n$ is the input length. It should be clear that the space complexity is $O(n)$.

Your first estimate just translates to a space complexity of $O(i^2) = O(n)$, since $n = i^2 + i$.


Proving the validity of a sequent using Modus Tollens Problem: Prove $p \rightarrow (q \vee r), \neg q, \neg r \vdash \neg p$ using Modus Tollens.
I need to prove the validity of the above sequent by using natural deduction. Initially, I didn't read the entire problem, and went the long way by doing an implication-elimination, two negation-eliminations, an or-elimination, and finally a negation-introduction. Then I read the problem and realized I had to use MT, and now I'm stuck. I don't have the greatest grasp on propositional logic and natural deduction. Am I allowed to do the following?
Since I have $\neg q$ and $\neg r$ as my premises, can I use an and-introduction and do $\neg q \wedge \neg r$, which would allow me to immediately use MT to deduce $\neg p$? If not, could someone point me in the correct direction? Thanks.

Modus Tollens is the following rule:

Given $A \to B$ and $\lnot B$, deduce $\lnot A$.

In your case, you are given $p \to (q \lor r)$, and so $A = p$ and $B = q \lor r$. Therefore you need to prove $\lnot B = \lnot (q \lor r)$. This is not the same as $\lnot q \land \lnot r$, though the two are logically equivalent. What you have to do is deduce $\lnot (q \lor r)$ from the premises $\lnot q$ and $\lnot r$.


Why in a min priority queue (heap based) it is called "decrease-key" and not just "set-key"? When you call decrease-key in a min priority queue, you are basically setting the key, you can accidentally put a higher key, right? so why isn't it called "set-key" or "update-key"? why (according to Wikipedia and other sources) a min priority queue has "decrease-key" and a max priority queue has "increase-key"? why not have both "set-key" and if you decrease it or increase it, do what you should do to keep the heap property invariant?

I mean what if I call decrease-key on a min heap and give a bigger value? Will it throw an exception? Why not just call it "set-key" and handle any kind of value?

Good question. One of the important applications of the data structure PriorityQueue is in Dijkstra's algorithm. Each node gets a distance from the initial node, which is updated when shorter paths are discovered. Hence updates only change the key in one direction.

The problem in the implementation of DecreaseKey is not that it is only decreasing (rather than updating the value). For a binary heap there are quite efficient methods both for increasing and decreasing. They both swap nodes with other nodes along a path in the tree (either upwards or downwards). The problem is actually knowing where to find the key. You cannot efficiently search for it, so a separate "index" has to be kept. When an update is done along a path, not only the decreased key is changed in the indax, but also the other keys along the path.

For abstract data structures we want to specify only the operations that are important in a particular context. So we have DecreaseKey only, given the Dijkstra motivation. Although for binary heaps extending the operations might be elementary, this might not be the case for other implementations of the PriorityQueue, like Leftist Heaps, Fibonacci Heaps, or Brodal Heaps.

What any particular implementation will do when the new value is in the wrong direction is up to that implementation.


Does expert system use algorithms? I want to build an expert system for analyzing the personality of a number of people and then distribute them in groups , each group will have members with different personalities.

I have been reading about ES a lot but I still confused , does  rule-based system enough to build the system, or do I have to use matching algorithms like stable marriage or Maximum bipartite matching.

Expert systems are called "Experts" for a reason. They are cable of doing a particular job at up most perfection. Not 100% but 99%. Now I am no expert on these systems (pun intended) but as far as these two algorithms go my answer would be to try to boil down to the exact purpose of your system. These two algorithms do two different things. All in all what I am saying is to find an concrete job that your expert system will do. Using the Stable Marriage algorithm you will be ranking and connecting vertices with edges accordingly to their respective weights. As for the Maximum Matching algorithm you will be trying to find the lone vertices and edges. At this point according to your needs I would try to find something in between or edit the Stable Marriage algorithm to fits your needs.

Good luck! You have chosen to tackle a very strong problem ;)


Basis sets for combinator calculus It is well known that the S and K combinators form a basis set for combinator calculus, in the sense that all other combinators can be expressed in terms of them. There is also Curry's B, C, K, W basis, which has the same property. There must be an infinite number of such bases, but I don't know of any others.

I am aware that there are a number of single-combinator bases, such as the Iota combinator and the various others constructed/reviewed by Fokker. However, these are "improper" combinators, meaning that they are expressed in terms of other combinators rather than pure abstractions.1  For the purposes of this question I'm interested only in basis sets composed of proper combinators.

Does there also exist a study of the other possible basis sets? Ideal would be something along the lines of Wolfram's study of various other models of computation, in which the various combinations are studied systematically. In particular, I'm interested in whether simple examples of the following things are known:

A minimal basis set that includes the I combinator. (I'm using "minimal" to mean that if you remove any member it stops being a basis, so the SKI basis would not count.)
A minimal basis set that includes the Y combinator, or the $\omega$ combinator (aka mockingbird)

Any other information about other possible bases for combinatory logic besides S, K and B, C, K, W would be really helpful.

As a broader point, I'm interested in the study of the combinatory calculus as a purely mechanical system, i.e. as a set of transformation rules on binary trees with labelled nodes, which need not be given any particular semantic interpretation. Any pointers towards resources that take this approach would be greatly appreciated. (To Mock a Mockingbird takes this approach but gives an incomplete presentation, whereas Barendregt's the Lambda Calculus is very much tied to semantics, making it hard for me to extract the purely mechanical aspects that I'm interested in.)

1To be precise: in lambda calculus a proper combinator is an expression of the form $(\lambda.x_1x_2\dots P(x_1,x_2,\dots))$, where $P(x_1,x_2,\dots)$ only has $x_1$, $x_2$ etc. as free variables, and does not contain any abstractions. So for example, $(\lambda x y z. x(z z))$ is a proper combinator, but $(\lambda x. x(\lambda y.y) )$ is not, because it contains $x$ applied to a lambda term.

It's easy to make other bases by switching out the combinators from one basis with ones that do something similar. For example, starting with BCKW, you can switch $C$ for $T = (\lambda x y. y x)$ (since both switch terms around) and $W$ for $\omega = (\lambda x. x x)$ (since both duplicate things). You know this is still a basis because you can recover $C$ and $W$ from it: $C = B(T(B B T))(B B T)$ and $W = C(B \omega(B B T))$.


Finding shortest and longest paths between two vertices in a DAG Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time?  Path lengths are measured by the number of edges.

I am interested in finding the range of possible path lengths in polynomial time.

Ps., this question is a duplicate of the StackOverflow question Longest path in a DAG.

For the shortest path problem, if we do not care about weights, then breadth first search is a surefire way.  Otherwise Dijkstra's algorithm works as long as there are no negative edges.

For longest path, you could always do Bellman-Ford on the graph with all edge weights negated. Recall that Bellman-Ford works as long as there are no negative weight cycles, and therefore works with any weights on a DAG.


Deformation of algorithms Has there been any attempt at a general theory to describe how an algorithm can be "deformed" to solve the problem more efficiently?

For example suppose we have an algorithm (say sorting a list of numbers) which solves the problem in $O(n^2)$. Can we deform this algorithm (in the "space of algorithms") to an algorithm which solves the problem in $O(n \log(n))$ time?

My motivation for asking this questions comes from analysis where if we want to solve the equation $f(x) = 0$ one technique is to first guess an $x_0$ such that $f(x_0)$ is small, then look in the neighborhood of that $x_0$ to find $x$.

Of course, I'm guessing the answers is no, but I'm sure a question similar to the above must have been posed somewhere in the literature somewhere.

There is no general way to do this. The "space of algorithms" is not a nice one, with a natural metric or other nice properties, unlike e.g. the real numbers. Note that even in the case of trying to solve $f(x)=0$, where your search space is $\mathbb{R}$, most algorithms work under several assumptions on $f$, e.g. continuity (there is no algorithm which can solve/approximate $f(x)=0$ for an arbitrary $f:\mathbb{R}\rightarrow\mathbb{R}$).

See the answers here, and also here for simple impossibility results regarding a general approach for optimizing the running time of an algorithm.


Why is it that Btrees most of the times have a degree that is odd? What happens if they are even? I was watching a lecture video and the Professor states that it would be very rare to see the order of a Btree to be even. I was hoping for an explanation but he cut it off there and moved on with the lecture.

One thing that distinguishes real-world B-trees from "lecture B-trees" is that real B-trees tend to have nodes and leaves where the size in bytes is fixed. So the "degree" of a B-tree is determined by the number of keys that will fit on a page.

So if the keys vary in size (e.g. strings), the "degree" of different nodes may be different. Roughly 50% of them will have even degree.


Tensor Product in Quantum Computation I can not understand the following equality   $$\langle ij|(|0\rangle \langle 0|\otimes I)kl \rangle= \langle i|0\rangle \langle 0|k \rangle \langle j|I|l \rangle?$$

Also to estimate phase $\phi$ in Nielsen & Chuang book, I can not understand why
$(|0 \rangle + e^{2\pi i 2^{t-1}\phi} |1 \rangle)(|0 \rangle + e^{2\pi i2^{t-2}\phi }|1 \rangle)\cdots (|0 \rangle + e^{2\pi i 2^{0}\phi} |1 \rangle)= \displaystyle\sum_{k=0}^{2^t-1}e^{2\pi i \phi^k} |k\rangle$.

Will you kindly help me?

A tensor product of operations, $I\otimes J$ say, acts on each subsystem separately: if $\phi$ and $\psi$ are states and $I$ and $J$ are operators then
$$(I\otimes J)(\phi\otimes \psi) = (I\phi) \otimes (J\psi)$$
In bra-ket notation the state $\phi\otimes \psi$ can be denoted $|\phi\rangle|\psi\rangle$.
In your first equation, the $\langle i|0\rangle\langle 0|k\rangle$ factor and $\langle j|I|l\rangle$ factor just separate in this way.

The algebra behind the second equation is basically:
$$(1+x^{2^0})\dots(1+x^{2^{t-1}})=1+x+x^2+x^2+\dots+x^{2^t-1}$$
except that the "1" is replaced by $| 0\rangle$, and the $x$ is replaced by $\exp(2\pi i \phi |1\rangle)$ (clash of my notation: $\phi$ is now a number). The only difference is that the multiplication is really a tensor product, and with bosons $|1\rangle\otimes |1\rangle=|2\rangle$.


Computing gaussian kernel for image blurring When I compute a gaussian kernel for image blurring should I normalize the 1D vectors? Because when I apply the raw values sometimes the image gets lighter or darker.
The function I'm using is $f(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{\frac{-x^2}{2\sigma^2}}$ or the 2D function.
So, should I just apply the results using cross correlation/convolution or should I normalize first?

Your function is used to compute 2D kernel, which you should normalize, otherwise if the sum of used weights is higher than $1$ your image gets lighter, when it is smaller it gets darker. You should not normalize vectors, because you apply 2D kernel, so normalized 1D vectors will not help.

The operation that you perform is convolution, not correlation, which in common meaning would try to measure how similar is the part of image to given kernel.


Finding efficient randomized algorithm I'm doing a course on randomized algorithms and
I've encountered a question that I'm struggling to solve.

Given a system of $m$ linear equations with $n$ variables over finite field $\mathbb{F_2}$ where every equation is of form $a_1x_1+...+a_nx_n=b \mod 2$ and $x_i,a_i,b\in\{0,1\}$ and multiplication and sum are $\mod 2$.

First part of the question is to find an efficient randomized algorithm that finds an assignment to the variables over $\{0,1\}$ so that expected value of satisfied equations is $\frac{m}{2}$.  This part is relatively easy, choosing a random assingment over $\{0,1\}$ gives us the desired result. Each equation is satisfied with probability $\frac{1}{2}$ and expected value over $m$ equations will give us $\frac{m}{2}$ satisfied equations.

The second part is the one I struggle with, it is asked to prove that there exist $O(logm)$ assignments to the variables such that every equation is satisfied by at least one assignment. And it is asked to propose a randomized efficient algorithm that finds those $O(logm)$ assignments with probability at least $\frac{1}{2}$. There is also a hint: let $E_i$ be an event that random assignment satisfies equation $i$, then events $E_i(1<=i<=m)$  are $2-wise$ independent.

I really don't know how to approach this. Any help would be appreciated.

You already proved in First part that using random assignments to the values it solves $\frac{m}{2}$ equations in expected value. Moreover, this fact came from knowing that each individual equation will be solved with probability $\frac{1}{2}$ on every random assignment. So we can use the following algorithm to solve this problem:

E = Unsolved equations (initially all equations)
A = {} # Assignments that solves the problem.

while E is not empty:
    a = Random assignment
    SE = solved_by(E, a) # Equations in E solved by assignment a
    if |SE| * 2 >= |E|:
         E = E \ SE      # Remove solved equations
         A = A U {a}     # Add this assignment to the solution

return A

This algorithm will find at most $\lfloor log_2(n) \rfloor + 1$ assignments so that every equation is solved by at least one assignment because condition if |SE| * 2 >= |E| half the size of |E| and add one assignment to A after every success. This will also run in time, since the probability of success is $\frac{1}{2}$, so the expected iterations for success is 2.


If one of the case obeys all rules of Pumping Lemma, can we conclude there is no contradiction? I am studying Pumping Lemma for Context Free Languages, wherein, I am slightly confused in a question where one of the case doesnt obey all rules but another case does. What's the conclusion? Do we call it a contradiction and declare the language is not context free or do we say there is no contradiction?
If its the former, it will declare (a)^n(b)^n as non-context free using Pumping Lemma even though we know its a context free language, since some of the cases will not obey the 3 conditions at the same time.
Edit:
By cases, I mean v and y's existence in different parts of the string. In a string aaaaabbbbb, either v or y could fully be in a, partially be in a and b or fully be in b.  ( Assuming you break the string into S = uvxyz where v and y are the repeating pieces)

This is a common question regarding pumping lemmas, and it is completely answered by carefully understanding the quantifiers in the lemma.
The lemma itself says the following:

For every CFL $L$, there exists a constant $p$ such that for every word $w\in L$, if $|w|>p$, then there exist words $u,v,x,y,z$ such that $w=uvxyz$, and (1) $|vxy|\le p$, (2) $|vy|\ge 1$, (3) for every $i\ge 0$, $uv^ixy^iz\in L$.

Now, the typical usage of the lemma is by contradiction, so we have a language $L$ which we suspect to be not a CFL, and we show the negation of the lemma (read this carefully, and see how we negate the formulation of the lemma):

For every constant $p$, there exists a word $w\in L$ with $|w|>p$, such that for every decomposition $w=uvxyz$, if (1) and (2) hold, then there exists $i\ge 0$ such that $uv^ixy^iz\notin L$.

As you can see, in order to apply the lemma, we can choose the word $w$, but we are given $u,v,x,y,z$. Then, we assume that cases (1) and (2) hold, and deduce that (3) doesn't hold.
It is really important to understand which elements we can choose, and which we need to be given without choice. These correspond to existential/universal quantification.


Is clause learning in SAT parsimonius? I have a model counting program bob.  On some graph coloring formulas, bob got the right answer only after removing clause learning.  That is to say, with clause learning, bob sometimes counts duplicate solutions, while satisfiability remains stable.  This would be big news if true.

I don't know precisely how Bob works, but let's talk about clause learning.
Suppose you have a set of variable assignments, $A$, say $x_1 = 0$, $x_2 = 1$, $x_3 = 0$. This is a single clause in disjunctive normal form:
$$A = \neg x_1 \wedge x_2 \wedge \neg x_3$$
The negation of this set of assignments is a single clause in conjunctive normal form:
$$\neg A = x_1 \vee \neg x_2 \vee x_3$$
So if you have a set of variable assignments that you know you never want to see in any solution, you can add its negation to a SAT problem in CNF and it remains a SAT problem in CNF.
With conflict-directed clause learning, you add clauses which correspond to "dead ends" in the search. Suppose you try some assignments and find that this is not a valid SAT solution. This means that you have identified a CNF clause which is unsatisfiable (i.e. a "conflict"). So if you can find an appropriate subset of assignments that inevitably leads to the dead end, and add its negation as a new clause, this has the effect of directing the search so that it will not get stuck in that dead end any more, while also not changing the solution set.
For model counting, you find a solution to the SAT problem, add its negation as a new clause, and then go try to find a solution to the augmented problem.
It would be big news indeed if adding the negation of a known solution to a SAT problem meant that the solution that you explicitly negated is still a solution. I suspect Bob has a bug.


Smallest set of features that would make relational algebra Turing complete I'm thinking this should be just one or two things, since lambda calculus is so tiny and still Turing complete.

Probably just recursion (something like "MY_QUERY(param) = select * from param UNION MY_QUERY(DO_SOMETHING_WITH(param))"). But I don't see how I could define aggregate functions with this.

Any idea?

You need just two things: new values and recursion/while.

New values means the ability to execute some external function that returns values that were not already to be found in the database. Obviously most implementations (including SQL) have that.

Recursion/while means the ability to execute a loop or iterative computation that may not terminate. The CTE RECURSIVE feature of SQL is one such.

SQL with CTE RECURSIVE is Turing Complete (without stored procedures).

See the Alice book http://webdam.inria.fr/Alice/ for a detailed treatment.


Encode an ascii string in base 15 How can I encode an ascii string in base 15?

In other words, I have the following characters available:

0123456789abcde

I have no idea how to do this. What do you suggest I do?

(If this is not on-topic, please migrate.)

Let's take a different view angle.

The problem is not really about encoding something like "decimals numbers" 0..127 into base-15 (which is messy). It's about converting a base-127 string into base-15. If you can see it that way, then it's just the same principle as with converting from, say, base-16 (hex) to base-10 (decimal), or base-10 to base-2.


RAM and ROM confusion we know RAM contains instruction for we ask computer to do operations
we know ROM contains instructions which for computer to work

does this mean RAM contains address of instruction sitting in ROM?
ROM tell how to add and RAM points to that address of ROM which tells cpu to add

"ROM" stands for "read only memory".  This usually means that you can read any location in ROM, but you can't change what is already in ROM.  (Data in ROM is written when the ROM chip is constructed, or using special hardware operations in exceptional situations.)

"RAM" stands for "random access memory".  In practice, what this means is that you can read any location in RAM, and you can overwrite any location in RAM.  So this differs from ROM in that you are allowed to write into locations in RAM.  (Originally, "memory" could only be accessed in specific locations at specific times.  For example, if all of your storage is on a tape, then you can't read or write locations on the tape that are not under the read/write head; you have to move the tape first.  RAM was better because the access was "random", in the sense that you could easily access any location in RAM at any time.)

Both RAM and ROM can contain any information that can be translated into in binary form.  This can include (a) machine language or assembler instructions, (b) addresses of locations in RAM or ROM, (c) data.  It can include high-level programming language function representations as well.  Whether we call that data or instructions depends on the context.


Please check my answer to a pseudocode CASE statement question This is a pseudocode question in my IGCSE CompSci textbook:

  Use a CASE statement to display the day of the week if the variable DAY has the value 1 to 7 and an error otherwise.

This is my answer to it:

CASE Day OF
    1 : OUTPUT "Monday"
    2 : OUTPUT "Tuesday"
    3 : OUTPUT "Wednesday"
    4 : OUTPUT "Thursday"
    5 : OUTPUT "Friday"
    6 : OUTPUT "Saturday"
    7 : OUTPUT "Sunday"
    OTHERWISE OUTPUT "Day invalid"
ENDCASE

Is this answer correct?

(I realise this is a very rudimentary question for a Year 10/11 CompSci class but I’m homeschooled with no teaching guidance whatsoever. So a big cheers to anyone who would take the time to check my answer for me.)

This problem is about switch-case statements. So, if you can do a pseudo code of such a statement with the case being a DAY variable and the steps are clear, that would be correct.
So, your answer is totally correct and steps are clear. There's no one way of doing pseudo code.

switch(DAY)
  case 1:
    print("Monday")
  case 2:
    print("Tuesday")
  case 3:
    print("Wednesday")
  case 4:
    print("Thursday")
  case 5:
    print("Friday")
  case 6:
    print("Saturday")
  case 7:
    print("Sunday")
  default:
    print("Invalid Day!")

Above is another possible way to a case statement for the DAY variable as your question expects.


Round Robin, confused about how to processes are handled related to arrival order See this picture, in parentheses are (arrival time, execution time required)

Why doesn't the "p5" process is processed before "p6"? Why do p3 and p4 are finished and p5 is executed only after the processes that arrive at "11" are executed?

In round-robin scheduling, every process is put into a big queue as soon as they arrive. When a process gets to the front of the queue, it is treated for some fixed number of time-steps (in your case 3 steps, as I suppose is also what's meant by the text "Quantum = 3"). If the process is not finished when its time is up, it gets stowed in the back of the queue. So when Process 5 is done at step 12, it gets stowed in the back of the queue, behind all the processes that arrived at step 11.


Time complexity of a classical version of Shor's algorithm I'm sorry if this question seems too naive.
I've read the Shor's algorithm of factoring big number using quantum computer on Wikipedia. It says,the key step is to find the cycle of the function defined on positive integers:f(x)=a^x mod N, where a and N are positive integer,and N is very large.

What I would like to do is to analyze the time complexity of this key step using a classical computer.I tried the following: Wikipedia's page on modular exponentiation, I see f(x_0) takes O(N),(or less),and let x_0 = 1 to N takes N*O(N)=O(N^2),which is enough to find the cycle of f(x). This lead to the conclusion that the whole factoring algorithm is in polynomial time on a classical computer,which is not the case as far as I know.

So I must be wrong somewhere.Thanks for any help.

When we say that an algorithm runs in polynomial time, we mean that there is a constant $k$ such that the algorithm runs in time $O(n^k)$, where $n$ is the length of the input as a string. When the modulus $N$ is part of the input, it's specified in binary (or any number system other than unary) so the length of that part of the input is only about $\log N$. Thus, running in time $O(N^2)$ corresponds to running in time $(2^{\log N})^2$, which is not a polynomial in the length of the input.


Communication complexity of string matching let us consider Alice and Bob communicate over channel bit by bit. They have one string over $\{0,1\}^{*}$. Let $x$ (uniformly at random) be the string that Bob have and $y$ be the string that Alice have.  They want to check whether there strings are same or not.

On simple algorithm is exchange $n$ bits one by one. We want to solve this problem with few bits exchanged between Alice and Bob.

My Idea : We will randomly select $k = O(\log {n})$ many bits and exchange only these bits. In this probability of error is going to be less than $1/2^{k}$ (because probability of making error for one bit is 1/2) and as each time we are randomly selecting the bits overall probability of error will be less than $\frac{1}{2^{k}}$.

Question : Is my solution optimal one to solve the problem described above?

By simply exchanging random indices you cannot hope to do better than $\Omega(n)$ communication if you want constant error probability. If the strings differ in only a single bit, and you exchange $k$ indices, then the probability of finding the index in which they differ is $\frac{k}{n}$, so if you want this to be constant you must have $k=\Omega(n)$.

The randomized communication complexity can indeed be reduced to $O(\log n)$, but you're going to need stronger arguments. One way to do this is to encode both words with an error correcting code having a large distance, and then use your algorithm (naive sampling) on the codewords.

To elaborate on the above idea, the choice of code doesn't really matter, as the only property you need in order to make naive sampling work is large distance. One example is using Reed-Solomon, given $s\in\{0,1\}^n$, think of it as a string of length $k$ over $\mathbb{F_q}$, with $q=n$ and $k=\frac{n}{\log n}$. In that case you can think of $s=s_0,...,s_{k-1}$ as the polynomial $P_s=s_0+s_1x+...+s_k x^{k-1}$ over $\mathbb{F}_q$. If $s_1\neq s_2$ then their corresponding polynomials agree on at most $k-1$ points in $\mathbb{F}_q$, which means they will differ on at least $n-(k-1)=n\left(1-\frac{1}{\log n}\right)+1$ points in $\mathbb{F}_{q=n}$.
Thus, with high probability, $P_{s_1},P_{s_2}$ will disagree on a random point in $\mathbb{F}_q$. This protocol requires you to send three elements in $\mathbb{F}_q$ (a point and both polynomials evaluations on it), which results in $O(\log q)=O(\log n)$ communication.

This is only one option, there are many randomized protocols for equality. One example is using a simple public coins protocol, in which both parties share two random strings $r,r'\sim U_n$, and exchange the values of $\langle xr,r'\rangle, \langle yr,r'\rangle$. This succeeds with probability $\frac{1}{2}$, and you can turn it into a private coin protocol with logarithmic overhead in communication, see these notes for details. Another option is to choose a prime $p\le poly(n)$ at random, and exchange $x,y\bmod p$. If $x\neq y$ then with high probability $p$ will not divide $x-y$.


Is the complexity of this algorithm O($\sqrt{n}$) or linear? Let's say I have two identical jars and I want to find the height that the jars will breaks when dropped from various heights. I can drop the jars from height increments using steps on a staircase. I want to solve this problem sublinearly.

I decided to increment using square numbers (1, 4, 9, 16..etc) for a complexity of O($\sqrt{n}$), where n is the number of steps on the stairs, so I know that I have an upper and lower bound once the first jar breaks. If the jar breaks at 16, I know that the height that it breaks at is between 9 + 1 and 16. If I were to run the algorithm linearly (on the second jar) from 10 to 16, would this make my algorithm linear?

No, it would not make the algorithm linear. The worst-case scenario would be $n = m^2 + 1$, where $m$ is some positive integer. In this case, you have an additional $(m+1)^2 - m^2 = 2m + 1$ many tries (since the next square after $m^2$ is $(m+1)^2$ and $n < (m+1)^2$), which is roughly equal to $2\sqrt{n} \in \Theta(\sqrt{n})$.


Efficient computation of Kronecker product Given matrices $A \in \mathbb{C}^{n_1,m_1}, B \in \mathbb{C}^{n_2,m_2}$ a naive way to computer the Kronecker product would be as such:

$M = \operatorname{zeros}(n_1n_2,m_1m_2)$ (initialize an empty array)
    For $p = 1,2,\ldots n_1n_2:$
        For $q = 1,2,\ldots m_1m_2:$
            $M_{p,q} = A_{{\lfloor {{p}{n_1}} \rfloor},{\lfloor {{q}{m_1}} \rfloor}} B_{p \bmod n_2,\  q\bmod m_2}$

Which will have running time $O(n_1n_2m_1m_2)$.

I was wondering if there is a more efficient way to computer $M$?

Thanks!

You cannot fill a matrix with $n_1 n_2 m_1 m_2$ entries in time faster than $\Theta(n_1 n_2 m_1 m_2)$. Some considerations:

There may be a way to reduce the number of multiplications (FFT?) by using extra additions, but it won't improve the asymptotic complexity;
This is easy to parallelize;
You can do this on-the-fly, i.e. store the matrix M as "Kronecker product of A and B" and perform the multiplication only after a request for an element M[p,q].
Conceptually you can forget about the rectangular shape of a matrix and think about the situation where you have two vectors $\left[x_1,...,x_k\right], \left[y_1,...,y_m\right]$ and want to compute $k \cdot m$ products $x_i y_j$ for each $i,j$.


Checking whether union of two languages is regular How to check if

$L = \{c^ka^nb^n \mid k>0 \wedge n\geqslant0\} \cup \{a, b\}^*$

is regular ,where

$L_1 = \{c^ka^nb^n \mid k > 0 \wedge n\geqslant0\}$ is clearly not regular and $L_2 = \{a, b\}^*$ is... ?

If $L$ were regular than so would the following language be:
$$L \cap ca^*b^* = \{ ca^nb^n \mid n \geq 0 \}.$$
You can show that the latter language is not regular in various ways.


Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized Problem is as following:

We are 8 trumpet players in an orchestra.

There are for example 4 parts so there are always two players on the same part.

Now, there are not always the same two players playing the same part meaning the combination of players that play the same part change from piece to piece.

What is the cheapest way in terms of distance and/or the least amount of switches resulting that the players playing the same parts can sit next to each other on every piece?

Trumpet Players:
 a,b,c,d,e,f,g,h

Parts: 1,2,3,4

Seats are arranged like that:

1st piece
| a1 | b1 | c2 | d2 |

| e3 | f3 | g4 | h4 |

Next piece the players might play the following parts:
| a2 | b1 | c3 | d1 |

| e3 | f4 | g2 | h4 |

and the next one againt different distribution of the parts:
| a4 | b3 | c1 | d3 |

| e2 | f4 | g2 | h1 |

how do we seat the players so that the least amount has to be traveled in order to reach the desired positions for the players playing the same parts to sit next to each other in the next piece?

additional notes:
i dont care where the pairs are starting and if a1 sits left of b1 or the other way around.

I would suggest using the A* algorithm.  The state is where each player is currently seating and the number of pieces you've played so far.  Each edge represents a way that you can update the seating.  Also, when you're in a state where, for the next piece to be played, everyone is sitting next to their partner on that piece, you can increment the number of pieces played at 0 cost.   The start state has 0 pieces played, and the goal state is any state where you've played all the pieces.   Then, A* will find the lowest-cost sequence of movements to complete the concern.

You'll need an admissible heuristic to estimate the cost to finish the concert, starting from a particular intermediate state.   One very simple heuristic is: count the number of players who will have some future piece to play, where they're not currently sitting next to their partner on that piece, and divide by two.  Perhaps a slightly better heuristic is to count, for each player, the number of future partners (for any piece not yet played) who they are not currently sitting next to, and divide by four.  Assuming each switch costs one and there is no other way to update the seating, this is admissible, as each switch can only decrease this count by at most four.


Maximum Schedulable Set Zero-Lateness Deadline Scheduling This is a homework problem for my introduction to algorithms course.

  Recall the scheduling problem from Section 4.2 in which we sought to
  minimize the maximum lateness. There are $n$ jobs, each with a deadline
  $d_i$ and a required processing time $t_i$, and all jobs are available to be
  scheduled starting at time $s$. For a job $i$ to be done, it needs to be assigned
  a period from $s_i \geq s$ to $f_i$ = $s_i + t_i$, and different jobs should be assigned
  nonoverlapping intervals. As usual, such an assignment of times will be
  called a schedule.

  In this problem, we consider the same setup, but want to optimize a
  different objective. In particular, we consider the case in which each job
  must either be done by its deadline or not at all. We’ll say that a subset $J$ of
  the jobs is schedulable if there is a schedule for the jobs in $J$ so that each
  of them finishes by its deadline. Your problem is to select a schedulable
  subset of maximum possible size and give a schedule for this subset that
  allows each job to finish by its deadline.

  (a) Prove that there is an optimal solution $J$ (i.e., a schedulable set of
  maximum size) in which the jobs in $J$ are scheduled in increasing
  order of their deadlines.

  (b) Assume that all deadlines $d_i$ and required times $t_i$ are integers. Give
  an algorithm to find an optimal solution. Your algorithm should
  run in time polynomial in the number of jobs $n$, and the maximum
  deadline $D = \max_i d_i$.

I've solved the problem as worded with the recurrence

$Opt(i, d) = \max\left \{
\begin{array}
 \\ Opt(i-1, d-t_i) + 1 \hspace{20 mm} d\leq d_i
 \\ Opt(i-1, d)
\end{array}
\right \}$

but our instructor added a new requirement that our algorithm must not be dependent on D. This recurrence seems like it would produce an $O(nD)$ running time if implemented with dynamic programming.

I can't figure out how to reduce its running time from $O(nD)$ to $O(n^k)$. To me it seems like it's a variation on the knapsack problem with all values equal to 1. In which case it seems like this is the best that can be done.

If I'm doing something wrong could someone point me in the right direction, or if I've done everything right so far, could someone at least give me a hint as to how I can make an $O(n^k)$ recurrence or algorithm.

Use a dynamic programming algorithm to compute an $n \times n$ table $T$, where the entry $T(j,k)$ answers the question: suppose you wish to schedule $j$ out of the first $k$ jobs. What is the earliest time you can complete processing these?

How do we compute $T(j,k+1)$? Either the job $k+1$ is included in the best set of $j$ out of $k+1$ jobs, so $$T(j,k+1) = T(j-1,k) + t_{k+1},$$ or job $k$ is not included in this set, so $$T(j,k+1) = T(j,k).$$ We also have to worry about the deadline. We can do this by making the entries of $T$ where the task is impossible equal to $\infty$, and checking whether we have exceeded the deadline at every step. So the pseudocode for computing the $T(j,k+1)$ entry of the table is

if T[j-1,k] + t[k+1] > d[k+1]
    then T[j,k+1] = T[j,k]
    else T[j,k+1] = min ( T[j,k-1]+t[k+1], T[j,k] )

We initialize by setting $T(j,k) = \infty$ if $j > k$, and $T(1,1) = \infty$ if $t_1 > d_1$, and $T(1,1) = t_1$ otherwise.


Priority queue with ubounded number of elements (i.e., with dynamic storage) I'm looking for a data structure that can work as a priority queue with reasonable maintenance complexities (like $O(\log n)$ for insertion and deletion) and that has a theoretical unbounded limit for its number of elements (like a tree structure, that is bounded only by the computer's available memory, and unlike a traditional heap, that uses an static array, which is too costly to augment).

The reason is that I'm implementing a program that makes use of a priority queue and I don't know a priori how many elements I'm going to insert in this queue at once, so sometimes I'm out of space to add another element.

There is no way to estimate this number, and to create a huge array to support a static type of queue is a terrible option, as maybe not even a half of it will be used and I'll be short on memory to allocate other objects.

I've heard of something like a Dynamic Heap (or something in the like) that is some sort of linked list of arrays, whose elements are dynamically allocated when needed, but I'm not sure this is the best strategy to follow, moreover, I would like to know if there were other options.

Just for the record, I'm implementing a Branch-and-Bound algorithm for solving a linear integer optimization problem, with each node stored on the queue being the abstraction of an active node on the algorithm. The number of active nodes cannot be estimated at any time, so a theoretically unbounded queue would help a lot.

I don't understand your claim that a traditional heap is too costly to augment. If the heap is currently of size $N$ and the $N+1$st element is inserted, allocate a new array of size $2N$ and copy the old heap into its prefix. This takes amortized constant time. You can also shrink the heap in this way, for example if it is only half full you can shrink it to two-thirds of its size.


How to teach random number generator algorithms? How can I teach random number generator algorithms? I'd like to show how seeding makes randomization closer to truly random.

Details of the task to be given are as follows:

  Code should read a text file. The file has random words (one word on each line). This is the dataset from which words will be selected randomly.

I am unsure of how to explain the difference between deterministic randomization and non-deterministic randomization using the above example.

So much depends on the language or library you are using. If the tool you are using allows feeding a specific seed I would start by demonstrating how using the same seed gives the same set of random numbers each time. If not and the tool uses the system time as the seed, as many do, then create several random data sets if a very tight look and show how they are the same.

This cre3ating several random sets in a tight loop is something students often do by accident BTW. It gives them no end of trouble as they see identical numbers for all of them.

Then demonstrate how the same code gives different (from the first example) random numbers when used with a different seed.

With your example, using a random number from the same seed would return the same word every time. Using a time based seed should normally return a different word each time.

BTW random.org is a useful/interesting site on the topic. They go into some detail on random and pseudo-random numbers at https://www.random.org/randomness/


Is L={|M is a TM and L(M) is uncountable} decidable? Is $L=\{\langle M\rangle\mid \text{$M$ is a Turing machine and $L(M)$ is uncountable}\}$ decidable?

My intuition is that it is not, but I'm not sure if Rice's Theorem applies in this case. If it is not decidable, how can I prove that using reducibility?

This is somewhat of a trick question. What you are missing is that there are no uncountable languages over a finite (or even countable) alphabet. This should be enough information to answer it.

(I initially gave the entire answer away, but edited it out after considering a bit.)


SAT solvers for use in $P^{NP}$ and $NP^{NP}$ The original question I am answering:

Can you use SAT solvers to solve problems complete in $\Sigma_2^P,\Pi_2^P,\Delta_2^P$?

My first thought:

Venn Diagrams show that the PH encloses NP, but does not equal NP. Therefore, there should be some problems that cannot be solvable using SAT?

My second thought:

To be able to use a SAT solver on one of those PH classes, it would imply that they are reducible to SAT, and so $\Sigma_2^P = \Pi_2^P = \Delta_2^P = \mathsf{NP}$.

This would imply that PH collapses to NP, which we know not to be true.
Are these thoughts correct?

We don't know that PH doesn't collapse to NP. We don't even know that PH doesn't collapse all the way to P.
The best you can say is that you can use SAT solvers to solve problems in one of these classes iff PH collapses to NP.


Calculating match % and ranking according to that I'm creating a website like where users will answer some yes/no questions set by me, up to them how many of those questions they want to answer. After a user submits his answer(s), he will be shown top 5 matches along with their match percentages. If two users have 10 common questions and their answers match for 8 of those questions then their match % will be 80%.

I can make this but my concern is about efficiency. A way of making this: If a user wants to see his top matches then match % (or match ratio) will be calculated for him vs every other user in the system. This will be stored in a temporary array. Array is sorted. Top 5 matches from the array are displayed.

Any less resource intensive way to calculate and show top matches?

Edit: If the top matches can be calculated without first calculating match percentages then i'm open to that.

There is probably no algorithm that is significantly better than doing a pairwise comparison between all pairs of users.

You can, as you say, memoize (remember) the top-5 match for each user, so that you never have to recompute the top-5 for that user again in the future, but you'll still need to compare that user to each other user at least once.  Basically, each time a new user appears, you compare them to all other users, to compute their top-5 matches (and update the top-5 matches of other users by adding this user to the top-5 lists of other users where appropriate).

That's basically the brute-force algorithm.  I don't expect there to be an alternative that is better in practice.

In principle, there are a variety of methods.  One method is to use a locality-sensitive hash.  The simplest form of LSH is to choose a random subset of questions, then for each user extract their answers to those questions, hash that, and store the user in a bucket associated with the user's hash value.  Then two users who are very similar have a decent chance of ending up in the same bucket.  If you construct 100 such data structures, each with a different subset of questions, and if you choose the parameters right, you might have a decent chance of finding all of the top-5 matches in this way (along with some other extraneous matches, but those can be filtered out by doing a full comparison for each potential match).  However, this is pretty fiddly with respect to parameters, and if people tend to answer only some of the questions, I suspect it won't perform that well in practice.


Shor's algorithm and offset elimination I am wondering if the second Quantum Fourier Transform (QFT) in Shor's algorithm is necessary. I am probably missing a point but it seems that an offset elimination function would suffice to determine the period?

QFT eliminates the offset value and it changes the period from r to M/r, where M is a sufficiently large value >> r^2. What we do normally is to take a measurement and get a multiple of M/r. Doing this a couple of times we take the GCD of those measured values and obtain M/r, and then it is easy to obtain r from it.

But is changing the period necessary if there is no offset? Suppose that the period we are looking for is, say 5. Given a superposition with non-zero values only on the multiples of 5, we have a periodic sequence with period 5. Make a measurement and obtain a random multiple of 5. Do this constant number of times. Since all measured values will be multiples of 5, can't I determine r from it by finding their common divisor? So why do we need QFT? Isn't just an offset elimination function sufficient to find the period?

Yes, if you could consistently eliminate the offset then that would be enough. But how are you going to do that?

The state's offset is the discrete logarithm of the value in the ancilla register. But you don't know how to compute the discrete logarithm efficiently classically. And the offset changes from sample to sample. And there are so many possible offsets (assuming you picked a big number to factor) that you won't see the same one twice.


How can an algorithm have exponential space complexity but polynomial time complexity? For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback problems". It is said that it runs in polynomial time but uses exponential space in a dictionary.

insert F_q into Q and into D;
while Q is not empty do
  remove any set F from Q;
  output F;
  for each uG-successor F′ of F do
    if F′ is not contained in D
      insert F′ into D and Q;
    fi
  od
od

How can this be? Does an exponential number of insert operations to the dictionary not inevitably imply exponential time?

This algorithm doesn't run in polynomial time, it runs with polynomial delay. As the paper notes:

  Observe that the number of minimal, and even minimum solutions, can be
  exponential in the size of the graph; Fig. 1 gives an example.
  Therefore, the total running time of any enumeration algorithm cannot
  be expected to be polynomial in the size of the graph.

The paper goes onto explain the concept of polynomial delay,

  However, certain enumeration algorithms for other combinatorial
  problems work with polynomial delay, i.e., the algorithm performs at
  most a polynomial number of steps before the first and between
  successive outputs.

What's polynomial isn't the entire runtime of the algorithm, its the time between successive outputs. Since the algorithm can output an exponential number of items, the total run time can quite easily be exponential.

When it comes to memory, the paper states:

  Note that memory requirements are polynomial for graphs with a
  polynomial number of MFVS, but potentially exponential for the general
  case.

Memory goes exponential if we have an exponential number of outputs. But in that case, there is an exponential amount of time passing to fill up that amount of memory as well.

Put another way, memory is exponential because we are measuring memory usage over the entire enumeration process. Time is polynomial because we are only measuring time between two outputs.


Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$ I'd really like your help with proving the following.

If $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$.

Here, $\mathrm{NTime}(n^{100})$ is the class of all languages which can be decided by nondeterministic Turing machine in polynomial time of $O(n^{100})$ and $\mathrm{DTime}(n^{1000})$  is the class of all languages which can be decided by a deterministic Turing machine in polynomial time of $O(n^{1000})$.

Any help/suggestions?

Here is the solution using padding. Suppose $L \in \mathrm{NTime}(n^{1000})$. Define a new language $L' = \{x0^{|x|^{10}-|x|} : x \in L\}$. Each $x \in L$ corresponds to some $y \in L'$ of length $|y| = |x| + (|x|^{10}-|x|) = |x|^{10}$. Therefore we can decide whether $y \in L'$ in non-deterministic time $|x|^{1000} = |y|^{100}$, i.e. $L' \in \mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$. In order to decide whether $x \in L$, form $y = x0^{x^{10}-|x|}$ and run the $|y|^{1000} = |x|^{10000}$-time deterministic algorithm for $L'$. We conclude that $L \in \mathrm{DTime}(n^{10000})$.


How to devise an algorithm to arrange (resizable) windows on the screen to cover as much space as possible? I would like to write a simple program that accepts a set of windows (width+height) and the screen resolution and outputs an arrangement of those windows on the screen such that the windows take the most space. Therefore it is possible to resize a window, while maintaining  output size >= initial size and the aspect ratio. So for window $i$, I'd like the algorithm to return a tuple $(x, y, width, height)$.

I believe this is might be a variation of 2D Knapsack. I've tried going over results around the web but they mostly had a lot of background (and no implementation) that made it hard for me to follow.

I'm less interested in the fastest possible algorithm, but more in something that is practical for my specific need.

Although your question does not say it, I'm assuming that you do not want windows to overlap.

One approach to this problem is to use a constraint solver such as Choco. One simply writes down the constraints encoding your problem, tunes the solver to act in a smart way, and then let it run. This means that all the thinking you need to do will be spent on finding a good way of encoding the problem, not on devising an algorithm and doing the programming and tuning. Here is a partial answer to get you started.

Assume that the screen size is by $x_{max}\times y_{max}$.

For each window, $W_i$, you'll have a set of variables $x_i, y_i, h_i, w_i$ and constraints

$x_i,y_i,h_i,w_i\ge 0$
$x_i + w_i \le x_{max}$
$y_i + h_i \le y_{max}$
Perhaps also some constraints on the minimal size of windows, e.g., $h_i\ge 100$ and so forth.
Aspect constraints: If aspect ratio is 3:4, the constraint could be something like $4h_i - \epsilon \le 3 w_i \le 4 h_i + \epsilon$, where $\epsilon$ is some small non-zero error term to allow for non-perfect window sizes, as otherwise you'd over constraint the problem.

Now you need to take care of window overlap. For each pair of windows, $W_i, W_j$, where $i\neq j$, you'll generate constraints like the following, which capture that no corner of $W_j$ appears within $W_i$. For $(x,y)\in\{(x_j,y_j), (x_j+w_j,y_j), (x_j,y_j+h_j), (x_j+w_j,y_j+h_j)\}$, generate constraint:

$\neg(x_i \le x\le x_i + w_j \wedge y_i\le y \le y_i+h_j)$.

The constraints specified thus far only describe non-overlapping windows that do not spill over the sides of the screen, that satisfy some minimal size constraints, and that preserve their aspect ratio.

In order to get a good fit, you need to specify a metric that captures what it means to be a good layout. One possibility is to assume that you want to keep windows roughly equal in size and/or that you want to minimize "white space". I do not think that this can be specified using Choco, but it may be possible with another constraint solve (someone else might be able to help here).

Choco does allow one to maximize wrt to an objective function specified as a single variable.
Based on this idea, you could maximize the following:

$\sum_i (h_i + w_i)$

by writing a constraint $\mathit{cost}=\sum_i (h_i + w_i)$ and telling Choco to maximize $\mathit{cost}$.


In C++ how does "sizeof(array)/sizeof(array[0])" give the number of elements in an array? Why isn't it affected by the length of each element? I'm playing around with C++ and was looking at how to loop through an array of unknown length. The following code was suggested and works perfectly from the little testing I've done:
std::string words[5] = {"Lorem ipsum dolor sit amet orci aliquam.", "Hi", "Welcome", "World", "LoopyDoopyDoo"};
for (int i = 0; i < sizeof(words)/sizeof(words[0]); i++){
     DO STUFF
}

From what I've read the sizeof() operator returns the size of a variable in bytes.
What I don't understand is how this isn't affected by the number of characters in each element of the array. I printed out the sizeof() value to check and the array size is always evaluated at 160 bytes and element 0 as 32 no matter how many characters are present. I thought that it might be allocating 32 bytes but not using them all so I stored some text that should use 40 bytes, but still no change. Am I missing something here? Is text stored differently in C++?
Any help in understanding how this actually works would be appreciated, thanks!

C and C++ are low-level languages that give the programmer precise control over the memory layout. Each object takes a constant amount of memory which is fully determined (on a given implementation) by its type. The sizeof operator lets programs know this size.
An object may contain pointers. The data that the pointers points to, if any, is not part of the object. The size of an object is what some higher-level language might call the “shallow” size: it only considers the object itself, not other objects that the object references.
For example, an object of type std::string has a certain size. This size is independent of the content of the string. This means that the only way to implement std::string for strings of unbounded length is for the std::string object to contain a pointer to the actual content of the string. sizeof(std::string) is the size of this pointer plus other data that the std::string type keeps track of (that would typically be the length of the string, the size allocated for the string, a pointer to the class's method table). It has no relation with the length of the string.
An array is an object which consists of several objects of the same type. Since the elements of the array all have the same type, they all have the same size.


Streaming algorithm and random access Consider an array $X$ of $n$ cells, each containing a number from $\{1,..., n\}$. There is at least
one duplicate number, i.e., a number that appears at least twice. I want output some duplicate number. When streaming we may pass over $X$ more than once. The inspection of a cell generates cost $1$. The cost of a run of an algorithm is the sum of all individual costs. I can at most store $\log_2n$ bit numbers.
I tried to do that with a streaming algorithm that uses additional memory $O(1)$ with costs $O(n^2)$. Is it possible to state a ramdom access algorithm that uses additional memory $O(\log_2n)$ with costs $O(n)$?.

Which algorithm solves the problem by using additional memory $O(1)$ with costs $O(n^2)$?.
Which algorithm solves the problem by using additional memory $O(\log_2n)$ with costs $O(n)$?.

My problem is similar to the cycle detection problem, but I don't know how to use the cycle detection problem to solve mine. Is there maybe a simpler way that I can't see now?

Here's how to reduce your problem to cycle detection. Your array is a mapping $f$ from $[n]$ to $[n]$. From each starting point $x$, you can iterate $f$. Using a cycle detection algorithm, you can either find out that the iterates of $x$ form a cycle, or find two iterates that map to the same point (your duplicate). For some starting point, you will find a duplicate.


What are some of the practical applications of CSP process algebra? CSP is used for the description and representation of concurrent systems, how it is used in practice (theoretically and programmatically)?

What are the application areas (other than concurrent and parallel systems) where it is used?

CSP is the formal basis of the programming language Occam which compiled to INMOS Transputers. Transputers appeared in all sorts of devices, such as set-top boxes for satellite TV. Eventually, however, the company doing all of this work failed to achieve commercial success, and was eventually absorbed by another company.


Some questions about the Computability of Turing Machines I'm learning for a test and I have some important questions about Computability of deterministic and non deterministic Turing Machines.

Consider we have the partial functions $f,g,h,t: \mathbb{N} \rightarrow \mathbb{N}$ with $f$ is Turing Machine computable, $g$ not Turing Machine computable, $h$ is not While solvable and $t$ is While computable. Are the following answers correct? And is there anything changing if we had an non deterministic TM?

There is no proof to do words are ok :)

Is $f \circ g$ Turing Machine computable?
Is $g \circ f$ Turing Machine computable?
Is $t \circ h$ While computable?
Is $h \circ t$ While computable?

My answers:

First of all, we know that Turing Machine = While Computability. (#)

I would say, that we do not know if it is or is not TM computable, because there may a TM who can handle the output of an not TM computable function.
I would say no, because if whatever $g$ takes, it won't be TM computable.
and 4. Because  of (#) it is the same like 1. and 2.

Could that be right? It is for an multiple choice test and those questions are tricky.

The answer is "we don't know without more information" for all 4.

Suppose $f$ is the identity function $f(x) = x$. Then $f \circ g = g \circ f = g$, which is non-computable.

On the other hand, suppose $g$ is a total non-computable function (which is a special case of $g$ being a partial non-computable function), and suppose $f$ is the constant zero function $f(x) = 0$. In this case:

$f \circ g$ is the constant zero function, which is obviously computable.
$g \circ f$ is also a constant function. We don't necessarily know what the constant is, but that doesn't matter; every constant function is computable. See How can it be decidable whether $\pi$ has some sequence of digits?

Deterministic vs. non-deterministic Turing machine doesn't affect the answer, because a deterministic Turing machine can simulate the execution of a non-deterministic Turing machine (potentially with an exponential slowdown) by dovetailing.


Parallelization of priority queue-based algorithms There's a number of algorithms that operate by maintaining and consuming a priority queue of "events". I'm thinking primarily of geometric algorithms, particularly sweep-line algorithms like Bentley-Ottmann and Fortune's algorithm, but also things like Dijkstra's algorithm and Prim's algorithm.

There's no trivial way to parallelize these algorithms: In non-degenerate cases there's exactly one event which is legal to process. One could speculatively distribute the next n events to n processors, but (a) handling them in any interleaved order would generally violate the algorithm's invariants, and (b) would often add new events to the priority queue which should have been handled earlier.

Nevertheless, for things like sweep-line algorithms, there's a natural locality to exploit. Handling two events which are close to each other along the sweep axis but far away on the perpendicular axis would probably be okay as long as the underlying state structure could be concurrently updated, and one could imagine either speculatively handling those events and rolling back only when interactions were detected, and/or partitioning a prefix of the queue into mutually independent workloads.

Are there any articles which explore this sort of approach, either for specific problems or for paradigms like sweep-line algorithms?

Two old, but, I think, still very useful resources:

M.T.Goodrich, M.R.Ghouse, and J.Bright. Sweep Methods for Parallel Computational Geometry. Algorithmica (1996), 15:126-153. - closely related to what you are asking about, download for free: link.
S.G.Akl, K.A.Lyons. Parallel Computational Geometry. Prentice-Hall, 1993 - monograph about first ten years of research in parallel computational geometry. In the Chapter Four they say: "The plane sweep technique appears to be inherently sequential", but nevertheless refer to a number of parallel sweeping algorithms. Please see: link.


What is a quotient structure? I was reading a paper here, and it mentioned "quotient structure" in the following sentence (third page, second paragraph of the paper)

  In order to obtain a representation of terms truly isomorphic to
  λ-terms, we need to build a quotient structure, quotient the set of
  raw terms with respect to alpha-equivalence. This construction based
  on a quotient corresponds very closely to the of presentation from
  standard textbooks on λ-calculus.

I am hoping that someone could point me a good tutorial on quotient structures.

It's a term coming from abstract algebra. When you quotient a set $S$ with respect to some equivalence relation $\sim$, you are replacing the set $S$ with its equivalence classes under $\sim$. Often the set $S$ has operations defined on it, and in that case we want these operations to be well defined for the quotient $S/\sim$, in the sense that if $x_i \sim y_i$ then $x_1 \circ x_2 \sim y_1 \circ y_2$. This allows us to define $\circ$ on the quotient.

An example in real analysis is $L^p$ spaces, in which functions are defined "up to measure zero".


Early Deadline First (EDF) scheduling in real-time systems feasibility test proof I am trying to prove Theorem 6.2 on page 127 of the book Real-Time Systems by Jane W. S. Liu: http://www.cse.hcmut.edu.vn/~thai/books/2000%20_%20Liu-%20Real%20Time%20Systems.pdf
It is based on Early Deadline First(EDF) scheduling.
It says the proof is similar to the proof for Theorem 6.1 on page 124-126. However, I am still stuck.
Here is what I have so far:
Density of task $T_j:\ \delta_j=\frac{e_j}{\min{\left(D_j,p_j\right)}}$
Density of the system: $∆=\sum_{j=1}^{n}\delta_j=\sum_{j=1}^{n}\frac{e_j}{\min{\left(D_j,p_j\right)}}$
$e_j$ is the execution time for task $T_j$
$D_j$ is the deadline for task $T_j$
$p_j$ is the period for task $T_j$
$\emptyset_j$ is the phase for task $T_j$
$r_{j,b}$ is the release time for task $T_j$ at period $b$
$J_{j,b}$ is the job for task $T_j$ at period $b$
$\emptyset_j=r_{j,1}$
$r_{j,b}+p_j=r_{j,b+1}$
THEOREM 6.2. A system $T$ of independent, preemptable tasks can be feasibly scheduled on one processor if its density is equal to or less than $1$.
If $D_j<p_j$ for some $j$, then $∆=\sum_{j=1}^{n}\frac{e_j}{\min{\left(D_j,p_j\right)}}\le1$ is only a sufficient condition so we can only say that the system may not be schedulable when the condition is not satisfied.
I try to prove the contrapositive just as Theorem 6.1 on page 124-126. So what I try to prove is that if according to an EDF schedule, the system fails to meet some deadlines, then its density is larger than $1$.
Suppose that the system begins to execute at time $0$. And at time $t$, the job $J_{i,c}$ of task $T_i$ misses its deadline. Assume the case that the current period of every task begins at or after $r_{i,c}$, the release time of the job that misses its deadline. We use $t$ to divide two types of task besides task $T_i$ as in below figure: 1) tasks with deadline happens before $t$ in the current period just like $T_f$, 2) tasks with deadline happens after $t$ in the current period just like $T_k$.

$J_{i,c}$ misses its deadline at $t$ tells us that any current job whose deadline is after $t$ is not given any processor time to execute before $t$ and that the total processor time required to complete $J_{i,c}$ and all the jobs with deadlines at or before $t$ exceeds the total available time $t$. So we have
$t<\left\lceil\frac{\left(t-\emptyset_i\right)}{p_i}\right\rceil e_i+\sum_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset_k\right)}{p_k}\right\rfloor e}_k+\sum_{f\neq i,f\neq k}{\left\lceil\frac{\left(t-\emptyset_f\right)}{p_f}\right\rceil e}_f$
then
$t<\left\lfloor\frac{\left(t-\emptyset_i\right)}{p_i}\right\rfloor e_i+e_i+\sum_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset_k\right)}{p_k}\right\rfloor e}_k+\sum_{f\neq i,f\neq k}{{\left\lfloor\frac{\left(t-\emptyset_f\right)}{p_f}\right\rfloor e}_f+\sum_{f\neq i,f\neq k}\ e_f}$
And it is
$=\left\lfloor\frac{\left(t-\emptyset_i\right)}{p_i}\right\rfloor e_i+\sum_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset_k\right)}{p_k}\right\rfloor e}_k+\sum_{f\neq i,f\neq k}{{\left\lfloor\frac{\left(t-\emptyset_f\right)}{p_f}\right\rfloor e}_f+\sum_{f\neq k}\ e_f}$
$\le \left(\frac{t}{p_i}\right)e_i+\sum_{k\neq i,k\neq f}{\left(\frac{t}{p_k}\right)e}_k+\sum_{f\neq i,f\neq k}{{\left(\frac{t}{p_f}\right)e}_f+\sum_{f\neq k}\ e_f}$
$=t\sum_{h=1}^{n}\frac{e_h}{p_h}+\sum_{f\neq k}\ e_f$
$\le t\sum_{h=1}^{n}\frac{e_h}{\min{\left(D_h,p_h\right)}}+\sum_{f\neq k}\ e_f$
$=t∆+\sum_{f\neq k}\ e_f$
So I prove up to $t<t∆+\sum_{f\neq k}\ e_f$
but I cannot prove $∆>1$

I might be too focus on the algebra. I believe I only need to argue or proof a scenario that would give the least density of the system that will fail to meet a deadline.
As shown in the figure below, all tasks start at the same time with same period and deadline. For each of period, each task only have time slot D=D1=D2=...=Dn to execute. In other words, they share exactly the same time slot to execute. If density > 1 then obviously schedule will fail. If the below system has a density of $1^+$(greater than 1 by the smallest amount), then any changes on Di or Pi will only increase the density of the system or make the system feasible.


Maximal size of a set of ordered words such that no pair of letters occurs twice Consider an alphabet $\Sigma=\{1,\dots,n\}$.
An ordered word is a word $w=w_1w_2\dots w_k\in\Sigma^*$ such that $w_1<w_2<\dots<w_k$. In other words, an ordered word is a strictly increasing sequence over $\{1,\dots,n\}$.

Let us call $O_{n,k}$ the set of all ordered words over $\{1,\dots,n\}$ of length $k$. Clearly, there are $\binom{n}{k}$ many ordered words of length $k$.

Now, what I am looking for is the maximal size of a subset $M\subseteq O_{n,k}$ such that each pair of letters $ij$ ($1\le i<j\le n$) occurs at most once as a consecutive substring in any word of $M$. What is the maximal size of such a subset?

Formally, let $\#_{ij}(M)$ be the number of words in $M$ that contain $ij$ as a consecutive substring, then
$$m_{n,k}=\max\{|M|:M\subseteq O_{n,k}\text{ and }\#_{ij}(M)\le 1\text{ for all }i,j\text{ with }1\le i<j\le n\}.$$
What is  $m_{n,k}$?

Asymptotic behavior as well as some non-trivial lower and upper bounds would be helpful.

$ $

Example: $\Sigma=\{1,2,3,4\}$ and $k=3$.

All ordered words of length $3$ are
$$O_{4,3}=\{123,124,134,234\}.$$
A maximal subset such that no pair occurs more than once would be
$$M=\{123,134\},$$
because all pairs $(12,13,14,23,24,34)$ occur at most once as a consecutive substring in $M$ and there is no set of size $3$ with this property. It follows that $m_{4,3}=2$.

Thank for any help.

There is a simple upper bound of $$\frac{\binom{n}{2}}{k-1},$$ following from the fact that there are $\binom{n}{2}$ ordered pairs of elements, and each ordered word contains $k-1$ of them.

There is an almost matching lower bound of
$$
\frac{\binom{n-k+1}{2}}{k-1}.
$$
This shows that for fixed $k$, the answer is asymptotically
$$
\frac{n^2}{2(k-1)} \pm O(n).
$$

For every $c \geq 1$ and $1 \leq d \leq c$, we can consider the collection of ordered words of the form
$$
d,d+c,\ldots,d+(k-1)c \\
d+(k-1)c,d+(k+1)c,\ldots,d+2(k-1)c \\
\ldots
$$
These collections for all $c,d$ have disjoint pairs. For a given $m \leq n$ and $c$, there is a word of this type if $m-(k-1)c \geq 1$, that is, if $c \leq \frac{m-1}{k-1}$. Therefore, the total number of words is
$$
\sum_{m=k}^n \left\lfloor \frac{m-1}{k-1} \right\rfloor.
$$
We can estimate this sum roughly by
$$
\sum_{m=k}^n \left(\frac{m-1}{k-1}-1\right) =
\sum_{m=k}^n \frac{m-k}{k-1} = \frac{\binom{n-k+1}{2}}{k-1}.
$$


Good text on algorithm complexity Where should I look for a good introductory text in algorithm complexity? So far, I have had an Algorithms class, and several language classes, but nothing with a theoretical backbone. I get the whole complexity, but sometimes it's hard for me to differentiate between O(1) and O(n) plus there's the whole theta notation and all that, basic explanation of P=NP and simple algorithms, tractability. I want a text that covers all that, and that doesn't require a heavy mathematical background, or something that can be read through.

LE: I'm still in highschool, not in University, and by heavy mathematical background I mean something perhaps not very high above Calculus and Linear Algebra (it's not that I can't understand it, it's the fact that for example learning Taylor series without having done Calculus I is a bit of a stretch; that's what I meant by not mathematically heavy. Something in which the math, with a normal amount of effort can be understood). And, do pardon if I'm wrong, but theoretically speaking, a class at which they teach algorithm design methods and actual algorithms should be called an "Algorithms" class, don't you think?
In terms of my current understanding, infinite series, limits and integrals I know (most of the complexity books I've glanced at seemed to use those concepts), but you've lost me at the Fast Fourier Transform.

It is my very personal opinion that the book of Jon Kleinberg and Éva Tardos is the best book for studying the design and analysis of efficient algorithms. It might be not as comprehensive as Cormen et al. but it is a great textbook. Let me point out, why I think this book might suit your interests best

you don't need heavy math machinery for the proofs
the book gives often a great intuition why something is working (or not), this is in my opinion very important for beginners and self learners
a very intuitive approach to NP-completeness
it has a great chapter how to deal with NP-complete problems in practice
it focuses on design patterns, which might help you to design your own clever algorithms

You should also notice, that there is a lot of free material in the WWW available. Great lecture notes are provided by Jeff Erickson. And you can even watch the whole MIT class on "Introductions to algorithms" taught by Charles Leiserson and Erik D. Demaine. Cool stuff!


Why is learning DNF harder than learning CNF? In the PAC-learning setting, it is easy to learn a CNF formula when we know each clause has at most $c$ variables.

We go through each positive sample, and eliminate every clause that contradicts the sample.

Learning a DNF formula is said to be much harder, but it seems a similar procedure can be used, so it is unclear to me why DNF is more difficult.

Start with all conjuctive clauses that have at most $c$ variables.  Go through each negative sample, and eliminate clauses that contradict the sample.

It's important to distinguish between $k$-CNF and CNF.  A $k$-CNF formula is a CNF formula where every clauses has at most $k$ literals; a CNF formula has no limit on the number of literals in each clause.

Both $k$-CNF and $k$-DNF are efficiently, properly PAC learnable, when $k$ is constant.  In contrast, as far as I am aware, it is not known whether CNF or DNF are efficiently, properly PAC learnable (no PAC-learning procedure is known for either).  So there is no asymmetry.

By "efficiently, properly PAC learnable", I mean that there is a polynomial-time algorithm for PAC learning, where the hypothesis space is the same as the concept space (e.g., given labelled instances from a $k$-CNF formula $\phi$, we want to find a $k$-CNF formula $\phi'$ that has low generalization error).

Since you haven't provided any references nor told us where you got the impression that $k$-DNF isn't PAC-learnable, it's hard to know what the exact source of your misconception might be.


NP-hard: an instance or a set? When we say a problem is NP-hard is that a property of a set of problems or is it a property of a instance of the set of problems?

You seem to be confused about terminology. You start correctly: "a problem is NP-hard". This already answers your question: hardness is a property of problems, not sets of problems or of instances.

To refresh, a problem is a question of the form, "Does the input object have this interesting property?" An instance is a specific object you're asking about.  So, for example, 3-colourability is the problem, "Can the vertices of the input graph be coloured red, green and blue such that there is no edge between vertices of the same colour?"  When you ask that question of a specific graph $G$, then $G$ is the instance.  (And a set of problems is just a set of problems: you know what a set is and you know what a problem is.)


Comparing rational numbers Given $a,b,c,d \in \mathbb N$ and $b,d \notin \{0\}$,

$$
\begin{eqnarray*}
\frac a b < \frac c d &\iff& ad < cb
\end{eqnarray*}
$$

My questions are:

Given $a,b,c,d$

Assuming we can decide $x < y \in \mathbb Z$ in $\mathcal{O}(|x| +|y|)$, is there any way of deciding $ad<cb$ without having to preform the multiplications (or divisions), $a\cdot d$ and $c \cdot b$. Or is there some sort of proof that there is no way.
Is there a faster method to compare rational numbers than multiplying out the denominators.

My current research:

Initial attempt at some general rules

One can try to make some general rules for solving the rational comparison:

Assuming all positive $a,b,c,d$:

$$
a < b \wedge c \ge d
 \Longrightarrow
\frac a b < \frac c d\\
$$
This basically means, if the left side is less than one, and the right side is at least one, the left side is less than the right side. In the same vein:

$$
a \ge b \wedge c \le d
 \Longrightarrow
\frac a b \not\lt \frac c d\\
$$

Another rule:

$$
(b > d) \wedge (a \le c)
 \Rightarrow
\left[\frac a b < \frac c d\right]
$$
I think of this rule as logical, since the greater the denominator, the smaller the number, while the greater the numerator, the larger the number. Hence if the left side has a greater denominator and a smaller numerator, the left will be smaller.

From here on in, we will assume that $a<c \wedge b < d$, because otherwise we can either solve it with the rules above, or reverse the question to $\frac c d \overset ? < \frac a b$, and we end up with this condition anyhow.

Rules:
$$
\left.
\\
\frac {(b-a)} b < \frac {(d-c)} d
 \iff
\left[\frac a b < \frac c d\right]
\right|_{a<c,b<d} \\
$$
This rule basically states that you can always subtract the numerators from the denominators, and set the results as the numerators, to obtain an equivalent problem. I'll leave out the proof.

$$
\left.
\\
\frac {a} b < \frac {c-a} {d-b}
 \iff
\left[\frac a b < \frac c d\right]
\right|_{a<c,b<d} \\
$$

This rule allows you to subtract the left numerator and denominator from the right numerator and denominator for an equivalent problem.

And of course there is scaling:

$$
\left.
\\
\frac {ak} {bk} < \frac {c} {d}
 \iff
\left[\frac a b < \frac c d\right]
\right|_{a<c,b<d} \\
$$
You can use scaling to make the subtraction rules above more significant.

Using these rules you can play around with things, apply them repeatedly, in smart combinations, but there are cases where numbers are close, and pathological.

By applying the previous rules, you can reduce all these problems to:
$$
\left.
\frac a b < \frac {ap+q} {bp'+q'}
\iff
\frac a b < \frac {q} {q'}
\right|_{a>q,b>q'}
$$

Sometimes you can solve this directly now, sometimes not. The pathological cases are usually in the form:

$$
\left.
\frac a b < \frac {c} {d}
\right|_{a>c,b>d,c\in \mathcal O(a), d \in \mathcal O(b)}
$$

Then you flip it, and result in the same thing, just with one bit less. Each application of the rules + flip reduces it by a digit/bit. AFAICT, you cannot quickly solve it, unless you apply the rules $\mathcal O(n)$ times (once for each digit/bit) in the pathological case, negating their seeming advantage.

Open problem??

I realized that this problem seems to be harder than some current open problems.

An even weaker problem is to determine:

$$ad \overset ? = bc$$

And yet weaker:

$$ad \overset ? = c$$

This is the open problem of verifying multiplication. It is weaker, because if you had a way to determine $ad \overset ? < bc$, then you can easily determine $ad \overset ? = bc$, by testing using the algorithm twice, $ad \overset ? < bc$, $bc \overset ? < ad$. Iff either is true, you know that $ad \ne bc $.

Now, $ad \overset ? = c$ was an open problem, at least in 1986:

  The complexity of multiplication and division. Let us begin with the very
  simple equation ax = b. When considered over the integers, testing its solvability and finding a solution x is possible by integer division with remainder zero. For checking a given solution x, integer multiplication will suffice, but it is an interesting open problem whether there are faster methods of verification.

  ― ARNOLD SCHÖNHAGE in Equation Solving in Terms of
  Computational Complexity

Very interestingly, he also mentioned the question of verifying matrix multiplication:

  It is also an interesting question whether
  verification of matrix multiplication, i.e., checking whether AB = G for given C,
  could possibly be done faster.

  ― ARNOLD SCHÖNHAGE in Equation Solving in Terms of
  Computational Complexity

This has been since solved, and it is indeed possible to verify in $\mathcal O(n^2)$ time with a randomized algorithm (with $n\times n$ being the size of the input matrices, so it is basically linear-time in the size of the input). I wonder if it is possible to reduce integer multiplication to matrix multiplication, especially with their similarities, given Karatsuba integer multiplication's similarities to matrix multiplication algorithms that followed. Then perhaps in some way we can leverage the matrix multiplication verification algorithm for integer multiplication.

Anyway, since this is still, to my knowledge, an open problem, the stronger problem of $ad \overset ? < cd$ is surely open. I am curious if solving the equality verification problem would have any bearing on the comparison inequality verification problem.

A slight variation of our problem would be if the fractions are guaranteed to be reduced to lowest terms; in this case it is easy to tell if $\frac a b \overset ? = \frac c d$. Can this have any bearing on comparison verification for reduced fractions?

An even subtler question, what if we had a way to test $ad \overset ? < c$, would this extend to testing $ad \overset ? = c$? I don't see how you can use this "both ways" like we did for $ad \overset ? < cd$.

Related:

Approximate Recognition of Non-regular Languages by Finite Automata

They do some work on approximate multiplication, and randomized verification, which I do not fully understand.
math.SE: How to Compare two multiplications without multiplying?
Suppose we were allowed to preprocess $c$ as much as we wanted in polynomial time, can we solve $ab=c$ in linear time?
Is there a linear-time nondetermistic integer multiplication algorithm? See http://compgroups.net/comp.theory/nondeterministic-linear-time-multiplication/1129399

  There are well-known algorithms for multiplying n-bit numbers with
  something like O(n log(n) log(log(n))) complexity. And we can't do
  better than O(n) because at least we have to look at the entire
  inputs. My question is: can we actually reach O(n) for a suitable
  class of "nondeterministic" algorithms?

  More precisely, is there an algorithm that can accept two n-bit
  binary numbers "a" and "b" and a 2n-bit number "c" and tell you in
  O(n) time whether "a * b = c"? If not, is there some other form of
  certificate C(a,b,c) such that an algorithm can use it to test the
  product in linear time? If not linear time, is the problem of
  testing the product at least asymptotically easier than computing
  it? Any known results along these lines would be welcome.

  John.

  ―johnh4717


Finding the two node-disjoint paths, minimizing the sum of their lengths Given an undirected graph and a start and end node, I am trying to find two node-disjoint paths such that the sum of their lengths is minimized.  In particular, each path must start at the start node, end at the end node, and no node (other than the start or end node) can be visited by both nodes.  Is there an efficient algorithm to solve this problem?
I know that if I just need the shortest path, I can use Dijkstra's algorithm, but finding one path with Dijkstra's algorithm and then searching for another is sometimes not optimal at all, since nodes in the first path may have blocked a possible and way shorter path.
I have tried implementing the node_disjoint_path algorithm from the Python networkx package. But I must say that the result is very varying from okay to really bad.  My network is not that big. "Only" 6000 nodes and 7500 edges.

This can be solved by a small modification to Suurballe's algorithm, with $O(|E| + |V| \log |V|)$ running time.  You might also be interested in Computing the k shortest edge-disjoint paths on a weighted graph.
Suurballe's algorithm works with directed graphs.  You can convert an undirected graph to a directed graph by replacing each undirected edge $(u,v)$ with two directed edges $u \to v$, $v \to u$.


Name of a sequence that is unknown to stop on a given input Several years ago I was self learning lisp by a book which I do not remember. As an example there was a recursively defined sequence which was said to be unknown to be finite or not for every input --- to generate a sequence you were required to provide two(?) initial values. At least that is how I remember.

There was a Wikipedia article on it but I can't find it either. Does anyone know what I'm talking about?

It has many names, I first heard about it as the Syracuse problem, but the most prominent name is maybe Collatz Conjecture.