texts: Is type unification a kind of search for alpha equivalence?

texts:
I was reading about type unification and it moves through of substitution of variables. To me it looks like a search for an alpha equivalence... I mean, two types are unifiable if they are alpha equivalent, at last if they are in polymorphic form, is this right?
If I have forall a.a -> a and forall b.b -> b I can apply [b/a]forall a.a -> a to achieve forall a.a -> a. So they are unifiable!?
Going deeper I could unify forall a.a -> a to int -> int and then deduce that the first is more general because I can achieve the second by [a/int] substitution on the first right?


texts: How to solve a Simple Linear Equation using a binary tree data structure

texts:
i am currently working on a school project that takes in a simple linear equation and has to return the value of x, the code i have transforms x + 3 = 3x - 2 into a binary tree format like so:

        =
     /     \
    +       -
   / \     / \
  x   3   *   2
         / \
        3   x

now that i have the expression in this format could someone please explain how can i obtain the value of x, any help is appreciated and if you have an alternative method that may make it easier i would love to hear it thank you


texts:
I am attempting to understand exactly how the terminology for k-approximation algorithms work, from when k is known and determining what k is.

If we assume that a vertex cover in a graph G is of size 7 and that there is a 3-approximation algorithm for finding the minimum vertex cover. Does that mean the algorithm could return values between 7 and 21 inclusive?

If the maximum independent set in a graph is of size 12 and an algorithm returns for a complement graph a clique of size 6 in the worst case. Would that algorithm be a 2-approximation or a .5-approximation?


texts: Multiplying two bivariate polynomials using FFT

texts:
Consider two bivariate polynomials of degree at most $n − 1$ in each variable:
$$
F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^iy^j \quad\text{and}\quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^iy^j
$$
Show how to compute the product polynomial in $O(n^3 \log n)$ time.

Can anybody briefly explain the solution please?


texts: Transition systems that satisfy LTL but not CTL, and vice versa

texts:
I am learning about temporal logic and model checking systems. One conceptual exercise that I am struggling with is how to create a transition system which satisfies only one of two given properties, when one is in LTL and one is in CTL. For example:

Find a transition system that satisfies only one of the following two properties: $FGp$, $AFEGp$
Find a transition system that satisfies only one of the following two properties: $FGp$, $EFEGp$
Find a transition system that satisfies only one of the following two properties: $GFp$, $AGEFp$

How should I begin when trying to reason about these types of problems? In general, is it easier to design transition systems for LTL properties or CTL properties? Or does it depend on the situation?

Any insight would be appreciated!


texts:
You want to print vectors with n elements, where:

the first element can have the values: e1.1, e1.2, e1.2;
the second element can assume the values: e2.1, e2.2, e2.3;
...;
...;
the nth element can assume the values: en.1, en.2, en.3.

I should print all possible vectors; eg:

{e1.1, e2.1, en.1 ...};

{e1.2, e2.1, en.1 ...};

etc. etc.

Someone could indicate an algorithm making use of while/for loop to print these vectors?

Thanks so much!


texts: Algorithm to check that one sum is less than another

texts:
Suppose that we have two sums:
a1+a2+...+an,
b1+b2+...+bm
We can perform only two binary operations on operands of these sums:

lt (less than)
eq (equal)

These operations can return 3 possible results: true, false, unknown. Other operations like summation, subtraction and etc. are not allowed.
The question is how to implement algorithm for function lt(a1+a2+...+an, b1+b2+...+bm), that also returns true, false or unknown? But unknown can be returned only if there is no enough information to return true or false.
For example if we know that (n=m=3 && a1 < b3 && a2 = b2 && a3 < b1) the algorithm have to return true.
Or if we know that (n=3 && m=2 && a1 < b1 && a2 < b1 && a3 < b2 && b1 < b2) the algorithm have to return unknown.


texts: Recovering data from under sampled data streams

texts:
I’m trying to analyze a repeated data stream from a sensor.  The data probably has events at the 100us scale, it occurs at a fairly random interval, and the signals are extremely similar.  The problem is that I don’t have any sensors that have sub-millisecond refresh rates.  The best I can do with what I have is about 1ms sensor reads.
So . . .
The idea is that if I sample a large number of event the chances are that the sampling ticks are falling on different sections of the signal.  If this is true then a series of 10-20 events should give me the data that I need to reconstruct the signal.  The signals repeat in a fairly random fashion and are very similar in each dataset so the chances are that each sampling run is gathering “pieces” of the total dataset.
Is there a name for this sort of procedure so that I can start to research how to do it?  Are there algorithms or toolsets in the open source world to accomplish this task?
Right now I’m literally graphing the data on graph paper and overlaying the image.  This is less than ideal . . .


texts: If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index?

texts: If we store a min heap of $n$ elements, $\color{Blue}{[1,2, \dots n]}$ into an array, then what can be minimum value present at any index $i$ and maximum value present at any index $i$. (elements are from $\color{Blue}1$ to $\color{Blue}n$)


texts: Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

texts:
From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs are not equivalent in power to nondeterministic PDAs.

However, all CFLs are decidable, and in this case, any deterministic TM is equivalent in power to a nondeterministic TM.

Now, this is a large gap - what is the smallest language "above" CFLs that is closed under nondeterminism?


texts: Why is a Fibonacci-Tree of rank 1 consolidated with one of rank n in this Fibonacci-Heap?

texts:
In the solution to problem 2 of this exercise sheet:

  The height of $n$-node Binomial  Heap  is  always $O(\log{n})$. Show
  that this  is  not  the  case for Fibonacci Heaps by exhibiting, for
  any positive integer $n$ a sequence of Fibonacci-heap operations that
  creates a Fibonacci heap consisting of just one tree that is a linear
  chain of $n$ nodes.

it is stated that

  We obtain a chain with two elements where $x$ is the root,
  having degree $1$. Thus the chain of height two and the chain of height $k$ are consolidated.

However, in this presentation, it is stated that:

  Delete $\min$.

  Delete $\min$; meld its children into root list; update $\min$.
  Consolidate trees so that no two roots have same rank

which is not the case with $2$ and $k$.

So why are they consolidated?


texts:
From P5 in this paper: https://hal.inria.fr/hal-01094195/file/CIC.pdf

  Using this purely functional part, it is possible to encode many int
  eresting notions. For instance
  ∀
  C
  :
  Prop
  , C
  is a logical proposition (a term of type
  Prop
  ) which encodes absurdity (
  ⊥
  ) : there is
  no closed term of type
  ∀
  C
  :
  Prop
  , C
  (so no proof of
  ⊥
  without hypothesis) and also from a proof
  t
  of
  ∀
  C
  :
  Prop
  , C
  one can build a proof
  t C
  of an arbitrary proposition
  C
  so the natural deduction
  rule for eliminating
  ⊥
  is derivable in the logic.

where

$$
\forall C: Prop, C
$$

looks entirely identity function to me, which can definitely be inhabited by a closed term. Why the author said it encodes absurdity?

If I were to encode absurdity, I would do

$$
\exists P: Prop, P \to \forall Q:Prop, Q
$$

That is, there exists a proposition which derives everything. From category theoretic perspective, it's precisely how the initial object is defined, which can encode absurdity with no doubt.

Did I misread it in a terrible wrong way that the author was actually right? How about my encoding, does it make sense to you?


texts: Is it possible to construct a finite state automata for a decimal adder?

texts: Suppose the strings are of the form x#y#z , where x,y,z are strings formed from the alphabet $\Sigma=(0,1,2,3,4,5,6,7,8,9)$ . The language is accepted if x+y=z is satisfied, for example : 56#65#121 is accepted, but 2#97#104 is not. Is it possible to find a finite automata for such a language ?  I cannot fathom how decimal addition could be carried out using a DFA .


texts:
I got no responses on stackoverflow, so I'm asking here:

How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems?  There are a few algorithms, using patience sorting, dynamic programming or with decision trees.  How are these used in real life -- maybe to data streams or something?

To remind you, I put in bold the longest increasing sequence

