texts: Is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP?

texts:
I was reading a paper and I came to the following :

"Since independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP (see [19]) for any fixed $\epsilon> 0$, the ..." where [19] is the following article : D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In STOC, pages 681–690, 2006.

My question: is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP? Because I cannot find this result in the cited article. However, I can find the results about max clique and chromatic number. What I am missing?


texts:
I'm trying to find An efficient algorithm for the following problem:

I have $n$ sets of numbers (different sets might have common numbers) and I need to find union combination of $k$ sets that Will yield the biggest set.

For example: if i have the sets $A1=\{1,3,4\},  A2=\{1,2,4\}, A3=\{5,7\}$ in that case $n=3$ and lets say that $k=2$.
 $|A1 \cup A3| =5$ or $|A2 \cup A3| =5$ will yield the biggest set
In contrast to $|A1 \cup A2|$ = 4.

If this is np hard question (i don't know if it is) a good Approximation will be fine
I think that brute force is $O({n \choose k})$ operations.


texts: why is this computational method by Knuth "effective" and "powerful"?

texts:
This is a follow-up question regarding Knuth's one formulation of the concept of an algorithm here. I am asking it here because I do not have enough reputation to post a comment to that question. To make my question self-contained, here it goes.

Knuth introduces the following formulation which "restrict the notion of algorithm so that only elementary operations are involved", (copied from the above mentioned question):

  Let $A$ be a finite set of letters. Let $A^*$ be the set of all strings in $A$ (the set of all ordered sequences $x_1$ $x_2$ ... $x_n$ where $n \ge 0$ and $x_j$ is in $A$ for $1 \le j \le n$). The idea is to encode the states of the computation so that they are represented by strings of $A^*$ . Now let $N$ be a non-negative integer and Q (the state) be the set of all $(\sigma, j)$, where $\sigma$ is in $A^*$ and j is an integer $0 \le j \le N$; let $I$ (the input) be the subset of Q with $j=0$ and let $\Omega$ (the output) be the subset with $j = N$. If $\theta$ and $\sigma$ are strings in $A^*$, we say that $\theta$ occurs in $\sigma$ if $\sigma$ has the form $\alpha \theta \omega$ for strings $\alpha$ and $\omega$. To complete our definition, let $f$ be a function of the following type, defined by the strings $\theta_j$, $\phi_j$ and the integers $a_j$, $b_j$ for $0 \le j \le N$:

  $f((\sigma, j)) = (\sigma, a_j)$ if $\theta_j$ does not occur in $\sigma$
  $f((\sigma, j)) = (\alpha \phi_j \omega, b_j)$ if $\alpha$ is the shortest possible string for which $\sigma = \alpha \theta_j \omega$
  $f((\sigma,N)) = (\sigma, N)$

He describes this formulation as effective and powerful.

My questions are:

What is the purpose of $\alpha$ being the "shortest possible string for which $\sigma = \alpha \theta_j \omega$?
Why is it so powerful? For example, if we are doing repeated multiplication (say compute $x^{10}$ given some $x \in I$), the string replacement values $\phi_j$ have to be predefined without knowing the value of $x$; but it seems that $\phi_j$ would have to depend on the specific value of $x$. So how does it really work?

Clearly I am missing something. Any help would be appreciated!


texts: Regularity of a language constructed from a know regular language

texts:
I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language:
$$
\{x|\exists n \ge 0 \; \exists y \in A \; y = x^n\}
$$
I've attempted to show that this is regular by a contradiction using Myhill-Nerode, by assuming it has infinite index, and showing this means that $A$ must have infinite index. However, I cannot seem to get this proof to work, because taking representatives of each class lets me show an infinite number of pairs of elements in $A$ that are not in the same class, but these elements do not uniquely correspond to my representatives, so I cannot show that an element is not in the same class as infinitely many others.
However, the book seems to indicate that the solution should be construction.
I can also easily see the construction for a NFA if $n$ was fixed, but this doesn't seem to offer any help, as this makes the states depend on $n$ (by using tuples of states, and simultaneously moving states once).
If anyone could suggest how to go about constructing the required automata, that would be very helpful.


texts: Algorithm to find player position in a 2D grid when all you know is the directional steps he has taken

texts:
Given the 2D grid shown below, where blue tiles can be visited and island tiles cannot.

Given that we do not know the starting position of a player on this grid.

Given that the player can move 1 step in any cardinal direction every turn.

Given that the player cannot visit tiles he has already visited.

Given that we are told every turn in which direction the player has moved.

What would be a computationally efficient algorithm to pinpoint the player's location in the least amount of turns?

One way that comes to mind that would give me good results but would probably be computationally intensive is to try to apply the player's path to every possible starting position. If we can traverse the path without hitting an island or going off the map, then the end tile is a valid possible position for the player. At first we would have a lot of possible positions for the player but eventually, after several turns, we'd end up with only one possible position.

I don't very much like that approach as it seems computationally heavy.

Instead, I've implemented a simple solution using a bounding box. At the beginning of the game, the player could be anywhere. But as soon as he moves, we can narrow the bounding box. For instance, if the player's first move is north, we now know that he can't be in the bottom row of the map. All that is needed is to keep track of the top left and bottom right coordinates of that box and update them every turn according to the enemy's movement until the box is eventually narrowed down to the player position.

I like this solution because it is simple and computationally light. The problem is that it doesn't take into account the islands and the players' previously visited cells. Therefore, only when the bounding box hits the grids' limits can we narrow it down. If the player starts in the middle of the map and tends to stay there, it can take a long time before narrowing down his position.

Is there a way to refine my solution (bounding box) in a way that would at least account for the islands and at best for the player's visited tiles as well? If not, what other algorithm could I use?


texts: In this example of determinising an NFA, isn't there an edge missing in the result?

texts:
I am reading a computer theory book and came across the following example converting a NFA to a DFA:

My question is, would you not need an edge labeled $b$ going from the $x_4$ node on the right to the null collection state?


texts: Updating connections weights in neural networks

texts:
I am learning about neural networks and have a couple of things I don't understand.

Firstly, in competitive learning I understand that only the neuron with the strongest output is reinforced. That is done in a manners imilar to:

Δwi*j = I(j)*h(i)

Where w* indicates the 'winning' neuron, j indicates the input we are considering, I(j) is the value of such input and h(i) is the sum of all weighted inputs. This is repeated for each connection leading to the winning neuron.

My question is... Why? Why not simply, for example, increase the connection by an arbitrary amount? Or by another function? I have done quite some research, but still can't make sense of this.

Thanks!


texts: What is the graph with $8$ vertices and $12$ edges that has the most spanning trees?

texts: I'm not sure if this is an open question, but what is the graph with $8$ vertices and $12$ edges that has the most spanning trees?


texts:
I have an arbitrary 2d area on the xy plane. I want to cover it with N discs such that all points in the area have at least one disc overlapping it. A disc with center (xc, yc) placed inside this area has a radius r that is a function of (xc,yc).

I am looking for references or algorithms that can help me to minimize N and generate the disc coordinates. So far the papers I've turned up on the discrete unit disk covering (DUDC) problem assume equally sized discs.

Luckily, for my particular application, r = f(x,y) is somewhat insensitive to changes in x and y. The heuristic I've been using is to use a modified hexagonal packing, but I would love to explore different approaches.

If anyone has any papers or online references that I could consult, I'd really appreciate it! I am not a computer scientist so if this is covered in a good textbook, I'd also be open to purchasing that.

I would be extra happy if it also discussed ways of minimizing N by allowing some degree of uncovered space, and also did a treatment on using ellipsoids instead of uniform radius discs.


texts: Prove the correctness of Tarjan's off-line least-common-ancestors algorithm

texts:
Tarjan's off-line least-common-ancestors algorithm is given as follows:

  LCA($u$)

  Make-Set($u$)
  Find-Set($u$).$ancestor$ = $u$
  for each child $v$ of $u$ in $T$
   $\quad$ LCA($v$)
   $\quad$ Union($u$,$v$)
   $\quad$ Find-Set($u$).$ancestor$ $= u$
   $u.color = $ BLACK
   for each node $v$ such that $\{u, v\} \in P$
   $\quad$ if $v.color == $ BLACK
   $\quad \quad$ print "The least common ancestor of" u "and" v "is" Find-Set($v$).$ancestor$

Note that we are given a rooted tree $T$ and an arbitrary set $P = \{\{u,v\}\}$ of unordered pairs of nodes in $T$, and we want to determine the least common ancestor of each pair in $P$.  To solve the off-line least-common ancestors problem, the above procedure performs a tree walk of $T$ with the initial call
LCA($T.root$).  Assume that each node is colored WHITE prior to the walk.

Given this, prove that LCA (correctly) prints the least common ancestor of $u$ and $v$ for each pair $\{u,v\} \in P$.

I'm thinking I'd need to prove two cases 1. w.l.o.g. $v \in T_u$ and 2. $v \notin T_u$ and $u \notin T_v$, where $T_u$ and $T_v$ are subtrees of $T$ rooted at $u$ and $v$, respectively.


texts: Image pattern detection - Finding similarities in same image

texts: The problem: Only pattern-like images are supposed to be uploaded and be used as backgrounds to a site, photos should not. How would you detect if an image looks enough like itself to be regarded as a pattern?


texts: What is the complexity of this recursive merge of two ordered Python lists?

texts:
This is not an assignment, but it is related to my Data Structures class.

I just wrote this Python code to merge two ordered python lists. I do know that I could do something like this: list1 + list2. I still want to know the answer for my question - it seemed important to my professor that we learn how to write good recursive function. The time complexity of a well written recursive merge function, according to him, is O(n).

The function receives two ordered lists and merges them into another ordered list. I would say that it runs in O(n), but, at the same time, I feel that my function is not well written; I guess I can't evaluate this more precisely because I don't quite know everything that happens behind the scenes to the Python's built-in functions I use.

def mergeR(l1, l2):
    lfinal = []

    if not l1:
        return l2
    if not l2:
        return l1

    if l1[0] < l2[0]:
        lfinal.append(l1.pop(0))
    elif l1[0] == l2[0]:
        l2.pop(0)
    else:
        lfinal.append(l2.pop(0))

    lfinal.extend(mergeR(l1, l2))

    return lfinal


texts: Can timestamp be used in synchronization of processes having Race Condition?

texts:
I am wondering whether timestamp can be used to solve process synchronization problem, when race condition occurs? Below is an algorithm for entry as well as exit sections for every process who wants to enter in critical section. Entry section uses FCFS (First Come First Serve) technique to give access to critical section.

    interested[N] is shared array of N integers where N is number of processes.

    // This section executed when process enters critical section.
    entry_section (int processNumber) {
        interested [processNumber] = getCurrentTimeStamp ();  // Gets the current timestamp.
        index = findOldestProcessNumber (interested);         // Find the process number with least timestamp.
        while (index != processNumber);
    }

    // This section executed when process leaves critical section.
    exit_section (int processNumber) {
        interested [processNumber] = NULL;
    }

According to me, this algorithm satisfies all conditions for synchronization, i.e., Mutual Exclusion, Progress, Bounded waiting and Portability. So, Am I correct?

Thanks for giving your time.


texts: How to determine the set of real numbers corresponding to a given floating point number?

texts:
Let's say we consider IEEE 754 double precision floating-point numbers, and we use RNTE - Round To Nearest, Ties to Even - rounding.
I know that the RNTE rounding works this way:
given two consecutive floating-point numbers, a and b, and a real number x,

if a <= x < (a+b)/2, x gets translated to a
if (a+b)/2 < x <= b, x gets translated to b
if x = (a+b)/2, x gets translated to the number with an even significand between a and b

For example, I want to know which are the real numbers that are "mapped" to 1, where 1 is a floating-point number. How should I proceed? I thought that I must consider both the cases where 1 is a and where 1 is b in the above definition, and so consider both the previous and the next floating-point number. Is it correct? Is there a simpler way?


texts: Minimum number of vertices to remove to bound the largest connected component of a graph

texts:
I have this problem, maybe anybody could help.

Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G \setminus \{v_1, \dots,v_l\}$ have at most $k$ vertices.

I wonder it this problem can be solved quickly (in polynomial time)?

(Related: finding the vertices when $k$ is small)


texts: Amortized Analysis for Addition of $n$ numbers

texts:
How can we add n positive integers with binary expansion $l_1$, $l_2$,...$l_n$ bits so that the total complexity is $O (\sum l_i)$ for $i = {1,...,n}$ ? More importantly, how can show this complexity using amortized analysis (the potential method)?

I know the elementary school addition of 2 numbers of length $s$ and $r$ is $O(r+s)$ and hence, the addition of n integers is $O(\sum l_i)$. However, what potential function would you use to prove that bound? I don't seem to have any intuition on that... Maybe use a function similar to the standard binary counter example (number of 1's in the binary representation of the number)..?