{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

As a bonus, is there any way to use the result that a sequence of length mn + 1 will have an increasing subsequence of length m or a decreasing subsequence of length n? E.g. Our list as length 16, so there should be an increasing sequence of length 5 or decreasing sequence of length 5.  In our case 0,2,6,9,11,15.

Also an increasing sequence of length 8 or a decreasing sequence of length 3: in our case 12,10,1.

CF: https://stackoverflow.com/q/12458641/737051


texts: How do you compute the Pareto Front of a set?

texts:
I need to decide which solution is the best design, in order to do that I need to compare them. Lower energy used and lower weight is better. My initial idea was to order both the fields best to worst and chose based on which one finished higher but whats better 3rd and 2nd, or 1st and 4th?

Pareto front is a set of nondominated solutions, being chosen as optimal, if no objective can be improved without sacrificing at least one other objective.

(Energy Used, Weight)

(30,20)

(50,30)

(10,40)

(20,50)

(40,10)

Diagram Showing the Table


texts:
Let $G = (V,E)$ be a graph having $n$ vertices, none of which are isolated, and $n−1$ edges, where $n \geq 2$. Show that $G$ contains at least two vertices of degree one.

I have tried to solve this problem by using the property $\sum_{v \in V} \operatorname{deg}(v) = 2|E|$.  Can this problem be solved by using pigeon hole principle?


texts: Proving that a specific grammar is ambiguous

texts:
How can I prove that the following grammar is ambiguous:

$$ A \to AA\mid B  \\  B \to aBb\mid ab $$

I tried finding a string that can be derived in two different ways, but to no avail.


texts: Inability to understand local fourier analysis in the given link

texts:
https://www.researchgate.net/publication/235662494_On_separating_overlapped_fingerprints
[Paper name-"On separating  overlapped fingerprint", author-Fanglin Chen,Jianjiang Feng,Jie Zhou]
I am unable to understand the process of local fourier analysis in the initial orientation field estimation. I have tried searching over the internet but in vain.
The sentence I am unable to understand has been marked in the paper. What is this 16 x 16 and then again from where do i get this 64 x 64? I can apply a gaussian filter by taking each pixel as centre. But how can i do that taking a 16 x 16 block as centre? The meaning of that sentence is absolutely unclear to me.
I have looked at the original paper from where this has been taken and also this paper (https://www.researchgate.net/publication/261469993_Automatic_segmentation_of_latent_fingerprints)
[Paper-Automatic Segmentation of Latent Fingerprint author-Anil K.Jain]
but things are very unclear to me.
Please, I would request the community to kindly help me. I am stuck at this for the last 2 weeks.
Thanks in advance to anyone who will help me


texts: When proving a set is not regular is it enough to prove a subset of it regular?

texts: E.g. when proving L = {w in {a,b}^*: the first, the middle, and the last characters of w are identical}, can i just prove ab^pab^pa is not regular? Where p is the pumping length?


texts:
How to trigger a thread to start working using semaphore?

I have find a lot of explanation about thread and semaphore but i still don't understand, any help please


texts: Tips for understanding the Pumping Lemma for Context-Free Languages

texts:
I'm having a hard time wrapping the idea in my head. Can anyone explain this as different from Sipser's perspective?

(I saw one discussion in reddit but it's for regular languages)
https://www.reddit.com/r/compsci/comments/1pnjrp/the_pumping_lemma/


texts: Why is the method of im2col with GEMM is more efficient than the method of direction implementation with SIMD in CNN

texts:
The convolutional layers are most computationally intense parts of Convolutional neural networks (CNNs).Currently the common approach to impement
convolutional layers is to expand the image into a column matrix(im2col) and perform and perform Multiple Channel Multiple Kernel (MCMK) convolution
using an existing parallel General Matrix Multiplication (GEMM) library. However im2col operation need load and store the image data, and also need
another memory block to hold the intermediate data.

If I need to optimize the convolutional implementation, I may choose to direct implementation with SIMD instructions. Such method will not incur any
memory operation overhead.

the benefits from the very regular patterns of memory access outweigh the wasteful storage costs.

From the following link, at the end of the link

https://petewarden.com/2015/04/20/why-gemm-is-at-the-heart-of-deep-learning/

So I hope to know the reason. May floating point operations require more instruction cycle? or the input image is not much large, so it may residue
in the cache and the memory operations don't need access DDR and consume less cycles.


texts: De Casteljau's algorithm without temporaries / stack

texts:
De Casteljau's algorithm is a method for calculating a point on an order $N$ Bezier curve at time $t$ by performing a linear interpolation between two order $N-1$ Bezier curves at time $t$.  You do this recursively until you reach order 0 which is single point / data value.

Calculating a point on an order 1 (linear) Bezier curve with control points $A$ and $B$ at time $t$ is done like this:

$\overline{AB} = A(1-t) + Bt$

Which you can see is just a linear interpolation between $A$ and $B$ at time $t$.

Calculating an order 2 (quadratic) Bezier curve with control points $A$,$B$ and $C$ is done by interpolating between $A$ and $B$, interpolating between $B$ and $C$ and interpolating between those results:

$\overline{AB} = A(1-t) + Bt$

$\overline{BC} = B(1-t) + Ct$

$\overline{ABC} = \overline{AB}(1-t) + \overline{BC}t$

Note that you could expand that out algebraically to get a polynomial in Bernstein form that doesn't use interpolation, but instead can be evaluated directly in one step:

$\overline{ABC} = A(1-t)^2 + 2B(1-t)t+Ct^2$

Calculating an order 3 (cubic) Bezier curve with control points $A$,$B$,$C$,$D$ at time $t$ would continue the pattern by doing a linear interpolation between $\overline{ABC}$ and $\overline{BCD}$ at time $t$.

When evaluating a curve using the De Casteljau algorithm, you need temporary storage.  In the $\overline{ABC}$ case you need to first calculate $\overline{AB}$ and $\overline{BC}$ and then you combine those results.  The storage needs get larger as the curve order increases.

My question is this:

Is there a way to reformulate the De Casteljau algorithm such that you can still use lerps to evaluate a point on the curve, but without the temporary storage needed?


texts: Why is universal turing machine considered with only one head?

texts:
While defining the following time hierarchy theorem (for deterministic case ) :

  If $f(n)\log{f(n)}=o(g(n))$ then there are languages decidable in $O(g(n))$ which cannot be decided in $O(f(n))$

The $\log$ factor comes due to the overhead of simulation by universal Turing machine, as the universal Turing machine has only one head. But what if the universal Turing machine uses same number of tapes and tape heads as some Turing machine $M$, when $<M,x>$ is given as an input to it ? Does the $log$ factor vanish ? Am I missing something ?


texts: What is a recursion for Huffman encoding?

texts:
If I had to write the Huffman encoding as a recursion in terms of the cost $C_{ij}$, given weights/frequencies $W = [w_1,\ldots,w_n]$, how would I do it? (where this is creating a minimum cost tree, $C = \sum_i w_i \cdot \mathrm{depth}_i$).

I am going off of Dasgupta's Huffman procedure:

  procedure Huffman(f)

  Input: An array f[1···n] of frequencies

  Output: An encoding tree with n leaves

  let H be a priority queue of integers, ordered by f

  for i = 1 to n:   insert(H,i)

  for k = n+1 to 2n–1:

    i = deletemin(H),   j = deletemin(H)

    create a node numbered k with children i,j

    f[k] = f[i] + f[j]

    insert(H,k)

It should be something like the matrix multiplication order minimization algorithm, which seeks to minimize the total number of components calculated when multiplying a string of matrices,

$$
C_{ij} = \min(C_{ik} + C_{k+1,j}+(m_i-1) \cdot m_k \cdot m_j)
$$

Where $m_i,m_j$ are the dimensions of the matrix multiplication at the level directly below the node...

I wrote something like:

$$
aC_{ij} = \min((a+1)C_{ik} + (a+1)C_{k+1,j}),\text{ for all } i,j,k
$$

With base case: $C_{ii} = w_i$

Knowing full well that this is probably incorrect.  But I don't understand how I should write it.  I mean, I have the algorithm fine—just Huffman + DFS afterward (which always turns left, then right) to find out the order of the elements.  But I don't understand how the recursion notation works in this situation.


texts: Regular Expression with at least one a, even number of b

texts: I've been working on some regular expression questions, and came across one that I cannot figure out. Working on the language over $\{a, b\}$, the text asks for a regular expression for the language of all words having at least one a and an even number of b's, using only | and * (maybe $\varepsilon$ too). My idea so far has been something like $(a^*ba^*b)^*a^*a(a^*ba^*b)^*a^*$, but this doesn't match cases like bab, bbbab, or baaab.


texts: Constructing a Pixel Image from Rectangles and Row or Column Rotations

texts:
The most recent challenge on Advent of Code involves constructing an image in a binary pixel array from a sequence of instructions:

rect AxB, which sets all of the pixels in a rectangle A pixels wide by B tall at the top left corner of the array.
rotate row y=A by B, which performs a circular rotation of row A by B pixels.
rotate column x=A by B, which performs a circular rotation of column A.

As part of solving the problem, I produced the following image:

####..##...##..###...##..###..#..#.#...#.##...##..
#....#..#.#..#.#..#.#..#.#..#.#..#.#...##..#.#..#.
###..#..#.#..#.#..#.#....#..#.####..#.#.#..#.#..#.
#....#..#.####.###..#.##.###..#..#...#..####.#..#.
#....#..#.#..#.#.#..#..#.#....#..#...#..#..#.#..#.
####..##..#..#.#..#..###.#....#..#...#..#..#..##..

This got me wondering:

How is the inverse problem solved? i.e. given an image, what sequence of instructions generates that image?
Are there any images which cannot be created with this set of instructions?
Is there a polynomial-time algorithm to find a minimal sequence of instructions that generate a target image? That is, where there is no shorter set of instructions that generates the same image.  If not, is there a polynomial-time algorithm for deciding if a given sequence of instructions is minimal?

I've done some Google searches but turned up nothing. I would appreciate any links to materials describing this or similar problems.


texts: Does Brzozowsky's algorithm always produce the right minimum DFA?

texts:
Let's say I have this NFA automaton A:

[q1] [reject]
    [q1] 0 -> [q2]
[q2] [reject]
    [q2] 1 -> [q3]
[q3] [accept]
[q0] [reject][initial]
    [q0] 1 -> [q1]
    [q0] 0 -> [q0]
    [q0] 1 -> [q0]

The output of Brzozowsky's minimization method, executed manually using JFLAP and confirmed by my own implementation is:

[q1] [reject]
    [q1] 1 -> [q2]
    [q1] 0 -> [q1]
[q2] [reject]
    [q2] 1 -> [q2]
    [q2] 0 -> [q3]
[q3] [reject]
    [q3] 0 -> [q1]
    [q3] 1 -> [q4]
[q4] [accept]
    [q4] 0 -> [q3]
    [q4] 1 -> [q2]
[q0] [reject][initial]
    [q0] 1 -> [q2]
    [q0] 0 -> [q1]

To be specific, this is the output of det(rev(det(rev(det(A)))) , since A is an NFA, where det() is the determinize function and rev() is the reverse one.
But this is not the minimum DFA, the right one obtained by Hopcroft's algorithm after the determinization of A is:

[q1] [reject]
    [q1] 1 -> [q1]
    [q1] 0 -> [q2]
[q2] [reject]
    [q2] 0 -> [q0]
    [q2] 1 -> [q3]
[q3] [accept]
    [q3] 1 -> [q1]
    [q3] 0 -> [q2]
[q0] [reject][initial]
    [q0] 1 -> [q1]
    [q0] 0 -> [q0]

So I'm pretty confused here.. Why Brzozowsky's method produced the wrong output?


texts: Is there any Boosting algorithm with closed-form solutions?

texts:
My goal is to formulate the learning and generalization phases of any Boosting algorithm as a matrix-vector operation.

Through Google, I found a good pdf (*) describing several boosting algorithms but the author Marco Cusumano-Towner only hints and doesn't explain how to recast the boosting algorithms (GradientBoost, Adaboost, QuadBoost) using matrix operations.

My question is:

Can I formulate a boosting algorithm as a regression, a game or a linear programming and arrive at closed-form solution which uses only matrix operations?

(*) Boosting with log-loss


texts: Why AKS primality test is called polynomial?

texts: It's complexity is $\mathcal{O}(\log^6n)$ and $\log^6n$ is not a polynomial. Can we say that primality testing is strictly contained in $P$ then?


texts: should you take question mark as a separate word in bigram language modelling when finding probability?

texts:
the corpus
 what is the shape ?
 what is the colour ?
 what colour is it ?
 it is what ?
 is it red ?
 what is it ?
 what shape is it ?
 it is red
 it is green
 the colour is red
 the shape is square
 red is the colour
 square is the shape
(1) What is the probability of the following sentences: (4 points)
a.   what colour is red ?


texts:
If the body of a simple for loop has time complexity $O(n)$ and it is
   executed $n-1$ times what is the time complexity of the complete loop?

I am trying to figure out the correct answer to this question for my upcoming exam. My reasoning is that if the body of the loop is executed $n-1$ times and its complexity is $n$ then the complete loop should have time complexity of $O(n \times (n-1)) = O(n^2 - 2) = O(n^2)$.

However, the correct answer given to us is $O(n^3)$.
Am I missing something or is it just a mistake in the answers?

Edit: It turns out that the answer given to us was just wrong...


texts: Solve recurrence relation $T(n)=n^{1/5}T(n^{4/5})+5n/4$

texts:
I am trying to solve this recurrence relation - $T(n)=n^{1/5}T(n^{4/5})+5n/4$. I can't use the master's method and the recursion tree method because of that $n^{1/5}$ term.
We can write $$\frac{T(n)}n=\frac{T(n^{4/5})}{n^{4/5}}+\frac54$$
Now we can change variable $S(n)=\frac{T(n)}{n}$. So, we get $$S(n)=S(n^{4/5})+\frac{5}{4}$$
Then I used the recurrence tree method by taking $n=2^{(\frac{5}{4})^k}$. I got $S(n)=O((log_{5/4}(log_2 n))^2)$. So, $$T(n)=O(n(log_{5/4}(log_2 n))^2)$$
I don't know, the answer doesn't look right. Can anyone please help me out? If anyone knows the final answer please let me know, so that I can check.
Thanks!


texts: Output of well-known algorithms for the Subset sum problem

texts:
According to Wikipedia:

  In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete.

What is the output of the known algorithms which resolve exactly the subset sum problem?

For example:

The algorithm which take $O(2^N*N)$ time.
The algorithme which take $O(2^{N/2})$ time.

Is it just Yes / No or do they also give the extraction of solution?

Example:

$A = \{1, 3, 4, 5\}$

$k = 8$ (The search item)

Output : YES
Output : {1,3,4}, {5,3} (where 1+3+4=8 and 5+3=8)


texts: Is there a "diminishing returns" tree search algorithm?

texts:
I'm looking for an algorithm that will let me plug in a heuristic for scoring a subtree, and as the algorithm does a depth-first search, it stops when the score has:

Already hit a threshold (minimum score)
only changed a very small amount from child to parent

So this algorithm would be doing a fuzzy search for a "payload."

Is there an algorithm like this?


texts:
Have such exercise:
Let $L_1=\{a^{2n}b^n|n\geq1\}^*$

and $L_2=\{b^na^n|n\geq 1\}^*b$

Prove, that $L_1, L_2$ are context free, while quotient $L_1/L_2$ is not context-free.

(This is  home exercise, which I am not sure what to make of it. 3rd one)

Anyway, proving $L_1, L_2$ are CFL is trivial.

For $L_1$:

S->aaSb|$\epsilon$

For $L_2$

S->Ab

A->bAa|$\epsilon$

So far so good, grammar can be constructed, i.e CFL. Fine.

But quotient.. Lets list few words for $L_1$: $\epsilon$ then: aab, aabaab, aabaabaab, $\dots$ then aaaabb, aaaabbaaaabb, $\dots$ and so on - string under Kleene, which contains twice as much $a$ than $b$

Now about $L_2$ words: b then bab,babab,bababab,$\dots$ then bbaab,bbaabbaab,$\dots$, ie - $(b^na^n)^*b$

But.. Only words in $L_1$ are of format which ends in suffix ...ab are where $n=1$: $aab,aabaab,\dots$, moreover - if we take string from $L_1$, for example $aabaab$, we kinda remove trailing $b$ ($aabaa$), after which we can't really remove anything else, in this particular case we would have to remove suffix $bbaa$, but there is no such suffix in word from $L_1$

So, all in all - quotient, to my understanding is $L_1$, with only difference that there is very last b always removed. And it feels to me like CF, what am I doing wrong?

Edit: According to comment, I have mistake in my thoughts, which is reasonable, we dont have to Kleenize $n$ in each substring.

Ie $aaaabbaab$ for $L_1$ is possible. Ok, now lets look exactly at $aaaabbaab$ - first remove trailing $b$, get $aaaabbaa$. Now $bbaa$ - resulting in $aaaa$.. So all in all, quotient is still $L_1$, which has some arbitrary suffix removed. Still feels CF to me


texts: Is 3-colouring NP-hard for 5-colourable graphs?

texts:
Recently it was shown that it is NP-hard to find a 5-colouring of a 3-colourable graph.
More generally, it is NP-hard to distinguish $k$-colourable graphs from those that are not $(2k-1)$-colourable, for $k\ge 3$.

J Bulín, A Krokhin, J Opršal. Algebraic Approach to Promise Constraint Satisfaction, STOC 2019. doi:10.1145/3313276.3316300 (preprint)

Turning the question around:

  Is deciding if a 5-colourable graph is 3-colourable NP-hard?


texts: benchmark data set for Metareasoning problem

texts:
I am developing algorithm for solving following problem:

Given a set of items with unknown feature(s) (but  know distribution of feature(s)). Algorithm must choose what items to measure(every measure has some cost)). I use Value of information theory to find this measurements.

After measurements are done  algorithm choose K best items from the set, using some utility function that depends on feature values of items.

I crafted few synthetic data sets, but perhaps there are some benchmark data sets that are used for this kind of problems?

Regards.


texts: O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B - how is this possible?

texts:
Context: I've been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem.

If

s = little string and S = len(s)
b = big string and B = len(b)

then I believe it would be something along the lines of (pseudocode):

hs = hash(s)
for every position, substring of length S in B:
    h_sub = hash(substring)
    if hs == h_sub:
         print position

Note that the for loop will run B-S+1 times, so whatever happens inside the loop must be O(1) in order for the whole thing to be O(B).

This assumes that there exists a O(1) hash function hash(s) that only returns the same hash when two words are permutations of each other, and never collide otherwise.

What is this hash function? It seems like you'd have to iterate through every letter in substring to calculate h_sub and I don't see how that can happen in less than O(S) time. This answer seemed promising but then someone found a non-valid collision.

I learned about the radix-2p hash for this problem in school and we had to prove it as a homework exercise so I am convinced of its correctness.

However in the calculation $k = \sum_{i=0}^{n-1} x_i(2^{p})^i$, the exponent on the $2^p$ always changes depending on the position of the letter $x_i$ within the substring, so I don't see how we can avoid having to iterate anew through all S letters of the substring when we calculate $k \text{ mod } (2^p-1)$.

Am I missing something or is there another approach entirely? Thanks.


texts: Show that a decidable language is not decided by a decider in a given set

texts:
M.Sipser's Introduction to the Theory of Computation offers the following problem in its chapter on decidability:

Let A be a Turing-recognizable language consisting of descriptions of Turing machines, {⟨M1⟩,⟨M2⟩, ...}, where every Mi is a decider. Prove that some decidable
language D is not decided by any decider Mi whose description appears in A.
(Hint: You may find it helpful to consider an enumerator for A.)

My qualm about this is that the question seems to imply finding a decidable language, the decider for which is not in the set of all deciders, which goes against the definition of decidability of languages.

Could you explain whether my doubts are justified? And if not, could you provide a proof (or a sketch of a proof) for the given problem (with or without the enumerator that is mentioned in the hint)?


texts: This is probably a very stupid question but I couldn't find an answer anywhere. I'm reading the Technical Reference book of the IBM PC XT and it says that "The system board also has from 128K by 9 to 256K by 9 of R/W memory." What does this by 9 means?


texts: Partitioning connected graphs in the plane

texts:
This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes.

How can we divide the plane using line segments in such a way that each subdivision contains exactly one connected component?

I was thinking of generating a voronoi diagram using the endpoints, but this presents some issues:

Long edges are not guaranteed to be in the correct partition.
The border becomes very complex (There is a separate line segment for most points)

Is there an algorithm that creates less complex borders?

The input would be a planar graph with multiple connected components, where each node has coordinates associated to it.

The output would be a subdivision for the bounding box given by the graph, which divides the plane using line segments.

Example solution using red lines

I'm looking to minimize the amount of line segments required, but optimality is not required.


texts: Find out the largest LCM of the partitions of n

texts:
I want to find out an algorithm to find out the largest least common multiple (LCM) of the partitions of an integer $n$.

Example:  $5 = 1 + 4$, $5 = 2 + 3$, since $\mathrm{LCM}(1,4) < \mathrm{LCM}(2,3) = 6$, the largest LCM of the partitions of $5$ is 6.

The definition of "partition" is the standard definition of it. In order to make the problem more clearly, I will take n = 10 as an example. The largest LCM if the partitions of 10 is 30, since 10 = 2 + 3 + 5.
More examples(Let g(n) be the answer that I want to get):
g(11) = 30
g(12) = 60
g(13) = 60

I want to find out an algorithm that can get the largest LCM in 1 second with the n less or equal to 250.


texts: Order-of-growth of selection sort is quadratic, it takes 2secs to sort 100 elements, what will be the expected completion time to sort 200 elements?

texts:
The above is an MCQ from an online quiz given by my Algorithm lecturer. The available options are 6secs, 4secs, 12secs and 20secs.

The answer I selected was 12secs and it was rejected. The lecturer said the answer should be 4secs and then I started to prove that the answer is greater than or equal to 8secs in the following ways.

1. Using Proportions

T = kN2, where k is an arbitrary constant

2 = k x (1002)       -------------(1)

x = k x (2002)       -------------(2)

(2)/(1) implies, x/2 = 2002/1002 = 22 = 4,

i.e. x/2 = 4 but x = 2 x 4 = 8secs

2. Using 'doubling hypothesis'

NOTE: This is almost identical to the first proof.

Running Time = aNb, where b = 2

2 = 1002a, and a = 2/1002

Then again, Time = aN2 = (2/1002)N2 =(2/1002) x 2002 = 2 x 4 = 8secs

3. Using a slide from a reliable source

As you can see the ratio T(2N)/T(N) = 4 for Selection Sort

Suppose the answer is 4secs,

T(2N)/T(N) = 4/2 = 2 and the order-of-growth becomes linear and this proves the answer 4sec is wrong.

Whereas when you substitute the answer 8secs,

T(2N)/T(N) = 8/2 = 4 and proves that the order-of-growth is quadratic according to this slide.

4. By ploting the curve on a graph

Both the points (100,2) and (200,8) satisfies Y=mX2 and m = 2 x 10-2, and I proved it through equations as well to show that the curve is quadratic and not cubic or else. Also plotted the straight line for the points (100,2) and (200,4).

Finally, the lecturer agrees that the answer should be 8secs but since that option is missing I should select the closest approximation which is 6secs.

But my point is the running time should be greater than or equal to 8secs and at the same time closest to 8secs because there are other basic operations involved as well like variable declaration, initiation, comparison, swap function and for small inputs the time taken for those aren't negligible. So the answer 12secs is my answer in the given context.

Although we can't tell the exact running time, what do you think is the possible range for running time? and, is my argument valid or not?

I thank you in advance!


texts:
Question about "Artificial Intelligence: A Modern Approach by Russell and Norvig"

I have issue to distinguish clearly between intelligent and rational agent presented by Norvig and Russel. What I understand is that rational agent think and act like human but not intelligent agent. Thus, Russel present 4 types of intelligents agents
– Simple reflex agents
– Model-based reflex agents
– Goal-based agents
– Utility-based agents

My question is : could Goal-based agents be a rational agents at the same time ? Does this concept limite intelligence to just human intelligence ? Some paper do not make distinction between these two terms.


texts: Check whether loop invariants are correct?

texts:
I'm trying to prove some code is correct, using Hoare logic.  How do I check whether my loop invariants are correct?

I'm asked to prove (using Hoare Logic) that the following program is valid:

x=1;
i=N;
while (i!=0){
    i--;
    x*=A;
}

with the pre-condition that N>=0 and post-condition that x=A^N.

This is my attempt:

{ N>=0 }
x=1;
i=N;
{i >= 0}
while (i!=0){
    {i>=0}
    {x = product(i in (0:N-i); A)}    (loop invariant)
    i--;
    x*=A;
}
{x = A^N}

The curly brackets represent invariants that are supposed to hold at that point in the code.  The 2 loop invariants seem to hold for every instance of the loop.

Is my attempt correct?  Are my loop invariants sufficient? Do I have too many?

I know that {i>=0} is given by the definition of the loop. Should I remove that loop invariant then, since it is the case by default?

EDIT: My new attempt

{N>=0}
x=1;
{x = A^(N-N)=A^0=1}
i=N;
{x = A^(N-i)}
while (i!=0){
    {i>=0}
    i--;
    {x = product(i in (0:N-i-1);A)}
    x*=A;
    {x = product(i in (0:N-i);A)}
}
{x=A^N}


texts: How to simulate online matching algorithms (implementation)

texts:
I was reading about online algorithms and bipartite matching.
I found an implementation that works fine on several websites (like geeksforgeeks).
For the online version, I found this paper
https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf
But there's one part that I don't understand.
In this paper, they refer to U (boys) as "on-line" which means data arrive sequentially (in real-time?) not all at once
While I can see how such case if frequent in real life, I fail to understand what kind of implementation could be used to demonstrate this...
I thought of the following

Create a graph with girls
add boys and define manually the girls they like via some sort of user input (input py/cin c++)
solve(match) for the newly added boy according to rank(priority) and return to user input till no more girls are left or till user decides to stop?

In the online version do we assume a predefined limited number for both U and V(boys and girls)? or just for girls?
Is my suggestion correct? or did I misunderstand something?
Thanks in advance


texts: Practical applications of Weighted Independent Set in path graph?

texts:
Consider Weighted Independent Set in a path graph, i.e., a graph where all the vertices are in a single path.

Does this problem have practical applications?  What are some?  This problem is used in many CS courses as an intro to the dynamic programming paradigm, but I don't see any mention about whether this is useful practically or whether it is only mentioned for didactic purposes.


texts: Is this method of proving non-regularity is equivalent to pumping lemma?

texts:
I find it really difficult to prove non-regularity of a language using pumping lemma. I do understand that regular language is the language that can be expressed using DFA/RE. So if I can't create DFA/RE for language can I use that as proof of it's non regularity?

For example, following is an attempt to create a DFA for
0^P
where p is prime number.

Following machine accepts 2,3,5,7 which are primes. But it also accepts those which are not primes. Can it be considered as proof of non regularity of said language?


texts: Pumping lemma for simple finite regular languages

texts:
Wikipedia has the following definition of the pumping lemma for regular langauges...

  Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1
  depending only on $L$ such that every string $w$ in $L$ of length at
  least $p$ ($p$ is called the "pumping length") can be written as $w$ =
  $xyz$ (i.e., $w$ can be divided into three substrings), satisfying the
  following conditions:

  |$y$| ≥ 1
  |$xy$| ≤ $p$
  for all $i$ ≥ 0, $xy^iz$ ∈ $L$

I do not see how this is satisfied for a simple finite regular language. If I have an alphabet of {$a,b$} and regular expression $ab$ then $L$ consists of just the one word which is $a$ followed by $b$. I now want to see if my regular language satisfies the pumping lemma...

As nothing repeats in my regular expression the value of $y$ must be empty so that condition 3 is satisifed for all $i$. But if so then it fails condition 1 which says $y$ must be at least 1 in length!

If instead I let $y$ be either $a$, $b$ or $ab$ then it will satisfy condition 1 but fail condition 3 because it never actually repeats itself.

I am obviously missing something mind blowingly obvious. Which is?


texts: Data Structure for high dimensional data with nullable coordinates

texts:
Are there alternatives to uniform grid spatial partitioning when considering data structures for data with nullable or missing coordinate values?

For example with uniform grid spatial partitioning it is fairly trivial to extend it to allow nulls:
Given a point P in nullable R3, (x?, y? ,z?), like (5, null, 1) we can assign this point a bin (i?, j?, k?) like (2, null, 1). We can then search neighboring bins by slicing the data structure like
bins[i-1:i+1 or null, :, k-1:k+1 or null] (assuming that j bin coordinate was null).
Basically, in the null dimensions the point becomes a hyper-plane of sorts.

This is more of an academic question. I can probably use the spatial partitioning approach just fine, but wanted to know if someone might be familiar with alternatives.


texts: Misunderstanding Turing's Halting-Problem Argument

texts:
I just watched a video by Computerphile on the halting problem (https://www.youtube.com/watch?v=macM_MtS_w4) .  I’m having some difficulty understanding the argument as it is made.  Let me explain it as I see it:

So that our terminology is the same, H is a (hypothetical) program which can analyze another program to see if it halts.  H+ is a modified version of H which loops forever if the analyzed program halts and halts if the analyzed program does loops forever.

In order to run H, you need to specify 2 things – a program and the input to that program.  The Input to the analyzed program is necessary because the program’s behavior will depend on its input.

According to Computerphile’s explanation of Turing’s argument, we are asked to consider what would happen if H+ were to analyze H+ with H+ as its input.  Since there are a lot of H+’s being thrown around, let’s define H+1 as the program that I am running, H+2 as the program being analyzed, and H+3 as the input to H+2.  (Of course, H+1, H+2, and H+3 have the exact same code; they are just being used in different ways.)    My question is this:  if we require H+3 as an input to H+2, then shouldn’t we require an input to H+3?  And if we continue the pattern and use H+4 as an input to H+3, then wouldn’t this mean that we require an H+5 as an input to H+4?  And so on?

If you counter by saying that Turing’s argument doesn’t require H+3 to have an input (or that its input doesn’t have to be H+), then doesn’t this break the whole symmetry of the problem?  After all, the whole point of Turing’s argument (as I currently understand it) is that if H+2 runs on H+3 and halts then it would be a contradiction to have H+1 loop forever on H+2 since H+1,H+2,and H+3 are all identical (and vice versa were H+2 to loop forever on H+3).  But the situation isn’t identical.  In one case H+2 is running on H+3.  In the other, H+1 is running on "H+2-running-on-H+3".

I guess you could say that each H+ maybe can only look one step in front of it, so that H+1 only “sees” H+2 and H+2 only sees H+3.  But then what does H+3 see?  Doesn’t it need some input of its own? After all, whether or not H+3 halts depends on the program it’s given.    If so, this brings it back to my first point (that we would need an H+4).

It seems to me this whole argument falls apart.  Either you would need an infinite stack of H+’s which can’t happen, or you have a finite stack which because of the discontinuity at the end means that the symmetry of each level doesn’t translate to the one below it.

So what am I missing?


texts: Average case analysis by key comparisons of Max Sort

texts:
I'm having trouble approaching this average case analysis in terms of key comparisons.
The pseudo-code is as follows:
maxSort(Array) {
    for (int i = Array.length - 1; i > 0; i--) {
        x = i - 1
        max_i = findMaxPos(x) # performs x key comparisons
        swapValues(max_i, i)
    }
}

findMaxPos returns position of largest value between index 0 and x of the array. Performs x key comparisons.
I believe the worst case is W(N) = n(n-1)/2 where n is the size of the array.
I am unsure how to contextualize the algorithm in an average case in terms of key comparisons. Should I create a decision tree and show the lower bound for average behavior? Or is there a way to use permutations? Any help is greatly appreciated
Edit: For context, the original question is asking for the number of key comparisons in the worst and average case. While working out the worst case was relatively straight forward I'm unsure how to write some sort of proof or perform analysis to show the average is the same


texts: Is the set of TMs that does not reach most cells to the right computable?

texts:
Let $L_{NTF} = \{ \langle M \rangle \mid $ for every $x\in\Sigma^* $ the machine $M$ does not reach the $|x|+10$'th cell during its calculation on $x$. $ \}$.

I would like to prove or disprove $L_{NTF} \in RE$.

I know how to easily prove that $L_{NTF} \in Co$-$RE$, because it is enough to find one word $x$ such that $M$ will reach the $|x|+10$'th cell during its calculation on $x$. There is a finite number of configurations as long as the machine does not reach the $|x|+10$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $|x|+10$'th cell it is fine by me. That is to say, for a given input $x$ I can decide whether or not it reaches the $|x|+10$'th cell during $M$'s calculation on $x$.

So this tells me that $\overline{L_{NTF}}\in RE$, that is $L_{NTF}\in Co$-$RE$.

But this idea will not assist me in proving $L_{NTF}\in RE$ because I may accept a TM $\langle M\rangle$ only after I will iterate over all possible $x\in \Sigma^* $, and since $\Sigma^*$ is $\aleph_0$ I will never accept a TM $\langle M\rangle$. This is my intuition for why $L_{NTF} \notin RE$.

So for proving this I have 2 options:

Showing a reduction $L\leq L_{NTF}$ where $L\notin RE$. I've tried using $\overline{L_{acc}}, L_d$ and $L_{\Sigma^*}$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
An idea similiar to (1), just showing a reduction $L\leq L_{NTF}$ where $L\notin R$. This will also be sufficient because it will prove me that $L_{NTF}\notin R$, and since I know $L_{NTF}\in Co$-$RE$ having $L_{NTF}\in RE$ will lead to a contradiction, thus we can deduce $L_{NTF}\notin RE$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...


texts: What algorithm to use for training combinations

texts:
I would be very glad if someone could help me with my machine learning task. I have palettes of 5 colors each (in RGB format), and would like to train the neural network so that I can input a color, and the model would give me 4 other colors that would go best with it.

My training set consists of 1500 palettes (1500 * 5 = 7500 examples - each color from palettes is combined with four other). I've trained the network with multi-label classifier: one color as input (3 variables RGB) and one-hot encoded vector as output (I've predefined 68 classes, so it looks like [1 0 0 ... 1 1 1]). So basically, I have two questions:

1) Very strange, but when I try to predict colors that go best with my color, I always get the same colors, just with different probabilities (with sigmoid activation function). Why could this possibly happen? Why my probabilities never reach over 30%?

2) This still doesn't solve my problem - I get only suggestions on different colors, but these colors may not match between them. I need an algorithm that would take into account all 5 colors at once. What kind of algorithm could possibly solve this problem? Maybe combine several?

Thank you for your time reading this!


texts: How can I complete my derivation of an algorithm to solve Sudoku puzzles from my formalisation of the rules?

texts:
I'm hoping to design and implement an intuitive algorithm that solves 9x9 Sudoku puzzles. I want to do this by first formalising the basic rules of the puzzle, and then deriving principles from these that when followed should be sufficient for solving the problem. I have reproduced my (very rough) work below.

Rule 1: Each box must contain one instance of each of the numbers 1 to 9:
----- At least one instance: If (i, j) is only possible location of v in box b, then val(i, j) = v
----- At most one instance: If val(i, j) = v in box b, then for all (i2, j2) in box b, if (i != i2 || j != j2) then val(i2, j2) != v

Rule 2: Each row must contain one instance of each of the numbers 1 to 9:
----- At least one instance: If (i, j) is only possible location of v in row r, then val(i, j) = v
----- At most one instance: If val(i, j) = v in row r, then for all (i2, j2) in row r, if (i != i2 || j != j2) then val(i2, j2) != v

Rule 3: Each column must contain one instance of each of the numbers 1 to 9:
----- At least one instance: If (i, j) is only possible location of v in column c, then val(i, j) = v
----- At most one instance: If val(i, j) = v in column c, then for all (i2, j2) in column c, if (i != i2 || j != j2) then val(i2, j2) != v

Rule 4: Each cell must contain exactly one number:
----- At least one number: If (i, j) cannot contain any value except v, then val(i, j) = v
----- At most one number: If val(i, j) = v1 && val(i, j) = v2, then v1 = v2

However, I have run into a problem. Having solved Sudoku puzzles of various difficulties myself, I am aware of other principles that may need to be followed to solve a given puzzle. For instance:

----- If v must occur in one of two or three cells in box b, and these cells fall in the same row r, v cannot occur anywhere else in r.
----- If v must occur in one of two or three cells in box b, and these cells fall in the same column c, v cannot occur anywhere else in c.

These examples look like weaker versions of principles I have already written above, but I am having a hard time trying to derive them from the rules, since I want to be rigorous rather than simply adding principles ad hoc.

If anyone could give me a hand by showing me how I can go about deriving these more complex principles rigorously from the rules (ensuring that nothing is missed), I would be grateful.
Thanks.


texts: Mapping categorical data in K-nearest neighbour

texts:
I have a data set which contains categorical data, for example:

+-----+-----+------+
| age | sex | grade|
+-----+-----+------+
| 18  |  M  |  59  |
+-----+-----+------+
| 19  |  F  |  16  |
+-----+-----+------+

How can i map the sex column to numerical data? generally how can i do map categorical data to numerical data in KNN? Is this a good idea to do this mapping?


texts: Bellman-Ford - is number of interations greater than diameter?

texts:
Diameter of a connected, undirected graph is the smallest natural
  number d, so that between any two vertices of the graph exist path
  of length at most d.

  Prove or disprove: in Bellman-Ford is the number of iterations always
  equal or lower than d.

I'm trying to solve this issue. What I tried was sketching a lot of graphs, however I have failed to find a single graph where the number of iterations would be higher than the diameter.

The only graph where the number of iterations wouldn't be <= than diameter would be a graph with negative edges, however I found out that in undirected graph there can't be any negative edges, otherwhere there would be a negative cycle.

So, AFAIK the statement is correct. However, how would I prove such a statement? I don't even know how to start. Thanks for any help


texts:
So I couldn't figure this one out, what do i do when i have multiply logs as the running time of an algorithm.

For example:

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

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


texts: According to this we can do so by replacing every edge in the undirected graph with two edges backwards and forwards with the same capacity. But I'm having a hard time seeing how this prevents something like $f((u,v))=c$ and $f((v,u))=c$ (where c is the capacity in the original undirected edge) but then that means the original graph has flow $2c$. Could someone prove or explain why the capacity restrictions are still satisfied?


texts: Can a RE language be reduced to a non-RE language?

texts:
In our lecture notes about many-one reduction we showed that the following statements hold:
$$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$
$$(I)\space L' \in RE \implies L\in RE$$
$$(II)\space L \notin RE \implies L'\notin RE$$

Now I was wondering if this would also be true if you'd reverse these statements i.e.
$$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$
$$(I)\space L \in RE \implies L'\in RE$$
$$(II)\space L' \notin RE \implies L\notin RE$$


texts: P vs NP and can an oracle make P=EXPTIME?

texts:
As I understand, diagonalization cannot be used to prove or disprove P vs NP, because for some oracle $A$, $P^A = NP^A$, whereas under another oracle $B$, $P^B \neq NP^B$.

I don't fully understand this logic. Diagnolization (Time Hierarchy Theorem) proves that $P \neq EXPTIME$. Does it therefore mean that there is no oracle $X$ that could ever make $P^X = EXPTIME^X$ ?


texts: Does any language need to have a bottom type?

texts:
From wikipedia:

In type theory, a theory within mathematical logic, the bottom type is the type that has no values. It is also called the zero or empty type, and is sometimes denoted with the up tack (⊥) symbol.

The "bottomest" types I can think of in js are undefined and null, both unity types.
Notice how in TypeScript there is the explicit never bottom type for function that are not supposed to return anything, or to always throw an exception.
The question is/are:

does JavaScript have no bottom type?
if so, does that mean that languages do not need to have a bottom type?


texts: What constitutes a minimal-sum section of an integer array

texts:
I'm having trouble understanding what constitutes a "minimal sum section" of an integer array. My book defines it as the following:

  Let $a[0],\dots, a[n-1]$ be the integer values of an array $a$.
  A section of $a$ is a continuous piece $a[i],\dots,a[j]$, where $0\le i \le j < n$. We write $S_i,_j$ for the sum of that section: $a[i] + a[i+1]+\dots+a[j]$.
  A minimal-sum section is a section $a[i],\dots,a[j]$ of $a$ such that the sum $S_{i,j}$ is less than or equal to the sum $S_{i',j'}$ of any other section $a[i'],\dots,a[j']$ of $a$.

My confusion comes with one of the examples that follow this definition:

  The array [1,-1,3,-1,1] has two minimal-sum sections [1,-1] and [-1,1] with minimal sum 0.

But, wouldn't the minimal sum section be $[-1]$ ?

In a later example they give:

  array $[-1,3,-2]$

Minimal sum

  section $[-2]$

So, in the last example they definitely counted one element as the minimal sum section, but not in the first one. Any clarification on why this is so would be greatly appreciated.


texts: Shortest path given correct order of colours?

texts:
I have a directed graph $G=(V,E)$ where each vertex is a 4-D coordinate $v: (x, y, z, c)$ representing spatial coordinates $x, y, z \in \mathbb{R}$ and the non-physical parameter colour $c \in (c_{1}, c_{2},... c_{n})$. The edge weights $\omega_{v_{a} \to v_{b}}: f(x, y, z)$ are purely a function of three of the four dimensions, as this is a physical problem.

Trouble is, I wish to find the shortest path given a specific sequence of colors (eg. $c_{2}, c_{5}, c_{1}, c_{1}, c_{3}, c_{4}$). It's difficult to incorporate this into the weight function as it is non-physical. Are there well-established path traversal algorithms that find the shortest path through coloured vertices, given the starting vertex, ending vertex, and the sequence it needs to pass through? I wonder if there is already a family of algorithms that describe this problem?
I've considered something like a Hidden Markov Model that abstracts vertices of colours into hidden states, but I am not sure how to prevent one state from being visited again (whereas in a directed acyclic graph I can prevent revisiting the same vertex).


texts: Is there a logspace version of the reduction used in Cook-Levin?

texts:
The proof (one of the standard ones, anyway) for Cook-Levin uses snapshots.
E.g., see Cook-Levin proof (end of page 2, early page 3)

Now, $z_i$ ( where $z_i$ describes a snapshot of the machine ) depends on $z_{i-1}$ and $z_{prev_{m}(i)}$, but to calculate $z_i$ we cannot erase index $i$, or we will forget what we are currently calculating. What happens if we are restricted to logspace? If we keep the recursive procedure, the stack may well take more than logspace since the variable i might become very large.

And a follow up is, if such log space reduction really exists, wouldn't that imply $P$ is in $L$?


texts: NLP: Automatically categorize words semantically into non-predefined classes

texts:
I am looking for a method to categorize a given word into semantically into classes. A simple example would be:

chair -> furniture

The most reasonable way to do so that comes to my mind, would be to create a tree containing words, where chair is a predecessor of furniture. Then one could define a threshold that describes the level of the tree predecessor that should be taken as the result.

Is there some existing research/tools or even trees that fulfill the described task? I cannot find anything in google because I do not know the specific term for my problem. Keyword Clustering as a technique seems a little different, because is works on existing data and return multiple matches.


texts: Useful conditions for proving super polynomial lower bound for some kind of recurrences

texts:
Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$

Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have been written above as $n_{i,n,m}$ and $m_{i,n,m}$, but they are written above as $n_i$ and $m_i$ in a way of abbreviation for more readablity.

Let us assume that $T$ is non-decreasing w.r.t $n$, and non-increasing w.r.t $m$.

I am looking for a useful, necessary and sufficient condition so that $\exists k. T(n,m)=O\bigg(\Big(\log(m)+n\Big)^k\bigg)$

The importance of such conditions stems from their applicabilty in concluding super-polynomial lower bounds on complex recurrences of the above-mentioned form.


texts: The shortest path that visits every specified node before finally reaching the specified end node?

texts:
After asking another question(Is the last step in the Christofides' algorithm necessary), I have decided Christofide's algorithm probably doesn't solve the problem I'm facing.
Is there any algorithms that would best suit this problem?

The input is a set of nodes on a graph (an implementation would be similar to the illustration in the question), and the required output is the shortest path that visits every specified node before finally reaching the specified end node.


texts: How to prove program solves the problem?

texts:
I am preparing for the exam on Theory of Programming class. Now I am trying to solve the task from the sample paper:

Task description starts here

Given the following problem:
A problem is given by its specification:

Let S denote the following program:

Write down the conditions that are sufficient to prove that the given S program solves the given problem.
Prove that S is a solution of the given problem. Detailed explanation is required.

Task description ends here

I tried to solve this task as sequence according to this:

My question: Am I on the right path? If yes, what should I take instead of S2? If I am on the wrong path - what should I do to solve this task?

It would be great if you could suggest the book, webpage, video tutorial which contains similar tasks.


texts: Shortest path with min-sum multiplication and Boltzmann distribution

texts:
My professor presented a method to find shortest paths using the min-sum multiplication and Boltzmann distribution.
He multiplies the adjacency matrix many times and takes the $\beta$ of Boltzmann very large to find it.

I cannot understand at all the method from my notes, and I cannot find it in my book (Papadimitriou) or on Google.

He wrote something like:
$A^k_{ij}$ is the number of paths from i to j (and that's ok), and then he put $A_{ij}=e^{-\beta w(i,j)}$. Then he took the $\log$ and he used the minsum product over $A_{ij}$.
Then he told that when $\beta$ is very large, any probability distribution will convert in the path of min length.

Can you give me a link where I can study on? Or can you give me a better idea of this method?


texts: Determine if items can be ordered grouping two simultaneous criteria

texts:
For a set of items with two properties, how can it be detemined if they can be ordered in a way so that for every value of either property all items of that value are grouped together.

Obviously trying every possible ordering is out of the question.

For example, if each item has a number and a letter, the following sequence satisfies the condition:

A1->A2->A3->B3->B4->C4->D4
\---A----/  \-B--/  \-C--/
 1   2  \-3--/  \---4----/

But the following sets cannot possibly be ordered in this way:

A1, A2, A3, B1, C2, D3

A1, A2, B1, B2

I came up with a solution which is a little long to describe and seems to work, but I was curious:

Is this a known problem? Can it be reduced to a known problem?


texts: Maximum flow in a graph, and conservation of flow

texts:
The requirement for the conservation of flow in a flow network is, as I see it in the MIT lectures on Algorithms, that $\sum_{v\in V}f(u,v)=0$ for every $u\not\in \{s,t\}$ where $s,t$ are the source and sink respectively.  I think I get the intuitive idea expressed here, that there should be no accumulation or net loss in any vertex.  However, it seems to me this expression actually says "The follow out of u is always 0".  Am I confused or is the correct expression, $\forall u\not\in \{s,t\}$

$$\sum_{v\in V}f(u,v)=\sum_{w\in V}f(w,u) $$

Or is it there something about the requirement that $f(u,v)=-f(v,u)$ that takes care of this automatically?  And maybe somehow in the summation we don't pay too much attention to the placement of the $u$ in the formula?


texts:
I'm not exactly sure whether this question belongs to this SE or not, but it doesn't seem to fit elsewhere.

Say a process behaves in a deterministic fashion (that is, it gives the same output when an input is entered over and over again), then can we build it as an algorithm?; if not, can you think of a counter-example?, that is, a deterministic process which can't be modeled as an algorithm.


texts:
I know some algorithms which compute the convex hull in a continuous space. Are there efficient algorithms to compute it in a discrete domain?

For example in 3D discrete space, given the blue points, we want the convex hull including the green points. This fugure's points are plotted on the plane $v_1 + v_2 + v_3 = 7$. So, it's a pseudo 3D, e.g., green ones are $(2, 4, 1)$ and $(3, 1, 3)$.


texts:
The language

$$L = \{x^r \# y | x, y \in \{a, b, c\}^*\\
\text{
and }x\text{ is a contiguous sub-string of }y\}$$

where $x ^ r$ denotes the backward written word x, is context-free.

Can someone explain, if this statement is true? I am not able to construct a PDA, so I think the language is not context-free. Does anyone have an idea how to prove it?


texts:
Task: There are N persons. Some of the persons were meet before. I need to find pairs of persons, that were not meet before.
Example: 4 persons - A, B, C, D.
A and B were meet before.
Good solutions: (A + C, B + D) OR (A + D, B + C).
Bad solution: (C + D) because it is forrbidden to create pair (A + B).
What algorithm can help to resolve this task?


texts:
This is the = Type variable rule that I'm seeing through out the my course and unable to grasp it completely.

$$\dfrac{\phi \vdash \Gamma[\mathrm{ctx}] \qquad \Gamma(x) = \tau}
        {\phi; \Gamma \vdash x : \tau}
        \textsf{(ty-var)}$$

The first thing in antecedent looks like it's stating that $\Gamma$ is well-formed under the context $\phi$, is that right? What does the second thing in antecedent mean? I have a feeling of this but I am unable to get this simple rule.


texts: Information theory of instruction set architecture design?

texts:
Information theory to a large extent deals with how to efficiently encode messages given a probability distribution over messages.

Intuitively, it seems like we can think of machine instructions (or programs) as "messages to the CPU". Some messages are more probable than others. E.g. "add numbers x and y" is more probable than "compute the y'th square root of x", which is maybe one of the reasons why we don't have an instruction like the latter.

However there are obviously other considerations involved like computational complexity, so it doesnt seem obvious to me how information theory can be used to understand instruction set architectures. Has information theory been apllied to understand insteuction set archtectures? (I didnt find anything after a quick google search.)


texts:
Imagine the following sets :

A = Set( sortedSet(1,2,3), sortedSet(4,8))
B = Set( sortedSet(3,4), sortedSet(5,6,7) )

Where each inner list represent a cluster composed by indexed dots (1,2,3...).

I want to gather cluster sharing the dots sharing the same index into one to get :

Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )

My first attempt was to merge two Sets

Set( sortedSet(1,2,3) ), sortedSet(3,4), sortedSet(4,8), sortedSet(5,6,7) )

and then merge each subset with subset of the same set where they share a common element. And repeat this process $k$ times with the result set until it doesn't change.

0 : Set( sortedSet(1,2,3,4), sortedSet(3,4,8), sortedSet(5,6,7) )
1 : Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )
2 : Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )
1 = 2 then Stop