texts: What does tilde mean, in big-O notation?

texts:
I'm reading a paper, and it says in its time complexity description that time complexity is $\tilde{O}(2^{2n})$.

I have searched the internet and wikipedia, but I can't find what this tilde signifies in big-O/Landau notation. In the paper itself I have also found no clue about this.  What does $\tilde{O}(\cdot)$ mean?


texts:
I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this:

User (U) | Group (G) | Price (P)
================================
U1       | G1        | P11
U2       | G1        | P12
--------------------------------
U1       | G2        | P21
U2       | G2        | P22
--------------------------------
U3       | G3        | P33
U4       | G3        | P34
--------------------------------
U5       | G4        | P45

A user (U) can apply to be an admin of more than one Groups (G). There is a salary (P) that must be given to U if U is selected as the admin of G (U can demand any arbitrary number as salary for a group G).

The goal is to satisfy these conditions

Every group should have exactly 1 admin.
A User should not be the admin of more than 1 group.
Find admins for as many groups as possible.
The sum of salaries should be minimum.

Examples/Notes

If there are only two applications and are by the same user U (say for groups G1 and G2, expected salaries P1 and P2), only either of G1 and G2 will get an admin. If P1 > P2, U should be adjudged the admin of G1 (and not G2).

I'm not very sure which category of Assignment problem does this fall into. My approach was greedy and doesn't look optimal.

Group-wise sort (ascending) the expected salary.
Arbitrarily allocate a user to a group where there is only 1 admin-ship request. Remove this user from other group-admin requests.
Among the first request across groups, find the maximum and allocate the user to the group. Remove this user from other group admin-ship requests.
Repeat

Question: What is an optimal solution to this problem?


texts: Why reverse pipeline stages in cycle-level simulator?

texts:
In pipeline simulator exercise, it says that:

  Traversing the stages in backwards order simplifies the instruction flow through the pipeline.

Also, in gpgpu-sim source code, the stages are reversed (line 2442):

void shader_core_ctx::cycle()
{
    m_stats->shader_cycles[m_sid]++;
    writeback();
    execute();
    read_operands();
    issue();
    decode();
    fetch();
}

Why? What problem it solves? Can anyone elaborate a bit or give a pointer to books/papers on this particular "trick"?

Many thanks!


texts: Why isn't the class of Turing-Recognizable languages closed under Complement?

texts:
I'm studying Turing Machines and I've already showed how Turing-Decidable is closed for the operations of Union, Intersection, Concatenation, Complement and Kleene Star. Next I did some demonstrations to show how T-Recognizable languages are closed for Union, Intersection, Concatenation and Kleene Star.

Now I'm trying to answer a question to show why the classe of T-Recognizable languages are not closed for the operation of Complementation, but I cannot understand it. Could someone please explain this?


texts: Compiler Question : Does the parser detect Errors in these examples or the Semantic routine?

texts:
For example, which part will detect these errors, Parser or Semantic Routine?
1) int Array[10.5]  ( wrong size )
2) int x="some string"
3) A[10.5] + 3  (not in declaration, but in the middle of the code)
The book that I'm reading says the first one will be detected by parser but the third one will be detected by Semantic routine! I don't get it? why not both of them by parser? if the parser can detect first one, then it should be able to detect the third one
ALSO, i thought that lexical analyzers usually turn every number into a same token? for example:
a = 3.5 + 5 --> id = num + num
so how can parser or semantic analyzer differentiate between a real number and a integer number?
Lets assume our compiler is a modern day compiler for C for example.


texts:
Well this is general question. And if anyone want to make it implementation specific then I will prefer Unix related stuff. But first need to know following problems in generality:

I read single process can have multiple threads. Multiple threads of same process does share things among them. I want to know what they share and what not.
Considering process is comprised of address space, stack, heap, global variables, code, data, OS resources, what among them is shared by threads? I have following guessings:

Global variables - I have read thread shares global variable. Also while programming in Java and C#, I have made threads to share class level variables. So I am believing that the threads share global variables (though not sure whether the concepts in high level programming languages translates as is to low operating system level facts).
Heap - Since global variable is stored in the heap, heap is shared among threads.
Stack - Since each thread can have its own execution sequence/code, it must have its own stack on which it might push/pop its program counter contents (when say function calls and returns happen). So threads of same process do not share stack.

Now I am unsure about the sharing of following things

Address space - Not sure what exactly counts under address space. But I guess address space is generally used in the context of processes, not threads. And since all threads of same process reside in the same address space as the parent process, it is said that threads share address space. (But then they maintain different stack inside same address space?)
OS resources - I guess this can be very implementation specific. For example, parent process can selective give handle of same file to some of its threads and not to all. Or I am mistaking and OS resources means something other than files?
Code - Threads can have different code, so sharing code is not always the case.
Data - Unsure about what to consider under data. But sure that global variables are shared among threads. And sure that local variables are not similarly shared.

Overall I am considerably confused due to vague terms, super-generalizations done in the Operating Systems books and extra-implementation specific details provided online. So I am trying to find some answer that can satisfy me.


texts: Fastest square root method with exact integer result?

texts:
I am dealing with the problem of computing $ s = \lfloor sqrt(x)\rfloor$ with $x \in [0,30000^2]$. The common sqrtf(x) on C language is too slow for this case, however it always gives me the correct result. I've tried with the Newton's method but I get very small errors when the square root of a number is exact. This leads to an uncertain pattern of $s-1$ results along the interval. If I increase the number of iterations the method becomes too slow but more exact.

Does anyone know of faster methods or directions on the latest research done in the area?

note to clarify: input is idealy a real number (i.e floating point) but i also accept solutions with integer as input.


texts: Find the k-th member of the recursive sequence

texts:
I have a recursive sequence: $a_n = 5a_{n - 1} + 2a_{n-2} + 3$, for $n > 1$. And I could return $k-th$ member in $O(\log{k})$ of sequence i.e. $a_k$.
I know how to get the formula of the $k-th$ member using the generating function method, but I need to find a more algorithmic solution.
For example, like this one.


texts:
How can I prepare for an introductory CS college course?

I am currently in Grade 12 and next year I will be studying Computer Science at a university in South Africa (syllabus is here). However CS has a very high dropout rate here in South Africa, more than any other course, and I'm nervous because of that. My experience with programming is limited to Java in the Net beans environment.  I understand the basics of programming (loops, arrays, methods and classes, reading and understanding other languages, etc).

My question is how can I be more prepared? I'm willing to learn new languages or take online courses or anything that can help me next year.


texts: What's wrong with this LL grammar? (very short)

texts:
S --> Ta | b | Sc
T --> Tc | λ

This isn't an LL grammar but I need it to be so I can do a parse table. The problem is that no matter how much I try I never manage to do make it an LL grammar. Can someone please help by making it a LL grammar? It isn't that big and I'm very confused.


texts: Is Dual Graph of a Triangulation of a Polygon Tree?

texts:
I have read that; if a polygon contains a hole in it, then the dual graph of a triangulation of the polygon not have to be a tree. But could not get it exactly. How is it possible, what is the relation with the hole in it?
If anyone could explain it with a polygon contains hole. I would be very happy and thanks in advance.


texts: Optimize binary multivariate polynomial multiplication

texts:
You have a few variables that can only assume the values 0 or 1 and you use those to form two polynomials. Is there a way to multiply the two polynomials that is faster than O(n²) where n is the number of terms in the polynomial?
What I could come up with:

As the variables are binary, they all follow the equation X²=X

You can represent any polynomial of this kind with an array of $2^n$ values, where n is the number of variables, where each index represents the variables multiplied and the value at the index position represents the quantity multiplied.

Example: for a polynomial with 3 variables, the array indexes will be as follows:
0 - _
1 - a
2 - b
3 - a * b
4 - c
5 - a * c
6 - b * c
7 - a * b * c
And the polynomial 1+3a-2b+bc could be represented as [1, 3, -2, 0, 0, 0, 1, 0]

to add two polynomials in this representation you just have to add the arrays

the value of the multiplication of two terms can be calculated multiplying their values and the index can be found by applying OR in their indexes. Example: array A and array B represents two distinct binary polynomials and K is the result of the multiplication.
A[i] * B[j] -> K[i | j] = A[i] * B[j]