Unfortunately i think this method is upperbounded in a bit less than $O(k.n^2)$ where n is the total number of elements in every subsets.

My second attempt was to get links which connected subsets of A and B.
Add to each A's subsets every sub sets of B which are connected to them from the link A -> B to get A'. Then use link B -> A to gathered A' subsets to get A''. Finally i apply my first attempt on A'' to get A''' and add it the lonely clusters in A and B.

So my final result is A''' + A_lonely + B_lonely

I use optimization that i know like using SortedSet and exist method (rather than go through each subset to know if they share a common element).

The second method works way faster (5min VS 45min) for a precise test.
But i know that i can still encounter the same issue due to the step A'' -> A''' which remains quadratic.

Any optimizations i could use or proper solution is welcome !


texts: What is difference between LAG (Left Atrributed Grammar) and LATG (Left Attributed Translation Grammar)?

texts: I am reading Compilers and am unable to understand difference between these two terms. I could not find any text which has clearly mentioned how they differ but these two separate terms are being used. Can someone please explain me?


texts: Do any decision problems exist outside NP and NP-Hard?

texts:
This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard.

In order to be in NP, problems have to have a verifier that runs in polynomial time on a deterministic Turing machine. Obviously, all problems in P meet that criteria, but what about the problems with sub-exponential complexity? They do not belong to P and it's not obvious to me that they all have efficient deciders. And they certainly don't qualify for NP-complete.