So, is there a faster way than looping and distributing each term?


texts: Why can't we detect infinite loops in the busy beaver problem?

texts: I was reading about the busy beaver problem the other day and I'm confused as to why we can't keep an array of Turing machine states that the machine has been through and simply iterate through it at each new machine state to see if it exactly matches a state we've previously seen. That ought to tell us there's an infinite loop, no? Then following this, shouldn't we be able to solve the problem for any given Turing machine, instruction set and tape?


texts: Is the number of sub-boolean algebras of a set with size of n equal to Bell(n)?

texts:
In boolean algebra (P(S),+,.,’) we must have S as 1 and {} as 0 in every possible sub-boolean algebra to hold id elements.
We must have S-x for every subset x⊆S to hold complements.
It seems like counting every possible partitions in S which is Bell(|S|) if i was not wrong.
For example the number of possible sub-boolean algebra of ⟨p({a,b,c,d}),∪,∩⟩ is Bell(4)=15 , is it right ?
If it is how we can define a bijection between every n class partitions to boolean algebra with size n ?


texts: Rearrange items in order reduce fragmentation and reduce wasted space

texts:
I have a segment with some offsets at irregular intervals

There are items of various length inside. Items cannot be placed randomly. Instead, their left side must match some offset.

Items are free to go past offests.

As you can see in this image, item number 3 is long enough that it goes through an offset, shown with a dotted line.

I also have some special type of offset that I'll call "barrier" that items cannot go past and cannot be placed on:

One last constraint is that items cannot overlap each other:

Items can be moved one at a time. So I can pick up an item and place it somewhere else as long as no constraint is violated.

I'm trying to come up with an algorithm/solver/optimizer which would find some good enough sequence of steps to reduce fragmentation and compact up these items. It follows that this procedure will reduce empty space between items and offsets:

Can you give some suggstion on how you would tackle a problem like this or point me in the right direction, give some ideas, name algorithms to take inspiration from, etc..?


texts: Proving that the language of satifiable CNF formulae with primes is NP-complete

texts:
Given the following language:

  $$L=\left\{\langle\phi, n\rangle \ \middle|\  \begin{array}{l}\phi\text{ is a satisfiable Boolean formula}\\ \text{written as POS (in CNF form)}\\ \text{and $n$ is a prime number}\end{array}\right\},$$

  Prove that L is an NPC language.

This is the first time I'm trying to solve this kind of questions, and I am stuck.

This is what I have so far:

To prove that a language is NPC, I need to prove two things:

1) $L \in \mathrm{NP}$

2) For any $L'\in \mathrm{NP}$, there exists a poly-time reduction from $L'$ to $L$.

To prove (1), can I say that $\phi$ is NP (because we know that SAT is NP), and that $n$ is P (because Prime is P)?

If so, I think that I need to say that $\mathrm{P} \subseteq \mathrm{NP}$ to complete the proof of (1).

What's next?


texts: Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?

texts:
Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O orders can be considered sets.

For example, $n^3 + 3n + 1$ can be considered an element of set $O(n^3)$. Moreover, $O(1)$ is a subset of $O(n)$ is a subset of $O(n^2)$, etc.

This got me thinking about big-Theta which is also obviously a set. What I found confusing is how each big-Theta order relates to each other. i.e. I believe that $\Theta(n^3)$ is not a subset of $\Theta(n^4)$. I played around with Desmos (graph visualiser) for a while and I failed to find how each big-Theta order relates to other orders. A simple example Big-Theta example graphs shows that although $f(n) = 2n$ is in $\Theta(n)$ and $g(n) = 2n^2$ is in $\Theta(n^2)$, the graphs in $\Theta(n)$ are obviously not in $\Theta(n^2)$. I kind of understand this visually, if I think about how different graphs and bounds might look like but I am having a hard time getting a solid explanation of why it is the way it is.

So, my questions are:

Is what I wrote about big-O correct?
How do big-Theta sets relate to each other, if they relate at all?
Why do they relate to each other the way they do? The explanation is probably derivable from the formal definition of big-Theta (might be wrong here) and if someone could relate the explanation back to that definition it would be great.
Is this also the reason why big-O is better for analysing complexity? Because it is easier to compare it to other runtimes?


texts: The busy beaver max shifts function, $S(n)$, has known values for $n\leq4$. Is there some basic, structural reason why it's inconceivable that we will ever find $S(n)$ for $n>4$?  What is so different about $n=4$  than $n=5$? Or $n=6$? Somewhere along the way there must be some fundamental difference, otherwise $S(n)$ would be, in principle, computable for all $n$, so what exactly is this difference?


texts: How use generalized suffix tree to match prefix string?

texts:
I know that generalized suffix tree can match substring for a given pattern.
But I have need a data structure which is able to

match prefix of many strings.
match sub string of of many strings.

For example:
The strings I have:

abc, abcd, bcxabc,

If the pattern is abc, I should match all three strings.

If the pattern is ^abc, I should only match abc, abcd. The ^ represent the start of a string.

I know I can build another TRIE. But it will cost almost the same space.

If there any way to achieve this in generalized suffix tree?


texts: Question on Virtual memory and Physical memory

texts:
This is the question where I'm stuck:
With a 32-bit virtual address, 4 KB pages(12 offset bits), and 4 bytes per page table
entry, we can compute the total page table size:

Number of page table entries = 2^(32-12) = 2^20
Size of page table is 2^20 * 2 = 4MB

I understand this, but what I don't get is that each page table entry is of 4 bytes which is 32 bits. That would make the Physical address= 32+ 12 (offset bits)= 44 bits. Wouldn't it?

I've read and understood the point that Virtual Memory size should be bigger than Physical address because that's when the Virtual memory can hold more memory value (Main memory+Disk, though virtually) than the physical address. Am I right?

Also, I've found a block diagram showing all virtual
addresses pointing to physical through a page table, and from  there they are mapped to main memory and disk address; mapped to disk if valid bit is 0 or else mapped to main memory.

Let me know if I'm wrong anywhere.


texts: How should we define the behavior of a Turing machine where the head tries to move left from the leftmost tape position?

texts:
If we have a Turing machine in a model with a tape that is infinite only to the right and assume at some point the head tries to move left from the leftmost position.

How should we define the behavior in such a case? Is a machine doing so for some input not a valid Turing machine? And if so, how can we make sure when we define a Turing machine that this situation can't occur for any input?

I've read some sources about Turing machines though couldn't find the answer to this specific case, and I see no reason why this case won't happen for an arbitrary Turing machine and some input.


texts: It is known that the existential theory of the reals is decidable in PSPACE (via John Canny), but as far as I can tell no one has demonstrated that it is in NP. This confuses me because it seems like a short certificate for a given formula would be an example of values for the variables included in the formula that demonstrates a valid assignment. Why is this argument invalid?


texts: Optimal algorithm to distinguish given black box access

texts:
This is a variant of this question. Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. Assume that $D$ and $U$ are far apart in total variation distance, ie,
\begin{equation}
d_{\text{TV}}(D, U) \geq \frac{2}{3}.
\end{equation}
We are not given an explicit description of $D$: we are only given black-box access, ie, we are only given a sampling device that can sample from $D$. Consider a sample $z \in \{0, 1\}^{n}$, taken from either $D$ or $U$. We want to know which one is the case and to do that, we consider polynomial-time algorithms that use the sampling device. I am looking for a single optimal deterministic algorithm that works optimally for all $D$.
Let $A$ be this optimal algorithm. For each $D$, our algorithm $A$ is optimal in the sense that
$$
\Pr_{z \sim D} [A(z) = 1] \geq \frac{3}{4}, \\
\Pr_{z \sim U} [A(z) = 0] \geq \frac{3}{4},
$$
Output $1$ is interpreted as "the sample comes from $D$, and output $0$ is interpreted as "the sample comes from $U$."
Let $A$ use the black-box sampling device a polynomial number of times (at most) and get samples $z_{1}, z_{2}, \ldots, z_{k}$ from $D$, for some polynomial $k$. My intuition is that, if this best algorithm decides that $z$ indeed came from $D$, then it must be true that $z_{i} = z$ for at least one $i \in [k]$. In other words, since we know nothing about $D$ or its support, we have to "see" $z$ at least once in the samples we collect from $D$ to ascertain that $z$ indeed came from $D$. How do I mathematically formalize this statement?
Also, does this same intuition hold if we are given a polynomial number of samples as input (taken from either $D$ or $U$) instead of just one and are also given access to a black-box sampler for $D$?


texts: Optimal solution algorithm for K-center problems

texts: I'm wondering if there is an algorithm that calculates the optimal solution of a typical k-center problem (more than one dimension). I've tried, but without success, to find this algorithm. Does such an algorithm exist?


texts: Find the minimum N such that the sum of beauty of all numbers from 1 to N is at least X

texts:
The beauty of a number is defined as follows :-

public int beauty(long number)
{
     int count = 0;

     while( number > 0 )
     {
         count += (number & 1);
         number = number / 2;
     }

     return count;
}

Given X, we need to find the minimum N such that the sum of beauty of all numbers from 1 to N (inclusive) is at least X. X may be as large as upto 10^18 and there are 2*(10^4) test cases.

As far as I have understood, the beauty of the number is the count of set bits in the integer. So we need to find the sum of count of set-bits from 1 to N. But numbers such as X = 10^18 give the values 10^15 for N. It is not feasible to run loop from 1 to 10^15. Is there a better algorithm ?


texts: Modifying Floyd–Warshall Algorithm for Vertex Weights

texts:
I was trying to modify the Floyd–Warshall's algorithm to take into account the weights over the vertices, in addition to the weight of the edges, while computing the shortest path. The length of a path from vertex A to an adjacent vertex B, Path(A,B) , is defined as:

     Vertex_Weight(A) + Edge_Weight(AB)

For a vertex A:

      Path(A,A) = 0

I was wondering if the Floyd–Warshall can be modified to handle this, and in particular if the following idea will work:

  The weight on a vertex V can be added to the weights of all the
  outgoing edges from V. Thus new edge weight Edge_Weight' is:

      Edge_Weight'(AB) =  Vertex_Weight(A) + Edge_Weight(AB)

  One can transform the original graph with the vertex weights to a
  graph without vertex weights, where the edge weights are modified as
  above. The normal Floyd–Warshall can be applied now.

If anyone could envisage a scenario where this might not work or if anyone knew of a better way, I would be thankful.


texts: Is the way an OS schedule threads related to parallel computing?