I'm willing to believe that all decision problems are either NP or NP-hard or both, but nobody has actually said that (that I can find). I'm also willing to believe that such problems do exist, even if they are very contrived. Maybe someone more knowledgeable can put this issue to rest for me. Thanks.

Edit

I abused the term 'subexponential' in my question. In my mind it meant some problem with a complexity between exponential and polynomial like L-notation in this table. See the links in Raphael's answer for more details.


texts: Complexity of Problems and Ease of Verification

texts:
Comparison-based sorting algorithms have a minimum worst-case complexity of $O(n \log n)$, while it is easy to check that an array is sorted in $O(n)$ time.

Are there other problems with proven minimum complexity $O(n^k)$ for some $k > 1$ that can be checked in $O(n)$ time? How high can $k$ get?


texts: $f(x) = \sqrt{x^{2}+1}-1$ (Loss of Significance)

texts:
Let us say that I want to compute $f(x) = \sqrt{x^{2}+1}-1$ for small values of $x$ in a Marc-32 architecture. I can avoid loss of significance by rewriting the function
$$f(x)=\left(\sqrt{x^{2}+1}-1\right)\left(\frac{\sqrt{x^{2}+1}+1}{\sqrt{x^{2}+1}+1}\right)=\frac{x^{2}}{\sqrt{x^{2}+1}+1}$$
Even though I can solve the problem, I do not know/understand why the solution has avoid the loss of significance?