texts:
From Wikipedia:

  Operating systems schedule threads in one of two ways:

  Preemptive multitasking is generally considered the superior approach, as it allows the operating system to determine when a
  context switch should occur. The disadvantage of preemptive
  multithreading is that the system may make a context switch at an
  inappropriate time, causing lock convoy, priority inversion or other
  negative effects, which may be avoided by cooperative multithreading.

  Cooperative multithreading, on the other hand, relies on the threads themselves to relinquish control once they are at a stopping
  point. This can create problems if a thread is waiting for a resource
  to become available.

I wonder if in  parallel computing (writing and running parallelized programs in OpenMP, OpenMPI, pThread), which of Cooperative multithreading and Preemptive multitasking is/are used, or does the way OS scheduling threads have nothing to do with the multi-process or multi-thread within a parallelized program?


texts:
As I remember:

A decision problem is a problem that has the answer yes or no.
An algorithm (in the context of automata theory) answers yes or no; it halts on all inputs, accepted or not.
A TM represents an algorithm. The TM accepts an input string and executes with that input. If the machine ends up in an accept state, the answer is yes, otherwise no.

How does a yes/no problem relate to general algorithms we are doing that have more than yes/no problems? Or is that every problem can be thought as a yes/no problem, i.e. is this a function f produce 5 (or whatever input) with input 2 (or whatever output)?


texts: Find total number of assignment in the worst case?

texts:
I have this algorithm

Algorithm (A[1..n])
    for i <- 1 to n do
        if (A[i] < 0) then
            A[i] <- 1 * A[i]
        End if
    End for

I have to find the total number of assignment in the worst case, but I'm a little bit confused, do I say I have 2 or 1, one for the assign A[i] in the statement and second for the i in the for loop (i <- 1).


texts:
Trying to construct the full tree for a 9 game token of Nim and am slightly confused. I don't understand how two players, min and max, will make their pick. For example, max picks first and can only pick [9]. Min then picks from [8-1], [7-2], [6-3],  and [5-4]. How does min calculate it's utility value here?

max                              [9]
min                 [8-1]   [7-2]   [6-3]   [5-4]
max        [7-1-1] [6-2-1] [5-3-1] [5-2-2] [4-3-2] [3-3-2]
min    [6-1-1-1] [5-2-1-1] [4-3-1-1] [5-1-2-1] [4-2-2-1] [3-3-2-1] [4-1-2-2] [3-2-2-2] [3-1-3-2][2-2-3-2] [2-1-3-2]


texts: clique, independent set, and minimum vertex cover

texts:
I was given a graph problem with 3 different questions and 1 set of answers. The problem is described below. The problem that I'm having is that it seems to me that the answer to all the questions is the same. I keep trying to find a caveat but I don't see one. What am I missing?

Here is the problem

Undirected graph $G$. $n$ - number of vertices. $m$ - number of edges. $d$ - maximum degree of a graph.

The maximum clique size of $G$ is no larger than
The minimum vertex cover size of $G$ is no larger than
The maximum independent set size of $\overline{G}$, the complement of $G$, is no larger than

Set of answers

(a) $d+1$
(b) $n$
(c) $n-1$
(d) $n/2$
(e) $d$
(f) $n-d$

It looks to me that the answer to every problem is (b) $n$, because

Clique cannot have more vertices than there are in a graph
Vertex cover cannot be larger than the number of vertices in a graph
Maximum independent set cannot be larger than the number of vertices in a graph.

I feel like I'm missing something, because the answers seem too obvious.

Any help is appreciated


texts: What is a polynomial time algorithm for finding a vertex cover of size $k$ in a tree? Would depth first or breadth first search be efficient or is there some other algorithm that finds the vertex cover that takes $n^k$ time rather $2^n$ time?


texts:
I'm having trouble with this problem as I haven't discovered a good way to determine the power of a Turing machine.  I was under the impression that if a Turing machine can perform the same actions and satifies unrestricted access to unlimited memory they're all pretty much equivalent.  Such as multiple tapes and nondeterministic Turing machines.

I am to determine if a and b are equal, more powerful or less powerful then a single-tape Turing machine.  Where do I start?

a) A Turing Machine that can only make moves to the right and never left.

b) A Turing Machine that can move right one space or move left two spaces.


texts: How Do You Design an Algorithm for This Graph

texts:
Introduction
I'm not really understanding my algorithms class. One of our HW assignments is to design an efficient algorithm for this graph

Questions

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

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

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


texts:
I have some difficulty trying to tell which equation to use when I'm given an explanation on how an algorithm operates. Especially divide and conquer.

Normally I see these kind of equations:

C(n) = aC(n/a) + b where a and b are constants

Other times I don't see the a in front of C(n/a) as an answer. That really confuses me.

Can you tell me when I will need to use which?

Thanks!


texts: Wrong DFA from NFA. String Does not contains 110

texts:
I am doing problem 1.g.
My Approach is to first create a NFA that accepts this string i.e. all strings having 110. Then converting it into DFA and then complementing it. I have the answer what should I get however my NFA to DFA conversion doesn't work. I don't know why. Can anyone guide me. Thanks. Here is my NFA. Note this is not full answer as there is complement left to be done. But I am stuck in between.

Then I converted it into FSA

This is What I got

I know there is a mistake that there should be self loop of 1 on the AC state but from my above NFA, I am unable to obtain it. Is my NFA wrong? Or I have done some mistake in conversion.


texts: How to create mathematical proof of TSP and SLAP equivalence?

texts:
In my thesis, I'm dealing with SLAP (storage location assignment problem) -- which is finding optimal distribution of products to location slots in a generic warehouse. My aim was to implement multiple evolution algorithms (GA, DE, ABC & PSO) to solve this problematic and do a comparison. Since the mentioned problematic (SLAP) is also combinatoric problem with similar constraints and characteristics as TSP, I did research on TSP problematic solved using these algorithms, and applied it on my problem, e.g. based on those papers: GA/PSO, DE, ABC. These approaches were mapped on my problem and works really well. Now, my supervisor told me to create a mathematical proof of TSP - SLAP problematics equivalence or at least some mathematical mapping, he is not doing research in this field so he cannot help me.
To summarize my problem and why I think it is similar to (nearly same as) TSP:

In TSP, we need to use all cities in the chromosome (solution in general). In my problem, we need to use all articles in the solution.
In TSP, we cannot have duplicates (we cannot go through one city more then once). In my problem, we also cannot have duplicates, as it would imply that more products are stored within one location slot.

I did some research and found out both SLAP and TSP are NP-Complete problems. It would be possible to create mathematical proof that my problem is NP-Complete. It is both calculated in polynomical time and some well known NP-Complete problem, such as halting problem can be reduced to this problem. Although I don't think this would help me much.
(Pseudo-)formal description:
Let's suppose we have $N$ products, and $M$ location slots, where $M$ >= $N$ (as a input). We need to distribute all products to the locations slots, in a way which decreases customer order processing time the most (i.e. all orders has to be processed ASAP). The objective function is duration of order processing and is evaluated as running a simulation of a warehouse (with given distribution of products to slots). So the output is the best possible allocation of the products to slots, which can be expresses simply as a vector of integers, where position in vector specifies article, and the number on the position specifies location slot (into which the product is placed).
Is there any way I can create a proof that these two problems are equivalent or atleast some mathematical mapping from my problem to TSP? Thank you.
If required, I can provide further data, such as chromosomes encoding in GA, ... (but it didn't seem relevant to the proof from my point of view).


texts: Proving NP-completeness for a not so cheesy problem

texts:
Let's say we have a matrix M[1..B, 1..B] (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. The mouse can move from a given positon (i, j) either in the direction (i+1, j) or (i, j+1). When the mouse visits a given position (i,j), it collects all the given cheese immediately, so if it decides to return to an already visited position, it will already be empty. Additionally, the mouse can ONLY reverse/back ONCE when traversing the matrix, because we can assume that this mouse doesn't particularly like to change its mind.
So given all these prerequisites, the question is whether or not it is possible for the mouse to collect exactly A pieces of cheese, starting from the position (1,1) and ending up in the position (B,B)?
There should be a proof that this problem is NP-complete by showing it is in NP and by reducing the NP-complete problem Subset Sum.
For showing it is in NP I was thinking about maybe looping through the whole matrix and counting the total number of cheese and then maybe have some sort of boolean condition to check whether or not the amount of cheese the mouse has collected equals to the total amount of cheese located in the matrix and that this will take polynomial time to do. However, I am not sure this is the right way to do and I am even more unsure of how to reduce Subset Sum to this problem. Thus, I am grateful for your help and advice!


texts:
Couldn't find a definitive answer anywhere so asking here. I have a Turing machine and the start state can go straight to the end state without passing through any of the other five states via

Blank -> Blank, R

And one of the questions is

In the best-case, how many steps are required to accept a string?

Is the answer 1 due to this step, or is it just there as a trick question on this worksheet? Thanks in advance.


texts: My teacher describes true quantified boolean formula (TQBF) as an interactive game between two players $\exists$ and $\forall$, and asks us to show a winning strategy for the existential player $\exists$. Can someone describe what this game is? I feel like this is background knowledge I am missing.


texts: Find height of deepest FULL level in binary tree

texts:
Suppose I have a binary tree that is guaranteed to have at least one level that holds the maximum amount of nodes possible. I want to find the height of the deepest level that is full/holds the maximum amount of nodes possible. I have a function highestFull() that calls it's recursive version highestFull(Node* t) which is initially given the root. I cannot use any of the standard library functions.

How do I approach this problem? I am looking for the most intuitive solution, not the most clever. I found an answer here, but I cannot understand why it works. I really want to understand the thought process behind the solution.


texts: Prove or disprove if $L_{1}$ is Turing-recognizable and $L_{2}$ is co-Turing-recognizable then $L_{1}\cap L_{2}$ is decidable

texts:
I thought about these languages:
$$L_{1} = A_{TM} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts } w \big\}$$
$$L_{2} = \overline{HALT_{TM}} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ doesn't halt on input } w \big\}$$

Their intersection:
$$L_{1}\cap L_{2}  = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts and doesn't halt on input } w \big\}$$

If I assume that the intersection is decidable by TM $T$ so I can use $T$ to decide $A_{TM}$ and that's a contradiction.

Is it true?


texts: I have seen in most of the places written that LL grammars form a subset of DCFL and DCFG. Is there a proof for that?


texts: Is $\Pi’\propto_{poly}\Pi$ for any two NP-complete problems $\Pi,\Pi'$?

texts:
I am facing the following question:

Let $\Pi$ and $\Pi$’ be two NP-complete problems, prove or refute $\Pi’\propto_{poly}\Pi$.

I do not understand the meaning of this question and how to answer it.
The definition of $\Pi’\propto_{poly}\Pi$" as follows:

Let $\Pi$ and $\Pi'$ be two decision problems. We say that $\Pi$ reduces to $\Pi'$ in polynomial time, symbolized as $\Pi’\propto_{poly}\Pi$, if there exists a deterministic algorithm $A$ that behaves as follows. When $A$ is presented with an instance $I$ of problem $\Pi$, it transforms it into an instance $I’$ of problem $\Pi'$ such that the answer to $I$ is yes iff the answer to $I’$ is yes. Moreover, this transformation must be achieved in polynomial time.


texts: Decidability/recognizability of languages with strings lacking alphabet characters

texts:
Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ odd-parity absent iff $|\{j : \mathcal{I}_j(s) = 0\}|$ is odd. That is, $s$ is odd-parity absent iff an odd number of characters from the alphabet are missing from $s$. Call a language $L \subseteq \Sigma^*$ odd-parity absent iff every string in $L$ is odd-parity absent.

I want to show whether or not the following proposition is true: if $L$ is odd-parity absent, then $L$ must be Turing decidable/recognizable.

At first, I was considering employing Rice's Theorem to show that the odd-parity absent language of Turing machine encodings is a non-trivial property and hence undecidable, but it seems conceivable that two equivalent Turing machine descriptions may be such that one is odd-parity absent and the other is not, and so this wouldn't be a valid property. Further, it seems we can always describe two equivalent Turing machines using two completely disjoint alphabets.

Also, I am not sure whether the proposition holds in the case of Turing recognizability.


texts: Why is determining the size of a maximum independent set or a clique in P?

texts:
I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard.

With respect to finding clique size, you can sort the node degrees, decrement $i$ from $|V|$ to $0$, and each time check if you have $i$ elements of node degree $i$, pick the power set of those $\geq i$ elements and verify the clique. However, picking the power set is exponential, and this algorithm would give you the solution itself. I have a hard time figuring out how you can construct an algorithm that decides the presence of a clique (or independent set) of a certain size in polytime, but doesn't give you the solution.


texts: Find a Cook Reduction from $R_{Clique}$ to its determinist problem

texts:
The question is to find Find a Cook Reduction from $R_{k-Clique}$ to its determinist problem.
Basically:
k-Clique: a group of $k$ nodes in the graph such there is an edge between every two nodes.
Suppose you are allowed to use an algorithm (B) that in $O(1)$, given as input a graph $G$ and a number $k$, returns whether the graph includes a $k-Clique$ or not.
Use B to define an algorithm (A), that in polynomial time, given as input a graph $G$ and a number $k$, returns a $k-Clique$ if it exists, and a symbol if it doesn't.
My idea:
My idea was to define something as follow:
1. While the size of the graph is greater than k
    2. Remove from the graph the node with the lowest deg
        1. check the new G with B, if yes, return it
        2. Else, continue

Something like that. I wasn't able to disprove it at least. But is it correct? How would I prove it?


texts: Maintaining search indices with binary trees

texts:
There are some documents to be indexed, that means I need to read the docs and extract the words and index them by storing at which document they appear and at which position.

For each word initially I am creating a separate file. Consider 2 documents:

document 1: “The Problem of Programming Communication with”
document 2: “Programming of Arithmetic Operations”

Here, there are 10 words, 8 unique. So I create 8 files (the, problem, of, programming, communications, with, arithmetic, operations).

In each file, I will store at which document they appear and at what position. The actual structure I am implementing has lot more information but this basic structure will serve the purpose.

file name        file content
the              1 1
problem          1 2
of               1 3 2 2
programming      1 4 2 1
communications   1 5
with             1 6
arithmetic       2 3
operations       2 4

Meaning. the word is located at document 1, position 3 and at document 2, position 2.

After the initial index is done I will concatenate all the files into a single index file and in another file I store the offset where a particular word will be found.

index file: 1 1 1 2 1 3 2 2 1 4 2 1 1 5 1 6 2 3 2 4
offset file: the 1 problem 3 of 5 programming 9 communications 13  with 15 arithmetic 17 operations 19

So if I need the index information for communications, I will go to position 13 of the file and read up to position 15 excluded, in other words the offset of the next word.

This is all fine for static indexing. But if I change a single index the whole file will need to be rewritten. Can I use a binary tree as the index file's structure, so that I can dynamically change the file content and update the offset somehow ?


texts: Knapsack problem with multiple constraints

texts:
I am unsure if I have even identified the problem correctly, but reading up on knapsack problem seems the closest to what I am trying to solve:

  A cook has $k$ ingredients of $p$ quantities. Given a
  list of $n$ unique recipes, each consisting varying ingredients of varying
  quantities.
  Now, the cook would like to use all ingredients on ONE recipe with minimal leftovers.

What is his solution? And can it be determined in $O(\log n)$ time?

Sample input

500 pounds of flour
300 mg sugar
5 mg of vanilla pods
20 eggs

Database of possible recipes:

Thai Fried Noodles (doesn't contain vanilla or flour, but contains 1 tablespoon of sugar)

Tiramisu (doesn't contain flour and vanilla but contains 3 tablespoons of sugar and 8 eggs)

Anna's Special Tiramiu (doesn't contain flour and vanilla but contains 1 tablespoons of sugar and 8 eggs)

Truffle Tagliatelle (doesn't contain any input ingredients)

EDIT Cost/benefit decision:

Given the sample input, Tiramisu recipe is the most preferred because among the 4 recipes in the database, it contains the most number of input ingredient type (2 of 4 types), and the most number of input ingredient quantity.

Expected result where 1) is the top search result of relevance:
1) Tiramisu
2) Anna's Special Tiramisu
3) Thai Fried Noodles
4) Truffle Tagliatelle

EDIT: I believe my question is a variant of the integer knapsack problem


texts: Sorting algorithm that moves element to a 2-dimensional array

texts:
I had an idea for a sorting algorithm wich is very fast, but can (potentially) use a lot of memory. I'm not a Computer Science student/graduate, only a self-taught programmer so I don't know how to evaluate it's viability. Also, I would like to know if it has already been documented and under what name.

Algorithm:

Get an unsorted array
Iterate through it, and find the highest and lowest value stored in it
Determine "range" (highest - lowest)
Make a 2 dimensional array presorted,
in which the first dimension's size is "range" + 1
For each element in array "unsorted"

Add the current element into presorted[current_element_value - lowest]

Make array "sorted", and add each element of presorted's second dimension, ignoring the empty first dimensions.
return the sorted array

An example using said algorithm would be the following:

unsorted[] = {5, 8, 2, 4, 6, 8, 2, 0, 4, 5, 6, 3, 3, 2, 1}

After iterating through it once, we get:
lowest: 0
highest: 8

range = highest - lowest = 8

Make 2 dimensional array presorted,
 consisting of range+1 arrays:

presorted[0] = {}
presorted[1] = {}
presorted[2] = {}
presorted[3] = {}
presorted[4] = {}
presorted[5] = {}
presorted[6] = {}
presorted[7] = {}
presorted[8] = {}

Next we add the elements, first element of unsorted is 5.
 5 - lowest (0) is 5

presorted[0] = {}
presorted[1] = {}
presorted[2] = {}
presorted[3] = {}
presorted[4] = {}
presorted[5] = {5}
presorted[6] = {}
presorted[7] = {}
presorted[8] = {}

After doing this which each element:

presorted[0] = {0}
presorted[1] = {1}
presorted[2] = {2, 2, 2}
presorted[3] = {3, 3}
presorted[4] = {4, 4}
presorted[5] = {5, 5}
presorted[6] = {6, 6}
presorted[7] = {}
presorted[8] = {8, 8}

Now, we simply create an empty array called "sorted",
 to which we add all the elements
 of non-empty arrays in presorted:

sorted = {0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 8, 8}

This is the C++ source code for it

std::vector<int> Sort(std::vector<int> &unsorted)
{
   int min = unsorted[0];
   int max = unsorted[0];

   int range;

   std::vector<int> sorted;

   for (int i = 0; i < unsorted.size(); i++)
   {
      if (unsorted[i] > max)
         max = unsorted[i];
      if (unsorted[i] < min)
         min = unsorted[i];
   }

   range = max - min;
   std::vector<std::vector<int>> presorted(range+1);

   for (int i = 0; i < unsorted.size(); i++)
       presorted[unsorted[i] - min].push_back(unsorted[i]);

   for (int i = 0; i < presorted.size(); i++)
   {
       if (!presorted[i].empty())
       {
           for (int k = 0; k < presorted[i].size(); k++)
               sorted.push_back(presorted[i][k]);
       }
   }

    return sorted;
}

Is this algorithm viable?

I think it could be used in certain scenarios (when range is not too big) and it has the advantage that you can determine if it's appropriate to use it with simply iterating once through the unsorted list.

I'll do some tests and report back.


texts: Does the amount of symbols a turing machine has affect what computations it can perform?

texts: Do additonal symbols on a turing machine actually change what is computationally possible on a machine, or do they just make them easier to work with? For example is there anything a 3 symbol turing machine could compute that a 2 symbol turing machine could not? (Assuming each machine can have any number of states).


texts: Start simplex method from feasible internal point

texts: I have one algorithm that generates a feasible solution to a linear programming problem. However, it is very likely that this is not a corner point. This makes it not suitable for direct use as an initial feasible solution for a bounded Simplex solver. How can I efficiently find a corner point from this solution that I can use?


texts: what are the BUS MASTERS in a processor?

texts:
I have multiple questions actually..

a)What is a System bus? Is there any other buses in the computer?

b)Is it always the case that , the processor access the memory via the system bus?

c) I read that " another master requests the access ".. What are these masters exactly? Is processor the bus master by default?

P.S. I am reading in the context of 8086 microprocessor


texts: Largest reported speedup for a parallel computation?

texts:
A parallel implementation of a computation is usually compared to a sequential version of the same computation.  The ratio of the time taken by the sequential version to the time taken by the parallel version is called the speedup.  So if 8 cores run their smaller parts of the computation in 2 time units, and one core runs the whole computation in 8 time units, then the speedup is 4.

  What is the largest speedup reported for a real computation?

It is possible to reach essentially infinite speedup in a search problem, since one of the parallel pieces of the search space may lead to a fast solution by that parallel instance, while the sequential solution has to work through the entire search space to get to that point.  More generally, I want to exclude any problem where one of the parallel processes can reach a shortcut.  So I am only interested in computations where the amount of work done by the parallel processes is the same as done by the sequential process.  This is common in solving PDEs by grid methods, or in discrete event simulation.
So with $n$ processors, one should never get more than $n$ speedup for these kinds of problems.

I would also like to exclude embarrassingly parallel problems like parallel rendering, since there one really has a vast number of independent tiny problems.  I am interested in problems where it is not possible to partition the computation into strictly disjoint pieces.

For a large speedup, one has to have many processors.  Given the restrictions on scope that I have conveniently labelled as "real computations", this question is then essentially about how efficiently the very large processor arrays that exist have been programmed.

I am aware of reported speedups of ~500 using arrays of GPUs, but surely larger speedups exist.

Edit: To address some of the comments, I dug up some further motivation, which will hopefully be precise enough for the tastes of those more mathematically inclined.  This is quite different in style from the above, so I append it here as a postscript.

For $n$ iid random variables $X_1, X_2,\dots, X_n$ with mean $\mu$,
denote their maximum by $X_{(n)}$ and their sum by $S_n$.
O'Brien has shown that $X_{(n)}/S_n \to 0$ almost surely as $n \to \infty$ iff $\mu < \infty$.

Letting $X_i$ be the time taken by the $i$-th processor to complete its task, and assuming that there is a timeout/recompute mechanism to ensure that $\mu$ is finite, this hints that the inverse of the speedup should be essentially unbounded.  (This is not necessarily the case: the techniques used may not carry over to the inverse, so I have to leave this a bit vague.)

This is a nice theoretical prediction, and the question arises: is this prediction borne out in practice?  Or do implicit dependencies or diverging behaviours of the different processors (i.e. a breakdown in the iid assumption) tend to curtail this supposedly unbounded increase?

The iid case corresponds to the embarrassingly parallel case.  Where the processors have to synchronize, independence breaks down.

My question can therefore also be rephrased as: how badly does non-negligible dependence between parts of a computation as seen in practice affect the large-scale speedups that have been demonstrated?  Given that the bounds for expectation of the maximum in the non-independent case are quite weak, some pointers to empirical data would be useful.

G. L. O'Brien, A Limit Theorem for Sample Maxima and Heavy Branches in Galton-Watson Trees, Journal of Applied Probability 17 539–545, 1980.


texts: What do we call a greedy algorithm that tracks the best $n > 1$ solutions?

texts:
A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima.

To avoid this problem, we may keep track of the best $n > 1$ solutions (instead of the best only). What is the name(s) of this algorithm?

Surprisingly, I can't seem to find the answer from Google. It'd be great if you could also list some resources on extensions to the naive greedy algorithm.


texts: Is there a concept of probabilistic quantum computers?

texts:
Answering my question Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above polynomial.
Accordingly a Quora answer

Quantum computation is fully deterministic. A given computation applied to a given starting state will always produce the same final state, every time. What is potentially non-deterministic is extracting the output in classical terms.

So, it looks like it makes sense to introduce probabilistic quantum computation (as opposed to "fully deterministic"). Does it make sense? Does such thing as probabilistic quantum computation exist in physics?
So maybe, for probabilistic quantum computation there is no known proof that there are computable functions of (probabilistic) quantum time complexity strictly above polynomial, is there?


texts: Round robin tournament scheduling using divide and conquer

texts:
I want to scheduling $n$ teams using divide and conquer method for $n \in \mathbb{N}$.My approach is that if $n$ is even divide it to to group $\frac{n}{2}$ and  $\frac{n}{2}$ but if $n$ is odd, add auxiliary team and scheduling $n+1$ team at the end we remove the last team and in table every match between $n+1$ team and others will mark as rest. but for some $n$ like 6 there will be a little problem. we should first schedule table for 3 team, 3 is odd so we should schedule for 4. for scheduling 4 teams we need schedule for 2 team and that's the base case so we have:

\begin{array}{c|ccc}
 & \text{Day 1} & \text{Day 2} & \text{Day 3} \\
\hline
1 & 2 &  &  \\
2 & 1 &  &  \\
3 & 4 &  & \\
4 & 3 &  &
\end{array}

now we should conquer the result. upper side of table didn't play with down site of table so we should schedule their matches, and remove team 4. then we have

\begin{array}{c|ccc}
 & \text{Day 1} & \text{Day 2} & \text{Day 3} \\
\hline
1 & 2 & 3 & - \\
2 & 1 & - & 3 \\
3 & - & 1 & 2\\
\end{array}

now we have table for 3 teams it's time to schedule 6 teams so we create table like this

\begin{array}{c|cccccc}
 & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\
\hline
1 & 2 & 3 & - & & & \\
2 & 1 & - & 3 & & & \\
3 & - & 1 & 2 & & & \\
4 & 5 & 6 & - & & & \\
5 & 4 & - & 6 & & & \\
6 & - & 4 & 5\\
\end{array}

for conquer step we should schedule match for upper side of table with down side so then

\begin{array}{c|cccccc}
 & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\
\hline
1 & 2 & 3 & - & 4 & 5 & 6\\
2 & 1 & - & 3 & 5 & 6  & 4 \\
3 & - & 1 & 2 & 6 & 4 & 5 \\
4 & 5 & 6 & - &1 &2 &3 \\
5 & 4 & - & 6 &2 & 3& 1\\
6 & - & 4 & 5 & 3 & 1 & 2\\
\end{array}

but it's not best answer and we can reschedule rest matches such that tournament end in 5 days for $n = 6$. how can I modify conquer step?


texts: A sufficient and necessary condition about regularity of a language

texts:
Which of the following statements is correct?

  sufficient and necessary conditions about regularity of a language exist but not discovered yet.
  There's no sufficient and necessary condition about regularity of a
  language.
  Pumping lemma is a necessary condition for non-regularity of a
      language.
  Pumping lemma is a sufficient condition for non-regularity of a
  language.

I know #(4) is correct and #(3) is false because "the converse of this statement is not true: a language that satisfies these conditions may still be non-regular", but what can be said about (1) and (2)?


texts: Possible solutions how to find all points (given by lat, long) that are within a radius from main point

texts:
let's say that I have:

M - Main point - given by coordinates (lat, long)
C - Collection of points - also given by coordinates (lat, long)
R - Radius - maximum search distance

I'm trying to find all points that are within a radius from main point (neighbors).

algorithm(main_point, collection_of_points, radius) --> neighbors

Obvious solution is to calculate distances and select those points, where distance is equal or smaller than R, but I believe there are better options with better performance.

Do you know any possible solutions? I'm open for every idea (not only the best one).

EDIT:

I should add that I'm looking for solution where points are strongly dynamic (every point is mobile phone or car). I'd like to update point when it's neccessary (it has been moved) so frequency of updates depends on amount of connected devices (so as queries). Let's say that server will get update request every 5 second and query request every 20 second.

Visualisation


texts:
Studying Quick-Find and Quick-Union heuristic I've found clear that:

with quick find trees and a union based on the size of the trees we can make a union in $T_{am}(n)=O(\log(n))$
with quick find trees and a union based on the height of the trees we can make a find in $T(n)=O(\log(n))$

But I read that using quick union trees and an union based on the size of the trees we can also have a find in $T(n)=O(\log(n))$, so my question is how can this be demonstrated? What relationship is there between height and size?

For example knowing that $\text{size}(A)=4$ I could have both:

        A                A
      / | \              |
     1  2  3             1
                         |
                         2
                         |
                         3


texts: Programmatically checking equivalence of statements

texts:
So as part of a theorem-prover/checker, I'm using Prolog to try to determine the equivalence of statements that have been parsed into tree form, e.g. $x=2$ is represented as eq(x,2), or $x=2 \land y\leq z$ if and(eq(x,2),leq(y,z)), and I want to determine if these statements are equal.

The way I'm currently (attempting) to do this is by trying to convert statements to some normal form, e.g. converting all greater-than statements to less-than statements, or eq(x,x) simplifies to true, and then statements would be compared syntactically to determine equivalence. However, this feels like it might be a tad tricky/complicated, and to some extent I'm a bit uncomfortable simply using syntax rather than semantics to determine whether they are the same.

Is there some standard way of solving determining these equivalences algorithmically, or perhaps can anyone think of a better alternative?

Much appreciated.


texts: What is the language of Sigma^n? Confused about meanining

texts:
I am learning the Theory of Computation, and I came across the language $\Sigma^n$. Could someone please explain what that could mean if $\Sigma$ is the alphabet?
Thank you so much!


texts: I've read multiple times (for example in some of the answers to this question https://stackoverflow.com/questions/8869563/how-much-memory-can-be-accessed-by-a-32-bit-machine) that a CPU with 32 bit address bus can support at most 4GB worth of memory (2^32) excluding any extensions such as PAE.  But doesn't that depend on whether memory is byte addressable or word addressable?  Assuming it is word addressable, wouldn't the maximum memory that can be supported be 2^32 * WordSize?  Granted such a CPU wouldn't be efficient due to the extra shifting that would be required to access byte level data but theoretically the memory capacity can exceed 4GB, right?


texts: Variant of Post's Correspondence Problem

texts:
I'm trying to solve the same problem as this fellow, in Java. The problem, in short, is:

Given pairs $(a_1,b_1),\dots,(a_k,b_k)$ of strings, find a sequence $s_1, \dots, s_m$ such that

$a_{s_1} \dots a_{s_m} = b_{s_1} \dots b_{s_m}$.

for all $i \ne j, s_i \ne s_j$.

If there is a shortest such sequence, the corresponding string shall be outputted. If there are several strings of equal length, the lexicographically smallest (?) one shall be outputted. The original problem is given here, and a C++ solution (which I don't understand because I don't know C++, and there are no comments) can be seen here.
If I've understood correctly, the second requirement means the i:th and j:th substrings used cannot be the same (if i and j are the same).
I'm able to solve the given sample cases, but something goes wrong quite early with the other test cases (which are unknown). This is my approach:
Load the pairs into String[] a,b. Create ArrayList<String> aOut, bOut (initialize both with new), and do:
for each pair i, if a[i].compareTo(b[i]) == 0, add them to aOut and bOut, resp.