texts: Does strong typing contribute to better performance optimization by compiler?

texts:
Do guarantees provided by the type systems enable better performance optimizations by the modern compilers? I found a 20+ year article suggesting that it would. Also, intuitively speaking, knowing more about the code in advance should also be useful. However, a friend claims that modern JIT compilers make such claim irrelevant. In his words:

This is a paper from 1998. Today, JIT compilers eliminate many of the cases mentioned in the paper for dynamically typed systems. For example, JavaScript uses integer arithmetic for integer types, without knowing the type declarations in advance. I doubt if predeclared types are as significant for performance today as they were two decades ago. Native instruction set and memory management mechanisms seem to have much more influence on performance to me.

What's the situation in modern compilers?


texts: How “logic-based symbolic reasoning” and “ontology” are related?

texts:
I have a basic understanding of knowledge representation systems, semantic networks and ontologies. But I can not relate my understanding to the reasoning.

How the reasoning is applied on ontologies and semantic networks?


texts: reduction from SET-COVER to VERTEX-COVER

texts:
I've come with an idea for reduction from the set-cover problem to the vertex-cover problem, But I'm not sure if this reduction is correct. I saw in  this post's comments that "There cannot be a nice reduction of this sort".

Consider the set of $S$ to be $S_1,...,S_n$ where the element of $S$ is $s_1, ..., s_m$. In the graph $G=(V,E)$ for each $S_i$ there is a vertex, and an edge from $S_i$ to $S_j$ will be iff there is some element $x\in S_i \land x\in S_j$.