We can also keep track of the length of the shortest pair in aOut/bOut, shortestOut, and prune aOut/bOut accordingly. These are pairs which on their own are possible outputs.
Next, we look at pairs that can be used to build matching strings from, call them bases. Such a pair (a,b) must be such that a is a substring of b or b a substring of a, counting from the first character (using regionMatches()). The longest of a, b must be strictly shorter than shortestOut.
Let's call the pairs that are neither outputs nor base pairs "block pairs". At this point, suppose we have the output pair and base pair indices (as they appear in the a[],b[]) recorded, as well as the block pair indices, in, say, outIndex, baseIndex, blockIndex. How do we build upon the bases effectively and without missing possible cases?
Here's basically how I did:
for each base pair i,
    for each block pair j, // if baseIndex.get(i) != blockIndex.get(j), do this loop

         aTmp = a[baseIndex.get(i)] + a[blockIndex.get(j)] // similarly for bTmp

         if (aTmp.compareTo(bTmp) == 0 && their length is at most shortestOut)
             add them to aOut, bOut
         else if (one is a substring of the other as before
                 && their length is strictly less than shortestOut)
         {
             add them as a new base pair
             record that the current block pair can not be used to expand the new base pair
         }

Finally we decide which of the pairs is shortest etc.
So finally my QUESTION (which isn't really Java-specific, whence my asking it here): is this a good way of going about it, or am I missing some crucial detail which finding a solution much easier? Indeed, will it do the trick? My solution runs out of memory which is probably due to the list of base pairs growing indefinitely, because I've some special case. Meanwhile the C++ solution, as far as I can tell, doesn't do the above or anything close to it. So, yeah, hints, tips and tricks, are most welcome, thank you.


texts: How to find several rectangles with minimum area to cover the red cells

texts:
In Figure 1, (a) is the input mesh, we want to find several rectangles to cover the red cells in (a), at the same time, the sum area of these rectangles should be as small as possible. Figure 1(b) and Figure 1(c) are two ways. Obviously, (c) is a better way due to the smaller sum of area the green rectangles . Besides, the side length of these rectangles should be at least two unit length, for example, the green rectangles in Figure 2 are not allowed. The rectangles can overlap.

How to do this effectively? Is there any algorithm to do this?

I have a simple idea, firstly, use the K-means algorithm to divide these red cells into K clusters, then for each cluster, find a bounding box(rectangle) to cover it. But the sum area of these rectangles may not be small.


texts: Understanding First conversion rules from church's lambda bible

texts:
While going through Church's text on Lambda calculus , I cam across the first set of conversion rules  .

Before writing out my query I would like to  put the notation that church has used for substitution  which is as follow :

$\ S$  $^x_yM $ means the act of substituting  $y$ in place of $x$ all through out $M$ .

(I think there should be a mention of free variables but do not know why has that been left out)

The following are the rules of conversion that he has introduced :

I. To replace any part $ M $ of a formula by $\ S$  $^x_yM $ , provided
that $x$ is not a free variable of $ M $ and  $y$ does not occur in N.

II. To replace any part $ ( (\lambda x M)N)$ of a formula by $\ S$  $^x_yM $
  provided that the bound variables of $ M $ are distinct both from x and from the free variables of $ N $.

III. To replace any part $\ S$  $^x_yM $ of a formula by $ ( (\lambda x M)y)$
provided that $ ( (\lambda x M)N)$ is well-formed and the bound
variables of $N$ are distinct both from $x$ and from the free variables of $N$ .

Now next church writes that Rule 1 may be used to transform  $ab (\lambda a a)(\lambda a a) $ into   $ab (\lambda b b)(\lambda a a) $

and rule III can be used to transform $ \lambda a a $ into $ \lambda a .(\lambda a a) a$  .

I tried figuring out the above usage of rule 3 but could not be sure .

So , if in $ \lambda a a $ if we think "a has been substituted in place of a" ,i.e., $\ S$  $^x_yM $ where $M$ is  $ \lambda a a $ and $x$ and $y$ are both $a$ , then I can see that application of rule 3 leads to
$ \lambda a .(\lambda a a) a$  .

Is this understanding of mine correct ?


texts:
I know that one of the techniques used by RISC machines to improve the pipeline is the delayed branch, but what other techniques do they employ, namely, can they use register renaming?

I know that Superscalar processors have register renaming, but a Superscalar processor can only be a CISC machine, right?


texts:
When people use the word "bidirectional" while describing buses, what are the two "directions" that are being talked about?

Also, why is the address bus unidirectional, as opposed to the data bus?

Edit: If all these buses are just connecting wires, what is the meaning of a 16 bit address bus? Does it mean that the wire can carry 16bits of information at a time?


texts: Deciding whether a given language is regular

texts:
I am struggling with a homework assignment. This next question seems to be pretty easy, once I get what I feel like I'm missing now. Anyway, here goes:

  Decide if the following language is regular or not and prove your
  claim.

  $$L=\{a^{i_{1}}ba^{i_{2}}ba^{i_{3}}ba^{i_{4}}ba^{i_{5}}ba^{i_{6}}ba^{i_{7}}b|i_{1}>i_{2}>i_{3}>i_{4}>i_{5}>i_{6}>i_{7};i_{1}<100\}$$

So, how do I go about doing so? Is there a thumb rule that might help? I was trying to use the pumping lemma to prove that it is not regular, but couldn't do it. I'm not even sure it really is not regular.

Any suggestions?


texts: O(1) access into an array-like data structure with numerical ranges for keys

texts:
Preface: It's been a long time since I've been in school, and my terminology is probably all wrong. Apologies...

Summary: I have a data structure with probability ranges assigned to the elements, and I want to "roll the dice" and get the element at that spot. I'm wondering if there's a (good) way to do this in O(1) time?

Assume I've got a data structure like this, where the indices/keys represent ranges, and the values are what I want:

a = {
  [0..0.3) -> "foo",
  [0.3..0.4) -> "bar",
  [0.4..0.9) -> "baz",
  [0.9..1.0] -> "qux"
}

I want to retrieve a value from that array using a randomly generated number between 0 and 1. So, using that previous example, I do something like:

a[0.2] == "foo"
a[0.3] == "bar"
a[0.5565] == "baz"
a[0.8] == "baz"
...and so forth

I think I could store the data in a tree structure where I could walk to the correct element in O(log(n)) time, but I'm wondering if there's a clever way to do it in O(1) time.

I'm also curious if there is a specific name for this kind of data structure. It seems like someone would have played with this at some point.

As background, I'm toying with creating a Markov generator, and that requires storing the frequencies for all the words/token pairs. I'm guessing this is a solved problem already, and there are probably better solutions than what I'm proposing, but it seemed like an interesting problem and now I'm curious about the index-by-range problem all by itself, independent of the Markov aspect.


texts:
The question is under the concept of LR parser.
Suppose the original grammar is
S->AA
A->aA|b

Is it necessary to add an additional rule S'->S to make it as augmented grammar?
In short, I want to know the use of augmented grammar.


texts: Loop Invariant Code Motion - am I missing something?

texts:
I've been implementing LICM for a project, and came upon a strange observation.

Let's say we have a loop

int i = 10;
while (i > 0) {
    a = 2;
    i--;
}

One can easily see that a = 2 is invariant. What we do next is check (for each invariant candidate) if the containing basic block dominates all uses of the said variable and all exits of the loop.

The former is clearly true, as a is only used once. The latter is what I don't seem to get. The CFG of the example above is

By looking at the graph we can clearly see that the cycle body (which is just a single basic block in this case) does not dominate all exits!

After thinking about this for some time, I got to the following conclusion:

In a general case, we can not know for sure if the body of a loop is going to be executed at least once. This implies that one can not simply move invariant instructions out of the loop, as they will then be executed dependless of the actual value of the loop termination condition.

I have not seen this adressed in any of the material covering LICM, as well as in the wikipedia article. In fact, their example, in which they transform

for (int i = 0; i < n; ++i) {
    x = y + z;
    a[i] = 6 * i + x * x;
}

into

x = y + z;
t1 = x * x;
for (int i = 0; i < n; ++i) {
    a[i] = 6 * i + t1;
}

seems incorrect, as the loop condition generally could have been false on the first iteration, and so x = y + z should not have been executed at all.

My proposed solution

All code deemed invariant should be put in an if (expr), where expr is the loop condition. For my original example, that would give us

int i = 10;
if (i > 0) {
   a = 2;
}
while (i > 0) {
    i--;
}


texts: Partition array - elements non-negative and negative. Minimal number of replacements of elements

texts:
I consider following problem:
It is given array with numbers, for example $[-2,0,1,-324,213,321,-2]$.
The problem is: replace elements such that negative numbers precede the non-negative. For our example: $[-2, -324, -2, 321,0,213,1]$.
Additional requirement is that algorithm should do minimal number of replacements.

My approach
Let's use partition from qsort algorithm - pivot is always $0$. It does $\lfloor n/2\rfloor $ replacements.
I think that it is minimal number. It is because of pesimistic case:
$|[1,1,..,1,-1,-1,...-1]|=n$  - in this case we must do at least $\lfloor n/2\rfloor $ replacements.

Can you give me algorithm that do less than $\lfloor n/2\rfloor$ replacements ?


texts: Find nth number which does not contain the digit c

texts: This problem was given to 9-graders. We write down numbers except for the ones which contain the digit c. Find the nth such number. I looked at the indications, but the algorithm used there stumped me. I will describe in here: if $c \ne 0$, then we transform the number n - 1 (since 0 is part of the series) in the 9th base. Then each digit in the representation of the 9th base which is bigger of equal than c and smaller than 9 will be incremented with 1. The number we obtain is the number we are looking for, BUT IN BASE 10. How? Could anyone explain it to me? Also, please, be patient since I have just started Competitive Programming and I am not really that good.


texts: Pick parameter function that minimises whole function

texts:
I have a recursive algorithm defined by the following recursion.

$$T(n) = T(n/f(n)) + O(\log f(n)).$$

I want to find the function $f$ that minimizes $T(n)$. If $f$ is a constant then $T(n) = \Theta(\log n)$. If $f = O(n)$ then $T(n) = \Theta(\log n)$. Is this true for all functions $f$ that $T(n) = \Omega(\log n)$ or can I get asymptotically better behaviour for some $f$? The reason I think there might be is that you can look at an extended binary search where you split your domain into $f(n)$ sections and then examine each section to see if your value is in that section. This recursion can be presented as follows:

$$T(n) = T(n/f(n)) + O(f(n)).$$

Binary search clearly runs in logarithmic time or worse for all values of $f$. This is the same as my recursion except that it is linear in $f$ instead of logarithmic. So you might expect better behaviour.


texts: Is Artificial General Intelligence possible with our current machine learning models?

texts:
In other words, is artificial human level intelligence not possible yet just because of limitations in processing power and amount of data required to train the models? Or we don't have the knowledge of how to achieve it even in theory?
Suppose that processing power and amount of training data is not a problem, could humanity build AGI with our current machine learning models and knowledge?


texts: Prove that the TM which would go over the leftmost position is not decidable

texts:
Let $M$ be a one-band TM and $w$ a word. We say that M tries to move the head over the left margin of the band if, while the head is in the leftmost position of $w$, the TM $M$ tries to move to the left.

Show that the language

$ LEFT_{TM} = \{<M,w> | $ M is a TM of the type above $\}$

is not decidable.

How can I show that such a language is not decidable?

I was thinking about using the TM $A$ which accepts any input and reduce it to $LEFT_{TM}$, but I'm not sure how. I would appreciate a nudge in the right direction.


texts:
Context:

I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's children. Additionally, I'd like to be able to replace one of the node's children in constant time (i.e., not doing a full recombination of hash values) as the branching factor for the tree could be quite large.

Question:

I am looking for a set of functions ($combine$, $separate$) that operate on fixed width integers and have the following properties.

Let $X$ be some set of integers with fixed width $b$.

(1) $combine(X)$ outputs an integer with width $b$

(2) $combine(X)$ operates in $O(|X|)$ time complexity

(3) $$combine\Bigl(\left\{t, separate\bigl(combine(X), x\bigr)\right\}\Bigr) = combine\Bigl(\bigl(X \setminus \{x\}\bigr) \cup \{t\}\Bigr)$$
where $x \in X$ and $t$ is some integer of width $b$.

(4) $separate(X, x)$ operates in $O(1)$ time complexity

(5) The outputs of $combine$ are going to be used as hash values so an algorithm with a "good" distribution of output values to avoid collisions is ideal. That said, I'd define good as anything better than trivial addition and subtraction (see below).

Initial thoughts:

A trivial implementation would have $combine$ and $separate$ be addition and subtraction (with some modulo logic); however, this obviously won't have a good distribution for tightly bunched input values.


texts: Computability of sequential cubic-order algorithms

texts:
I have a cubic-order algorithm which must be executed sequentially; there appears to be no way of making it parallel.

I need to come up with an estimate of maximum input size that can be solved using today's technology. So, the essential problem seems to be how to relate the cost of a single step to execution time on a "typical" hardware. Is there a gold-standard way of doing this, e.g. something an attentive peer-reviewer would like to see being done in a manuscript?


texts: Counting inversions in a list of integers using divide and conquer techniques

texts:
This is a homework. It looks easy, but not really.

A list of integers $a_n$, for every $i<j$, if $a_i>2a_j$, then it is an inversion. Count the inversions in the list, and return the count and the ordered list. Note, here the order is defined by the condition, not just sort the integers.

The easiest way is double loop, but it will be a $O(n^2)$ algorithm. So I think I should try divide and conquer, by modify the merge sort algorithm. I think I could get a $O(n \log n)$ algorithm. But I found, while merging and counting cross-halve inversions, I have to scan all the elements in both left halve and right halve. Equivalent to a double loop.

For example:

[8] [6, 3]

8 and 6 are not inversion, 6 and 3 are not inversion, but 8 and 3 are inversion. I have scan all the elements to make sure there's no exception.

Another example:

[2, 7] [1, 5]

There no inversion in either halve, but 7 and 1 are inversion.

I am thinking may be there's a function, and I can define $b_n=f(a_n)$, then I can treat $b_n$ as normal merge sort problem. But I could not figure it out.


texts: Why is it not always possible to compute the centroid of feature vectors?

texts:
Hi in the data mining and machine learning course that I'm taking there is a subject on feature spaces and there is this part about feature vector aggregation and metric spaces that I don't really understand. Now our curriculum is basically a huge presentation and the whole information about feature vector aggregation fits on one slide, anyway what I don't understand is this:

For a given sample $D$ the centroid can be computed as   $C_D = \frac{1}{|D|}\cdot\sum_{o\in D} o$

and then on the slide it says, quote:

  In a general metric space (that is, not a vector space),
  where we only have pairwise distances, it might not be
  possible to compute a centroid

I don't really think I understand what "only pairwise distance" means (my guess is it has something to do with the fact that a metric space defines the distances between all pairs of elements in its set) or why the consequence of it is that you can't always compute the centroid.

I read somewhere that metric spaces does not have to define addition or scaling and if that is the case it makes sense to me that you can not calculate the centroid. Is this what it essentially is about or am I completely misunderstanding something?


texts: Why is the halting problem semi-decidable?

texts:
This is what is known about the halting problem and semi-decidability :-

The halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x.

A language is said to be Semi-decidable if there exists a Turing machine which halts if a word belongs to the language (YES cases) and may reject or go into infinite loop if the word doesn't belong to the language (NO case).

Now, in the halting problem we can't say whether the machine will halt even if the input belongs to the language (YES cases). Then how is it Semi-decidable? I think it should be non-recursively enumerable or undecidable.


texts: Can a 1-tape turing machine simulate a stack?

texts:
Is it possible to simulate a stack-based machine using a 1-tape turing machine? I cannot wrap my head around it as turing machines do not provide mechanisms such as pointers.

I failed to find any examples or explanations. If it is possible, how?


texts:
I have the following homework problem, with given solution but I do not understand why certain choices in the solution were made as opposed to my own (incorrect) solution and I would like some clarification.

The question is to compare the growth rates of several functions using o, O and $\Theta$.  It is the first time I have seen this notation and it is assumed knowledge for the class.

I am given the relation:

$f(n) \leq c.g(n) \Leftrightarrow \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

I have the following function $n\log n$. I am then supposed to compute o$(n \log n)$, according to the solution. As I interpreted the relation above and in the problem I had picked $f(n)$ and $g(n)$ to be the same $n \log n$ and evaluated to find that limit and quickly concluded my answer was incorrect.

The solution sets $f(n)=n^l$, where $l \in \mathbb{N}$ and $g(n)=2^n$ and the proceeds to calculate the limit and shows that it is in fact 0 as $n \rightarrow \infty$. I am fine with calculating the limit, I do not get why $f$ and $g$ were set to be what they were and how I would make this choice in the future, for say a different function not $n \log n$.

Any help in explaining why it has to be this way, would be really appreciated. Thanks!


texts: Dijkstra's Algorithm with different color nodes

texts:
You are given a directed graph G = (V, E) and nodes s, t. Nodes are colored red, white, and blue. A path from s to t is called colorful if it contains both a red node and a blue node. The task is to determine if a colorful path exists, and if so, find one that contains a minimum number of white nodes.

Im not sure how to get started on this. Any help is greatly appreciated!


texts: Longest Even-Length Palindromic Subsequence (with distinct adjacent characters except for the center 2 letters)

texts:
You are given a string S containing lowercase English characters. You need to find the length of the largest subsequence of S that satisfies the following pattern:
X1,X2,X3...Xn,Xn,...X3,X2,X1
where Xi is some character of S. The only constraint is that no adjacent character should be the same except Xn, that is Xi != X(i+1) for all 1<=i<
n.

Input: The string: S
Output: The integer: 2n
Constraint: 1<=|S|<=10^3

Sample input 1: "acdbdea"
Sample output 1: 4
Explanation: "adda" is the longest subsequence following the given pattern.

Sample input 2: "abbacdeedc"
Sample output 2: 6
Explanation: "cdeedc" is the longest subsequence following the given pattern.

Sample input 3: "taker"
Sample output 3: 0
Explanation: No subsequence follows the given pattern.

This question was asked in a coding interview and I didn't know how to solve it. I understood how to find the longest palindromic subsequence but don't know how to implement the distinct adjacent character part. Please help. Pseudocode is fine.


texts: Inviting an optimal subset of persons such that all friends of a person invited are invited

texts:
Let's say that you want to invite a person $u$ in party $P$. The
person $u$ will join the party if and only if all the friends of $u$ will join the party as well. Otherwise, $u$ will reject your invitation. Hence, we have two sets: $P$ with all the persons, and $F$ with the friend relations. Suppose $(u, v)$ belongs to $F$. This means that $u$ treats $v$
as a friend of $u$, and thus $u$ will reject your invitation if $v$ does not join the party. Note that $(u, v) \in F$ doesn’t mean that $v$ treats $u$ as a friend of $v$. Also, every person $u$ in $P$ has a quality measure, $p_u$ (this can be positive or negative and is given). Now I need to find a subset of $P$, such that all those in the subset won't reject my invitation and the qualities among the people is maximized.

Here is an example of a feasible and non-feasible subset:
$P = \{a, b, c, d\}, F = \{(a, b),(a, c),(b, d),(b, c)\}, p_a = 10, p_b =
1, p_c = 1, p_d = −20$.
A subset $\{a, b, c\}$ is not feasible because $d$ is not
invited and thus $b$ rejects your invitation.
A subset $\{b, c, d\}$ is feasible with total quality is $p_b + p_c + p_d = −18$ which is not maximized. The optimal
subset $A$ of this example is $\{c\}$ with total quality is $p_c = 1$.

Now I need to design an algorithm that finds this optimal subset in $O(|P|(|P| + |F|)^2)$ time.
My thoughts:
The elements in $F$ are directed edges, and the elements in $P$ are the nodes. As we are kind of dealing with a maximum flow problem, and as the required running time resembles the running time of the Ford Fulkerson algorithm $O(VE^2)$, I thought, that $(|P| + |F|)$ should be the amount of edges in the graph. Hence, my thought was to split each node $u$ into two nodes, say $u(\mathrm{in})$ and $u(\mathrm{out})$ with the directed arc $u(\mathrm{in})\rightarrow u(\mathrm{out})$ and edge weight the $p_u$. This way we have $(|P| + |F|)$ edges. However, the max flow algorithm doesn't necessarily saturate the edges it travels. However, in my case, whenever a node is reached (person is invited)/edge is travelled it adds the full flow $p_u$.

How would you approach this problem? And what are your thoughts on how the algorithm should work?


texts: Data Structure which maintains spacing for similar elements

texts:
I want a queue like data structure in which a new element inserted has to be some elements away from a related element.

While reading from this data structure, related elements should only be read after some time.

Suppose X is inserted. Then Y which is related to X should only be inserted at a position which is k elements away from X.

The relation is my own condition and can be found in O(1).

If a stream of elements are coming to be inserted we can hold related elements and then when some unrelated elements are inserted such that the distance criteria is fulfilled it should insert the related element.

So is there some type of data structure which can achieve this.