is this reduction even right?


texts: How much better are conservative updates for count-min sketch?

texts:
I've been reading about count-min sketch and I'm interested in the performance of this data structure when doing conservative updates. To my understanding from the Wikipedia article, conservative updating means that when you see an item, instead of incrementing all the counters you only increment the counter(s) that have the lowest current count. Intuitively, I understand that this method will give a strictly better estimate than the standard update procedure because collisions are now less likely to cause us to overestimate a count.

I know that it's possible with traditional count-min sketch to tune the parameters of the data structure based on the error rate $\delta$ you're willing to tolerate. This error analysis shows that to solve $\epsilon$-approximate heavy hitters with probability $1 - \delta$, we should use a sketch with $\frac{e}{\epsilon}$ columns and $\ge \ln \frac{1}{\delta}$ rows/hash functions. What would this analysis look like if we were performing conservative updates?

I found this paper which I believe calculates the probability of a false negative using conservative updates to be $(1 - (1-\frac{1}{W})^N)^d$ where $W=\frac{e}{\epsilon}$ is the number of columns, $N$ is the number of unique additions, and $d$ is the number of rows. What I don't understand:

How does this calculation take into account the fact that only the counter(s) with lowest current count are incremented in each step?
Intuitively, why does this probability depend on the size of the stream $N$ (where it seems that the probability of false negatives in traditional count-min sketch does not?)


texts: Pumping Lemma to prove that L is not context free

texts:
I have the language  and I want to prove that is not context-free.

So I started like this:
 is variable.
Choose w =

Case 1:
vxy has no c. Choose i = 2
 has more a than c or more b than c.

Case 2:
vxy has no a.

At case 2 I don't know how to continue, I'm confused since I seem to be not able to prove that there is a case where vxy has no a and the word's b-count or c-count is smaller than the amount of a's.


texts: Is two arrows on each state necessary in DFA?

texts:
In DFA, is two arrows on each state necessary?

Or it depend on language alphabets? I mean if there is $\Sigma = \{a\}$ then there should be one arrows on each state.

OR if there are $\Sigma = \{a , b\}$ then there should be two arrows on each state.

OR if there are $\Sigma = \{a , b , c\}$ then there should be three arrows on each state.

and so on...


texts: one for loop wraps 2 indexof method, what is the time efficiency?

texts:
I'm confused about how to know the time / space efficiency.

If there is an array whose size is n, do a for loop on this array, so that time efficiency should be O(n) = n, where n is array size. then if I have two indexof methods in the loop, indexOf and lastIndexOf, should the O(n) become n*(2n)? because each of the indexof methods has the time efficiency of n as well just like a for loop?
how to know the space efficiency of this method?

char firstNotRepeatingCharacter(String s) {

    char[] str = s.toCharArray();
    // n
    for (int i = 0; i < str.length; i++) {

        char item = str[i];
        // 2n
        if(s.indexOf(item) == s.lastIndexOf(item)) return item;

    }
    // 2n2

    return '_';
}


texts: Does P = NP in Cellular Automata of Hyperbolic Spaces?

texts:
I read a few years ago in this book that NP problems are tractable in the space of cellular automata in the hyperbolic plane. What does this mean? Does P = NP according to these books/papers?
Some excerpts from the paper:

It is well known that if we have binary trees at our disposal “for free”, it is possible to solve NP-problems in polynomial time, see [14, 5]. However, it is not immediate to implement binary tree algorithms in the pentagrid, and the goal of this section is to indicate how one can proceed.

From my understanding, the P = NP problem is looking for polynomial-time algorithms to solve complicated problems. From my cursory glance through the books and papers, it seems to suggest that he has solved the problem. What am I missing?
Here is another paper, titled In Some Curved Spaces, We Can Solve NP-Hard Problems in Polynomial Time: Towards Matiyasevich's Dream.


texts: Characterize the Equivalence Classes of a Language

texts: Given a language $A = \{a^nb^n : n >= 0\}$, how would one go about characterizing the equivalence classes of this language, in order to apply Myhill-Nerode to show it is not regular? The idea and meaning of "characterizing equivalence classes" is what I am struggling with.


texts: Every LEFT-RESET Turing machine has an equivalent conventional Turing machine

texts:
I am working on a proof of the theorem that every LEFT-RESET Turing machine has an equivalent conventional, single tape Turing machine. The transitions for the LEFT-RESET Turing machine are {Right, RESET}, and the transitions for the conventional Turing machine are {Left, Right}. Here is the general outline of my proof:

Given a LEFT-RESET Turing machine $T_1$ and a conventional, I will prove that $T_1$ has an equivalent conventional Turing machine $T_2$. There are two possible transitions for $T_1$: right and reset. The right transition of $T_1$ is identical to the right transition of $T_2$. When $T_1$ performs a reset, $T_1$ moves its read-write head left until it reaches the leftmost cell on the tape. Therefore, a LEFT-RESET Turing machine is equivalent to a conventional Turing machine. Q.E.D.

Do I have to prove that there is a series of transitions on $T_1$ that are equivalent to a single left transition on $T_2$? Other write-ups I have seen include this, but if the LEFT-RESET Turing machine cannot perform a traditional left transition as an operation, I do not understand why it is part of the proof.


texts: Can someone clarify landau symbols definition please?

texts:
I'm more or less familiar with the landau symbols, most specifically in computer science for complexity, however I was wondering if someone could clarify a bit for me. I'll just mention that I know that technically the correct notation is to say $f(n)$ is an element of $O(f(n))$, not $f(n) = O(f(n))$.

Loosely, my understanding is this, given$ f(n) = n^2 + 2n +log(n)$ Big O represents the upper magnitude, so it would be correct (according to a past CS tutor), but not very accurate, to say $O(f(n)) = n^3$, but incorrect to say $O(n) = log(n)$, whereas the $Ω(f(n)) $represents the lower bound, so it would be correct, but inaccurate to say $Ω(f(n)) = log(n)$ or (not sure about this one), $Ω(f(n)) = 1$.

I know that $Θ(f(n))$ is defined as the intersection of $O(f(n))$ and $Ω(f(n))$, but is it valid to drop off lower orders of magnitude in the case of $Θ(f(n))$? ie. is $Θ(f(n)) = n^2$ correct? If not, what is the correct equality?

What I am entirely unsure about is $o(f(n))$ and $ω(f(n))$. I've seen the mathematical definitions and I know that the only difference between them and $O(f(n))$ and $Ω(f(n)) $respectively is that rather than "there exists C", it is "for all C", but my understanding of mathematical symbols is (at this stage) embarrassing. If anyone could shed some light on all of the above it'd be appreciated, thanks.


texts: Difference between the way RISC and CISC handles interrupts?

texts: I know the general basics of how RISC and CISC processors differ, but I also want to know whether the two differ in the way they handle interrupts.


texts: Proving a set is at a certain level of the arithmetical hierarchy

texts:
I'm interested in methods for proving a set is at some level $\Sigma^0_n$ (or $\Pi^0_n$) in the arithmetical hierarchy, and in particular, proving it is at the level with the smallest $n$ possible.

I know that a set is in $\Sigma_n^0$ if it can be expressed as a sequence of $n$ quantifiers (starting with $\exists$ and then switching between $\exists$ and $\forall$) on variables, followed by a decidable formula on those variables. I also know membership in $\Pi_n^0$ can be proved in a similar way, just starting with $\forall$ instead of $\exists$.

These slides use that approach to place several sets at different places in the arithmetic heirarchy (on slides 26,31,33, and 35, for example).

Here's where things start to get tricky for me. If a language is in $\Sigma^0_n$, it seems like it's also trivially in  $\Sigma^0_{n+1}$,  $\Sigma^0_{n+2}$, and so on -- because you can take the formula you used to show that the language was in $\Sigma^0_n$, and tack on "dummy" quantifiers that don't actually do anything.

So, let's say I want to proving that a language is in $\Sigma^0_n$, but not $\Sigma^0_{n-1}$, i.e. I want to put the language in its lowest spot on the arithmetical heirarchy. Now, it seems like just showing that the language corresponds to a  a $\exists,\forall,...$ sequence followed by a decidable formula won't cut it, because there's a chance that I was adding useless quantifiers to artificially inflate my language's difficulty. What techniques exist to get around this issue -- How do I prove that my quantifiers are "essential", so to speak?

I'm definitely interested in being as formal as possible with such a proof, so any links to textbooks or papers would be much appreciated.


texts: Keywords for the science articles search (parallel computing)

texts:
Often, similar ideas or works have vastly different namings or covers. This is a hassle for searching in distant fields, especially in a non-native language.

Idea. We mathematically model (Petri nets, graphs, automatons, any formal way) architectures and algorithms. One of the models can be substituted for various behaviour data or even its implementation or mix of the model with a real data in general case. Then we simulate their interactions on paper or on an instrumental computer and obtain some useful predictions with aim on parallel computations without actually write the code and measuring its characteristics (full finished code at least, this isn't a simple profiling of a real implementation). For example, this way could trying to predict scaling, algorithm and architecture matching quality, performance, comparative measures of variants, etc.

Could you, please, name not obvious keywords or other leads (authors, titles, surveys are the most useful) to the articles containing similar ideas and their implementations?

"Obvious" keywords are "model, architecture, interaction, parallel computations, imitation, simulation" and their combinations. Synonyms could be missed too, if they aren't found by goggle with "~."


texts: Hard Drive Seek Time using FIFO, SSF, SCAN

texts:
A hard disk spins at 6000 rpm (revolutions per minute), and it takes 100 μs (on average) for the head to traverse one track. Consider the following sequence of disk track requests: 27, 129, 110, 186, 147, 41, 10, 64, 120. Assume that initially the head is at track 30 and is moving in the direction of decreasing track numbers. Compute the time it takes to serve the requests using (1) FIFO, (2) SSF (Shortest-Seek First), (3) SCAN.

I understand the difference between the different algorithms and I generally get how to calculate it.

My questions is, when I calculate the Average rotational time, i.e. (60/6000) / 2 = 5ms, do I need to multiply this by the number of tracks moved?

My FIFO calculation as an example:

(3+102+19+76+39+106+31+54+56) * (5ms + 0.1ms) = 2478.6ms

I add up the number of tracks moved and multiply this by the average rotational time + the time it takes to traverse each track.

Is this approach correct?

Thank you


texts: Cache consistency in uniprocessor system

texts: In a uniprocessor system, can we have a Cache consistency problem? For sure, it exists in a multiprocessor system. But I wonder if it exists in a uniprocessor system and in which scenario.


texts: Decision problem which belongs to P reduced to a decision problem which belongs to NP?

texts: Is it possible to have a decision problem $A$ which belongs to P and reduce it to a decision problem $B$ which belongs to NP, i.e. $A \leq_{\mathrm{p}} B$, where $A$ belongs to P, $B$ belongs to NP?


texts:
I've been studying the low-level hardware implementations of floating point numbers and doing an exercise to design a custom floating point implementation.

I know that being able to represent negative zero is important for some purposes, but ran across a curious question.

Complex numbers are generally represented by two fp numbers. Is there any use in being able to represent negative zero on the imaginary line? Does anybody use this for anything?


texts: Can a subset of an NP-complete problem be in P?

texts:
The problem is NP-complete (proven) for all input data (without exception).

We assume that P != NP.

Is it possible that there is an (infinitely large) subset of the problem, for which this subset is in P?

Theoretical question.


texts: How can I explain to my parents that I study programming languages?

texts:
I am currently finishing my MSc in computer science. I am interested in programming languages, especially in type systems. I got interested in research in this field and next semester I will start a PhD on the subject.

Now here is the real question: how can I explain what I (want to) do to people with no previous knowledge in either computer science or related fields?

The title comes from the facts that I am not even able to explain what I do to my parents, friends and so on. Yeah, I can say "the whole point is to help software developers to write better software", but I do not think it is really useful: they are not aware of "programming", they have not clue of what it means. It feels like I am saying I am an auto mechanic to someone from the Middle Ages: they simply do not know what I am talking about, let alone how to improve it.

Does anyone have good analogies with real-world? Enlightening examples causing "a-ha" moments? Should I actually show a short and simple snippet of code to 60+ year-old with no computer science (nor academic) experience? If so, which language should I use? Did anyone here face similar issues?


texts: Random generator considerations in the design of randomized algorithms

texts:
It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. Perfect random sources are unavailable in practice. Although it is proved that for all $0 < \delta \leq \frac{1}{2}$ the identities BPP = $\delta$-BPP and RP = $\delta$-RP hold, it is not true that the original algorithm used for a prefect random source can be directly used also for a $\delta$-random source. Instead, some simulation has to be done. This simulation is polynomial, but the resulting algorithm is not so efficient as the original one.

Moreover, as to my knowledge, the random generators used in practice are usually not even $\delta$-sources, but pseudo-random sources that can behave extremely badly in the worst case.

According to Wikipedia:

  In common practice, randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior.

In fact, the implementations of randomized algorithms that I have seen up to now were mere implementations of the algorithms for perfect random sources run with the use of pseudorandom sources.

My question is, if there is any justification of this common practice. Is there any reason to expect that in most cases the algorithm will return a correct result (with the probabilities as in BPP resp. RP)? How can the "approximation" mentioned in the quotation from Wikipedia be formalized? Can the deviation mentioned be somehow estimated, at least in the expected case? Is it possible to argue that a Monte-Carlo randomized algorithm run on a perfect random source will turn into a well-behaved stochastic algorithm when run on a pseudorandom source? Or are there any other similar considerations?


texts: Is CPU Registers part of Primary Memory?

texts:
A friend of mine appeared in an exam recently, and one of the question asked was regarding CPU Registers, which has two points:

(a) CPU Registers are part of Primary Memory
(b) They are volatile

And the choices given were:

Both (a) and (b) are true
Only (a) is true
Only (b) is true
None of the above

They are volatile. So the second and forth options can be avoided. The confusion was regarding whether it was part of Primary Memory. To my knowledge, CPU Caches, RAMs and ROMs can be called as primary memory. But will CPU registers would be called as part of primary memory? Or will it be considered as Level0 caches?


texts: Generalization of automaton - Sipser example 1.33

texts:
I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure
that my transition function is wrong. I'd like some advice on how to fix that and how to simplify the notation such that to make it simpler.
Let $k > 0$ be a natural number and $B = \{n_{1}, n_{2}, \cdots, n_{k}\}$ a set with $k$ natural numbers.
Let $\Sigma = \{0\}$ an unary alphabet and let
$$C = \{0^{i} \in \Sigma^{*} \mid i \in \bigcup_{b \in B} \{i \in \mathbb{N} \mid i = 0\  mod\ b \}\}$$
the set of all strings $0^{i}$ such that $i$ is a multiple of some natural in $B$. Construct a nondeterministic finite automaton
$N$ that recognizes C.
We will construct a NFA that recognizes C.\
Let $k > 0$ be a natural number and $B = \{n_{1}, n_{2}, \cdots, n_{k}\}$ a set with $k$ natural numbers.
Let $N = (Q, \Sigma, \delta, q_{0}, F)$ where
$Q = \{q_{i,j} \mid 1 \leq i \leq k, 0 \leq j < n_{i}, n_{i} \in B\} \cup \{q_{start}\}$
$\Sigma = \{0\}$
for any $q \in Q$, any $a \in \Sigma \cup \{\epsilon \}$, $i, j \in \mathbb{N}$ and $n_{i} \in B$
$\delta(q, a) =
  \begin{cases}
    \{q_{i, 0} \in Q \mid 1 \leq i \leq k\} & q = q_{start},\ a = \epsilon \\
    \emptyset & q = q_{start}, a \neq  \epsilon \\
    \{q_{i, l} \in Q \mid 1 \leq i \leq k, 0 \leq j < n_{i}, l = (j + 1)\ mod\ n_{i} \} & q \neq q_{start},  a = 0 \\
    \{q_{i, j} \in Q \mid 1 \leq i \leq k, 0 \leq j < n_{i}\}  & q \neq q_{start},  a = \epsilon \\
   \end{cases}$
$q_{0} = q_{start}$
$F = \{q_{i, 0} \in Q \mid 1 \leq i \leq k\} $
After I convinced myself that the 3rd and 4th rule of the transition function above was wrong I rewrote it, as follows:
$\delta(q, a) =
  \begin{cases}
    \{q_{i, 0} \mid 1 \leq i \leq k\} & q = q_{start},\ a = \epsilon \\
    \emptyset & q = q_{start},\ a \neq  \epsilon \\
    \{q_{i, (j+1)\ mod\ n_{i}} \} & 1 \leq i \leq k, 0 \leq j < n_{i},\  q = q_{i, j},\ a = 0 \\
    \{q_{i, j}\} & 1 \leq i \leq k, 0 \leq j < n_{i},\   q = q_{i, j},\ a = \epsilon \\
    %%\{q_{i, l} \in Q \mid 1 \leq i \leq k, 0 \leq j < n_{i}, l = (j + 1)\ mod\ n_{i} \} & q \neq q_{start},  a = 0 \\
    %%\{q_{i, j} \in Q \mid 1 \leq i \leq k, 0 \leq j < n_{i}\}  & q \neq q_{start},  a = \epsilon \\
   \end{cases}$


texts: FA for w when length of w is even or divisible by 3

texts:
I want to construct a FA for the language

$\{w \in \{a,b\} | $length of w is either even or divisible by 3$\}$.

I've been playing around with some FAs, but I can't seem to create one that does the job. I can easily create one that accepts words with even length, and also one that accepts words with lengths divisible by 3, but I am unable to combine these.

This is my attempt:


texts: Time complexity of arithmetic operations

texts:
I want to calculate the time complexity of the listed algorithms, please correct if I'm doing something wrong:
The question is, do some operations like multiplying, dividing, or plus really affect on time complexity ?

// Time complexity is O(log n)
    void calculate(n: Int) {

        while (k < n) {
            k *= 2 //or k *= k
        }
    }

// Time complexity is O(n)
void calculate(n: Int) {

    while (k < n) {
        k += 1000
    }
}

//Time complexity is O(log n)
void calculate(n: Int) {

    k = n

    while (k > 1) {
        k /= 4
    }
}


texts: Show the problem of a machine visiting infinitely many tape cells on some input is undecidable

texts:
I am attempting to prove the following problem is undecidable. Given a Turing machine $M$ and input $x$, does $M$ visit infinitely many tape cells on input $x$?

I am considering a reduction from the halting problem. Is this the right approach?


texts: Is Post's correspondence problem recognizable?

texts: I want to know whether Post Correspondence Problem (PCP) is recognizable. I learnt how to demonstrate the undecidability of PCP. I thought to use the similar approach for recognizability too i.e. to considering MPCP and show whether it is recognizable. I am not sure if it is a good approach.


texts: What is the closed-form expression for $T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1$ where $T_1 = 1 ?$

texts:
Problem:

  Find the closed-form expression for$$
T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1
\tag{1}
$$where $T_1 = 1 .$

Calculating this sum I came up with the following result:
$$
T_n = 8^{\left(n-1\right)}
\tag{2}
\,,$$
but is this result correct?

I know the sequence is:$$
\begin{align}
 T_1 & =  1 \\
 T_2 & =  8 \\
 T_3 & = 64 \\
     & ~~\vdots
\end{align}
$$

Questions:

What would be the closed-form of $T_n ?$
What would be the best way to find it?


texts: About a step in the analysis of Quicksort by Sedgewick and Wayne

texts:
In the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations:
$$\begin{gather*}
C_N = N + 1 + (C_0 + C_1 + \dots + C_{N-2} + C_{N-1})/N + (C_{N-1} + C_{N-2} + \dots + C_0)/N\\
NC_N = N(N+1) + 2(C_0 + C_1 + \dots + C_{N-2} + C_{N-1})\\
NC_N - (N-1)C_{N-1} = 2N + 2C_{N-1}\\
C_N/(N+1) = C_{N-1}/N + 2/(N+1)\\
C_N\sim 2(N+1)(1/3 + 1/4 + \dots + 1/(N+1))\end{gather*}$$

How did they get the last transformation?

It is also written that the parenthesized quantity in the last expression  is the discrete estimate of the area under the curve $2/x$ from $3$ to $N$? How is it related to quicksort?


texts: Algorithm playing modification of "Hey, That's My Fish!" game

texts:
Ok, I must admit this a task from my studies but I'm stuck.

Rules of the game are on Wikipedia. However, we have a modified version: on input we have a board with x fields, there are y penguins on some fields, there may be gaps between fields. All penguins are the same, they can move only to the farthest possible location (in a straight line, can't jump over gaps and other penguins). There is one player and he needs to move the penguins in such manner so as to get the maximal number of fish. I have to come up with an algorithm that finds the sequence of moves that leads to the best possible result.

I tried something like guessing the final arrengment of the fields (f.e. all the penguins left on fields with just one fish each) and then reverse-engineer the steps but I didn't go any further with my idea.

I also thought it would be probably good to represent this as a graph, possibly with weighted edges and then do some graph search but again, I don't know what next.

Finally, there was a thought about using Monte Carlo method. However, this just seems too hardcore for a class project like this and that would be too diffult for me.

Any ideas where should I start?


texts: Problems in P with provably faster randomized algorithms

texts:
Are there any problems in $\mathsf{P}$ that have randomized algorithms beating lower bounds on deterministic algorithms? More concretely, do we know any $k$ for which $\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)$? Here $\mathsf{PTIME}(f(n))$ means the set of languages decidable by a randomized TM with constant-bounded (one or two-sided) error in $f(n)$ steps.

  Does randomness buy us anything inside $\mathsf{P}$?

To be clear, I am looking for something where the difference is asymptotic (preferably polynomial, but I would settle for polylogarithmic), not just a constant.

I am looking for algorithms asymptotically better in the worst case. Algorithms with better expected complexity are not what I am looking for. I mean randomized algorithms as in RP or BPP not ZPP.


texts: Question regarding a particular type of graph

texts:
Let $G = (V,E)$ be a directed graph where every vertex is represented by an $n$ bit string. The edges are represented by two polynomial-sized circuits $S$ and $P$. There is an edge from $u$ to $v$ if and only if $S(u) = v$ and $P(v) = u$. I am trying to prove:

$G$ just contains paths, cycles, or isolated vertices.
Let $A_{G}$ be the adjacency matrix of $G$. Consider $H = \frac{1}{2} A_{G}$. Then, $||H||_{2} = 1$.


texts: How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack?

texts:
I am now studying Knapsack Problem (KP), and find the Meet-in-the-middle algorithm described in Wikipedia a little unclear that, how to realize it in the theoretical time complexity of $O^*(2^{n/2})$? I can understand the algorithm for Subset Sum Problem (SSP) which is a particular instance of 0-1 KP, but for the generalized problem there might be something wrong with the step:

  for each subset of A do
      find the subset of B of greatest value such that the combined weight is less than W

As I understand, this is to search (eg. do binary search) on combined weights of all subsets of B, which takes logarithm time for each search. But after knowing which subsets have combined weight less than W, how to find the one of greatest value? If search on values of the subsets with weight < W, it takes linear time to find the maximum since the list of value is unsorted this time. As a result, the total time complexity is no longer $O^*(2^{n/2})$, but something like $O^*(2^n)$.

Even if it starts from finding the subset of greatest value (easy for a table) first without constriction on combined weight, after that, verification of weight will probably turn false and thus more tests are needed for other subsets, of which the number seems associated to the table size linearly again.

Now I can only assume the total value and combined weight are strongly positive correlated, so that after finding the subset with maximum allowed weight, it takes only constant time to search around this subset for the exact one of greatest value. But I am not satisfied with this explanation. So anyone has better ideas about this issue?

PS: I have read the original paper by Horowitz, Ellis and Sahni, Sartaj, but I found the problem defined there is a decision problem rather than the common optimization problem. Maybe somebody can provide ideas in this direction.


texts:
I am working on the following homework exercise:

Let $G = (V,E)$ be an undirected graph and $c: E \rightarrow \mathbb{R}$ it's cost function. Further let $T = (V,E')$ be a spanning tree in G.

I need to show the equivalence of the following statements:

$T$ is a MST.
For all $e = \{x,y\} \in E \setminus E'$ holds: No edge of the (unique) path from $x$ to $y$ has a higher cost than $e$.
For all $e \in E'$ holds: Let $C$ one of the two connected components of $T-e$, then $e$ is an edge with minimal weight in $\delta(V(C))$.

I have done $1) \implies 2)$ and $2) \implies 3)$, but I do not know how to prove $3) \implies 1)$. Could you give me a hint?

EDIT:
Please note that $\delta$ refers to the cut, i.e.:

$$\delta(X) = \{ \ \{u,v\} \in E(G) : u \in X \text{ and } v \notin X \}\}$$


texts: If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?

texts: Is there a non-regular language over unary alphabet $\{a\}$ which has a Myhill-Nerode equivalence class that is not a singleton?