texts:
I'm making a program to play the board game Quoridor. I build a move tree using Monte Carlo Tree Search (MCTS). MCTS requires me to test whether a node is expandable.  A node is said to be expandable if it has a child node that hasn't already been visited.
How can I test whether a given node is expandable?
I know you could always try out every play possible given a node, and test whether each generated node is already a node in the tree, but that seems inefficient.  Is there a more efficient algorithm?
The rules of Quoridor are (quoting from Wikipedia):

Quoridor is played on a game board of 81 square spaces (9x9). Each player is represented by a pawn which begins at the center space of one edge of the board (in a two-player game, the pawns begin opposite each other). The objective is to be the first player to move their pawn to any space on the opposite side of the gameboard from which it begins.
The distinguishing characteristic of Quoridor is its twenty walls. Walls are flat two-space-wide pieces which can be placed in the groove that runs between the spaces. Walls block the path of all pawns, which must go around them. The walls are divided equally among the players at the start of the game, and once placed, cannot be moved or removed. On a turn, a player may either move their pawn, or, if possible, place a wall.
Pawns can be moved to an adjacent space (not diagonally), or, if adjacent to another pawn, jump over that pawn. If an adjacent pawn has a third pawn or a wall on the other side of it, the player may move to any space that is immediately adjacent to other adjacent pawns. The official rules are ambiguous concerning the edge of the board.
Walls can be placed directly between two spaces, in any groove not already occupied by a wall. However, a wall may not be placed which cuts off the only remaining path of any pawn to the side of the board it must reach.

I'm using the Monte Carlo Tree Search algorithm, which follows these steps:

Selection: Using a tree policy, like UCT1, nodes are selected while traversing down the tree
Expansion: From the node selected by the tree policy, create a random child node
Simulation: Either use a random simulation from the node or a system with a weighing of moves
Backpropagation: If the simulation is victorious for the computer, add say each node "won" all the way up the tree. If it lost, then each node "lost" up the tree.

During the Selection step, one cannot select a node that is fully expanded. Is there a better way to check whether a node is expandable than just trying out every possible move from that node, and check if it is already in the tree? What algorithms exist for this (if any?)


texts: Algorithm to replicate human noising of names by creating a categorical distribution given a character, with higher probabilities on similar chars

texts:
I’m trying to find a way without just hard coding to create a categorical distribution over all characters given a character but with similar looking ones having higher probability. For example, if the input is ‘l’ then 1,j,!,/,I,t would be characters considered similar looking and should have a higher probability than other letters. Is there a way to do this without hard coding a distribution for every character?

The reason for this is I'm trying to create an algorithm that noises human names similar to the noise you'd expect in a dataset that are due to human error. For example, "Frank" could be noised by a person to be like "Fr4nk" (maybe they quickly doubled checked their work and they mistook the '4' for an 'a') or something like "Dell" could easily be miss inputted by a person as "De11" or "DeII"(These are actually capital i's rather than l's). I'm trying to create an algorithm to replicate this accurately.


texts: In algorithm analysis what does it mean for bounds to be "tight"

texts:
For example we could say alg(x) runs big omega(n) but this bound is not "tight".

What is meant by "tight"? Is it that the bound isn't at its maximum?

So maybe a tighter bound could be big omega (1)??


texts:
Say, I want to put N objects into a hash table. How do I figure out how big the size of the table needs to be to have K comparisons on average when the table is: half full? three quarters full? all but last full?

Basically, this is due to me not really understanding the theory. I tried googling it, but didn't get it either. Can I have an explanation even a monkey would understand?


texts: Is every subset of a RE language also RE, in general?

texts:
I'm trying to understand the question in my title in an intuitive way:
If I have an RE language A, then some TM, say TM(A) accepts on it. If I take a subset of A, say A2, then all elements of A2 will cause TM(A) to halt in the accept state.

However, is it in general possible to then create a TM for A2, say TM(A2), such that A2 is the max possible set that halts TM(A2) in the accept state. Thus making A2 its language - and would this language be RE?

Thanks


texts: What are the minimum and maximum numbers of elements in a heap of height h?

texts:
I came across the question:

What are the minimum and maximum numbers of elements in a heap of height $h$?

To which I came up with this theory:
$$\sum_{i=0}^{h-1} 2^i = 2^h-1$$
$2^h-1$ is the internal nodes and that is understood according to the understood fact. But because nowhere except CLRS mentions heaps to be a Nearly Complete Binary Tree everywhere it is mentioned as a Complete Binary Tree.
The maximum number of elements can be easily computed:
$$\sum_{i=0}^{h} 2^i = 2^{h+1}-1$$
But I cannot get the point of computing the minimum number of elements:
Should it be:
$$2^{h}+1$$ for $0$ or $2$ children property
Or should it be:
$$2^{h}$$ for $0$ or $1$ children property
Reference1: https://walkccc.github.io/CLRS/Chap06/6.1/#61-1
Reference2: HeapSort
Thank you.


texts: Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^*(bb^*aa^*ba^*)^*$ ?


texts:
Yesterday I wrote my undergraduate exam in complexity theory. I had to leave off one question, which bugs me since then. Consider:
$$ HALF-SAT = \{ \varphi \mid \varphi \text{ is a formula which is satisfied by at least half of all assignments }\} $$
I'd like to know how I can prove NP-hardness.

FWIW, here's what I figured out:

HALF-SAT is probably not $\in$ NP, at least in no verifiable way I can think of (not really relevant to the question)
SAT $\preceq$ HALF-SAT doesn't work, at least not by just adding clauses with new variables, doesn't change satisfiable-assignments/arbitrary-assignments ratio
TAUT $\preceq$ HALF-SAT via $\varphi \mapsto \varphi \wedge x_{new}$, but that's coNP-hardness (together with NP-hardness this further lets me assume 1., intuitively)

And no, this has nothing to do with the problem you find via googling "HALF-SAT".


texts: Branch and scope globally unique identifiers

texts:
Say we are working with a Prolog-like system where variables are dynamically created in different branch contexts and scopes, yet these variables are also globally viewable by the system regardless of the current context. Is there a way to label each variable with a unique scope ID which can be used to determine if the variable assignment is considered live (i.e. not discarded by backtracking) in the current context.

Naively, you could create a bitstream of left/right branch decisions, but the memory usage would be really excessive and also have bad query time for liveness. Can anything better be done?


texts: Introduction to the Traffic Light Scheduling Problem

texts:
I would like to understand the basics of how traffic light scheduling works. Looking through research papers the topics typically revolve around actual highway systems in urban areas, but also includes managing information routing in wireless networks, and a few other areas. They also seem to be modeled similar to how machine learning is modelled, using feature vectors and optimization functions rather than using discrete concrete objects. This approach is a bit hard to comprehend as a newcomer, which leads me to look for a graph theory based approach.

I am wondering what the basic graph theoretical mathematical model looks like for a traffic system composed of discrete entities such as traffic light and entity, and how they go about modeling the optimization of the flow of traffic, not necessarily specific to cars or wireless networks, but to agents or entities in general.

It seems that it would start off like this:

Given an entity $\phi$ and a traffic light $\psi$, and intersection $\gamma$, the entities are essentially messages being passed around through intersections, which are being governed by traffic lights. This could be seen as a graph $G = (V, E)$ where intersections are the nodes $V$ and the edges are the roads $E$. The roads are directed.

Given that, I am left wondering how to possibly define the problem of the flow of entities through the roads/intersections, governed by the traffic lights, and how the traffic lights are turned on and off. At first glance it seems like an unsolvable problem. I understand basic graph theory but haven't seen anything on this complexity of entities flowing through the graph with these sort of constraints. Would like to know what the general model is of it so I can learn where to go from here.

The specific example I am interested in is making sure each intersection has an equal amount of entities pass through it.


texts: How to determine memory allocation for single level table

texts:
I received this problem on my study guide but I have no idea if I'm doing it correctly:
How much space needs to be allocated for a single-level page table for a machine with a 32 bit virtual memory address and a 4K page size?
I understand that the last 12 bits of the address is the offset but how would I determine how much space is needed?


texts: What Computer Science projects for undergrads are mostly in demand by European and American firms?

texts: Computer Science has a broad spectrum of disciplines ranging from AI, Big Data, Cryptography to Human Computer Interaction and Bioinformatics. I would like to know what projects are ideal for undergrad students of CS among these disciplines that can attract funding from European and American firms.


texts: Constructing an FSA, where Ratio of number of states of FSA to its Minimal DFA Equivalent < 0.5

texts:
I need to choose a language, design a finite automaton M such that L = L(M). Construct a minimum-state DFA M′ equivalent to M in such a way that the ratio of the number of states in M to the number of states in M′ is less than 0.5.

I have zero idea as to how I should approach this. I've tried considering a few DFA's, as its the best place to start, considering that NFAs obviously have fewer states than their corresponding DFAs, but I'm not able to think of an approach to derive or contemplate a DFA with it's minimal counterpart having states < 0.5 times number the original DFA.


texts: What is the most efficient algorithm for finding the bounding inequalities of a cone given the extremal rays?

texts: Say that I am given a cone, as specified by the extremal rays whose facets form its convex hull, what is the most efficient algorithm that finds the linear-rank inequalities whose intersection defines the interior of the cone? Also, what is its run time? I have a situation where I have on the order of several thousand extremal rays organizable into 16 distinct families related by S_6 symmetry, and I am wondering about whether there exists a feasible algorithm that addresses this problem.


texts:
Solving $T(n) = \frac{1}{n}(T(0)+T(1)+...+T(n-1)) + cn$ for all $ n \geq 1$

Subbing few numbers in we get

$T(1) = T(0)/1 + c(1)$

$T(2) = \frac{T(0)+T(1)}{2} + c(2) $

Which is kind of going backwards as I am going back to finding T(n)

So I am kind of confused about it, any idea?

Are we even able to unroll this reccurence?


texts:
What is meant by a short pipeline?

Does that mean the instructions are split into small number of pieces OR length of a piece is short?


texts: Drawing a DPDA for the language $L=\{w\in\{a,b\}^*|n_a(w)=n_b(w)\}$ in Sipser's format

texts:
As I know $L=\{w\in\{a,b\}^*\mid n_a(w)=n_b(w)\}$ is a deterministic context free language. I have drawn a push dawn automata for this language in the format of Sipser as the following

However, as you may know, in Sipser's format, the transition
$$\varepsilon,$;\varepsilon$$
means that "don't read any thing from the input" and it doesn't mean "read $\varepsilon$ from the input". In Sipser's format this is a non-deterministic push down automata, since in deterministic one, we have that if there is a transition
$$\varepsilon,$;\varepsilon$$
outgoing from the state $q_1$ then it must not be an outgoing transition
$$a,$;a$ $$
from that state.
Could you please help me to draw a DPDA for that language in Sipser's format?


texts: How to prove universality in complex systems?

texts:
I'm working on my graduation project for CS, which is about cellular automata. Recently, i was able to build a system where the input is transferred to multiple different structures at once.  The input consists of numbers, a sequence of numbers ranges from (-infnite to infinite), like ('5','65443'or'9921075').

From the sequence of numbers {input}, i can see each number's behavior and how it interacts with other numbers by analysing the different structures it outputs, it is like a Cellular Automaton structure simulates another Cellular Automaton structure.

How can i relate these properties to universality, What should i look for or analyze in these structures to show universality?


texts: What happens when ε-clos(X) contains duplicate elements? Example: (1+0)*1

texts:
I am learning about state machines from the Stanford online cs143 course. Here I have tried to build a nondeterministic finite automaton for the regular expression (1+0)*1, but when I attempt to convert it to a DFA I find that the epsilon closure of the initial state A ends up having two outputs for the value 1, which I imagine would be impossible for a deterministic automaton.

I understand that my NFA differs from the instructors, but I'm unsure of whether or not it is valid. If it is valid, why am I having difficulty converting it to a DFA?


texts: Finding a successor in a binary search tree in $O(1)$

texts:
In my algorithms course I have learned about the binary search tree and its functions add, find and remove.
I have also learned about how to find the successor and the predecessor in a balanced binary search tree, but they are both $O(\log n)$ I think.

Now, I have been thinking, how can I change a given binary search tree so that I could find any given node's successor in $O(1)$ time? The other operations should still run in $O(\log n)$ time.

I have thought about maintaining the tree in a linked list but I am sure that there is a better solution to it.


texts:
Say that $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$ are two strings of the same length.  An anagramming of two strings is a bijective mapping $p:[1\ldots n]\to[1\ldots n]$ such that $a_i = b_{p(i)}$ for each $i$.

There might be more than one anagramming for the same pair of strings.  For example, If $a=$`abcab` and $b=$cabab we have $p_1[1,2,3,4,5]\to[4,5,1,2,3]$ and $p_2[1,2,3,4,5] \to [2,5,1,4,3]$, among others.

We'll say that the weight $w(p)$ of an anagramming $p$ is the number of cuts one must make in the first string to get chunks that can be rearranged to obtain the second string. Formally, this the number of values of $i\in[1\ldots n-1]$ for which $p(i)+1\ne p(i+1)$. That is, it is the number of points at which $p$ does not increase by exactly 1.For example, $w(p_1) = 1$ and $w(p_2) = 4$, because $p_1$ cuts 12345 once, into the chunks 123 and 45, and $p_2$ cuts 12345 four times, into five chunks.

Suppose there exists an anagramming for two strings $a$ and $b$. Then at least one  anagramming must have least weight. Let's say this this one is lightest. (There might be multiple lightest anagrammings; I don't care because I am interested only in the weights.)

Question

I want an algorithm which, given two strings for which an anagramming exists, efficiently yields the exact weight of the lightest anagramming of the two strings. It is all right if the algorithm also yields a lightest anagramming, but it need not.

It is a fairly simple matter to generate all anagrammings and weigh them, but there may be many, so I would prefer a method that finds light anagrammings directly.

Motivation

The reason this problem is of interest is as follows.  It is very easy to make the computer search the dictionary and find anagrams, pairs of words that contain exactly the same letters.  But many of the anagrams produced are uninteresting.  For instance, the longest examples to be found in Webster's Second International Dictionary are:

  cholecystoduodenostomy
  duodenocholecystostomy

The problem should be clear: these are uninteresting because they admit a very light anagramming that simply exchanges the cholecysto, duedeno, and stomy sections, for a weight of 2. On the other hand, this much shorter example is much more surprising and interesting:

  coastline
  sectional

Here the lightest anagramming has weight 8.

I have a program that uses this method to locate interesting anagrams, namely those for which all anagrammings are of high weight. But it does this by generating and weighing all possible anagrammings, which is slow.


texts:
Consider propositional logic over the connectives $\land$, $\lor$, and $\lnot$. Notation: $| \alpha |$ is the length of formula $\alpha$.

We are given a formula $\phi$. Cancel all cancellable negations in $\phi$ by applying all possible valid biconditionals (EDIT: such as the examples below) to get $\phi'$; for clarity we note that $\phi \leftrightarrow \phi'$. We are also given that $\phi'$ is monotonic. Are there examples where $| \phi' |$ must grow exponentially, or is $| \phi' |$ bounded by a polynomial? If there's an example of exponential growth, please show it.

EDIT: The following biconditionals are examples of what I'm trying to get at, formulas which can be used to cancel negations while preserving equivalence. The procedure would presumably be to unify the left-hand side of the formula with $\phi$ via unification and substitute the right-hand side as appropriate per unification.

$$\alpha \land (\lnot \alpha \lor \beta) \leftrightarrow \alpha \land \beta$$ $$\lnot \lnot \alpha \leftrightarrow \alpha$$


texts: What does point-free mean mathematically?

texts:
Point-free style is generally taken to mean a style of programming without explicit variables.
I have some intuitions on point-free style but I want to know what the formal mathematical definition is.
I feel like the informal definition should not be taken too literally. Universal quantification, labels/continuations and a variety of other constructs are a sort of binder as well right? And I have the intuition de-bruijn indices aren't really point-free style either.
I understand the term point-free originates in topology and maybe category theory but I don't really understand how these perspectives relate.
"point" in category theory just seems to mean working in terms of the covariant Hom functor "Hom(x, -)". Under this definition a Cartesian category could be defined in a pointy way as a category where Hom(x, -) has
fst : Hom(x, a * b) -> Hom(x, a)
snd : Hom(x, a * b) -> Hom(x, b)
fanout : Hom(x, a) -> Hom(x, b) -> Hom(x, a * b)

This is not what I would expect a "pointy" definition of a Cartesian category to be though. I would expect something like the Kappa calculus to be a "pointy" way of talking about Cartesian categories in the same way the lambda calculus might be a pointy way to talk about Cartesian Closed categories.


texts:
I want to show that $\text{NP} \neq \text{SPACE}(n)$ and tried it like this:

Let $L$ be in $\text{SPACE}(n)$ so there is a deterministic $k$-tape TM which decides $L$ in polynomial time. Let's consider a binary alphabet. There are $2^{kn}$ possible strings on the working tapes so for an input of length $n$ the TM can be in $2^{kn} \cdot k \cdot n \cdot |Q|$ different configurations where $Q$ is the finite state set.

Since the TM is deterministic and decides $L$ no configuration can be visited twice (otherwise we would be in an infinite loop). So $2^{kn} \cdot k \cdot n \cdot |Q|$ is also an upper bound for the runtime of the TM which is exponential and therefore not in $NP$.

Is this argumentation enough? I found this answer on the internet and now I'm confused because it looks so much more complexive but also comprehensibly...


texts: how to prove that the property 'doesn't halt for some input' is not semidecidable

texts:
I am taking a computer theory class and one of the exercises is to prove that the property "doesn't halt for some input" is not semidecidable. This property is the negation of the property "halts for all inputs".

I know that the halting problem is undecidable, but i need some kind of contradition to prove that the negation ("doesn't halt for some input") is not semidecidable as well.


texts: Why is Hamming Weight (in the CRC context) independent from the data?

texts:
I'm designing a communication protocol for 24 to 52 bits (typically 32 bits) data including the CRC-8 for error detection. I'm trying to select the best polynomial for this kind of application.

In the paper Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks Koopman, et. al. gives a very nice method to select a CRC polynomial depending on the needs of the application. The paper proposes that if Hamming Distance of two or more polynomials are equal, select the minimum Hamming Weight for a given bit length and error bits. Also Koopman kindly makes all these calculations and information publicly available in his site: http://users.ece.cmu.edu/~koopman/crc/index.html

As he also suggests "Don’t blindly trust what you hear on this topic", I've also verified his results for some of the 8-bit CRC polynomials using my own software. But here is what I failed to understand:

In the paper 32-Bit Cyclic Redundancy Codes for Internet Applications he defines the Hamming Weight as

  A weight $W_i$ is the number of occurrences of a combination of $i$ error bits, including bit errors perturbing the CRC value, that would be undetected by a given polynomial for a given data word length.

Also, he explains why the Hamming Weight is independent from the data as follows:

  Consider the fact that a data corruption is undetectable if and only if it transforms one codeword (some payload with its valid FCS value) into a different valid codeword.  But because CRCs are linear, this means that the faulty bits that have  been  flipped  from  the  original  codeword  have  to themselves form a valid codeword. (In other words, the bits flipped in the message payload have to be compensated for by bits flipped in the FCS field, and the only way this can happen is if the entire set of bits flipped is itself a valid codeword.) This means that the actual data in a message payload is irrelevant in computing error detection abilities, which simplifies things greatly.

I also tried to calculate the Hamming Weight for different data and indeed obtained the same results. But I don't understand why this is the case. A rigorous proof or any different insights are greatly appreciated.

Edit: The example for Hamming weight given in the paper:

Suppose we have a codeword of length 12144 bits. So we have

$$ \pmatrix{12144 \\ 4} = \frac{12144!}{12140! ~ 4!} = 906 \times 10^{12} $$

possible bit errors. Hamming Weight is the number of undetected 4 bits error out of all possible 4 bits errors. So it is calculated for 802.3 CRC polynomial to be $W_4 = 223059$. This means $223059$ of $906 \times 10^{12}$ errors go undetected and this number does not change with the used codeword.


texts: How do incompressible strings and random strings share the same properties?

texts:
I came across the following theorem in Sipser's about incompressible strings.

  Let $\;f$ be some computable function which holds for almost all strings. The for any $b > 0 $, the property $\;f$ is false only on finitely many strings that are incompressible by $b\;$.

where "almost all strings" means that as $n$ grows the fraction of strings of length $n$ for which $f$ is false approaches $0$.

The book proves the above theorem and says that if we select some sufficiently long string at random, it's likely that property $f$ would hold true for it. Thus incompressible strings and random strings share this property.

Though I understand the proof for the theorem, I am unable to understand its meaning. How does this show there is some sort of relation between incompressible strings and random strings?

Also how does this theorem help us? Although I can generate random strings, there is no method to generate incompressible strings in general.


texts:
It is clear that any language in $\mathsf{EXP}^{\mathsf{EXP}}$ can be computed in $\mathsf{2EXP} = \mathsf{DTime}(2^{2^{\mathsf{poly}(n)}})$.

My question is whether the converse is true: is $\mathsf{2EXP} \subseteq \mathsf{EXP}^{\mathsf{EXP}}$?


texts: Is the problem of traversing every vertex of a graph (not necessarily once) without crossing an edge more than once in P?

texts:
I know that finding a Hamiltonian circuit is in NP and I know that finding an Eulerian circuit is in P. However, what about the following problem:

Must leave the starting vertex and visit every other vertex;
You may only return to the start after visiting every other vertex;
You can visit the same vertex multiple times, as long as it's not the starting vertex;
You don't have to use every edge in the graph, but each edge can only be used once.

Is that in P or NP-hard? I tried different approaches to this but now I don't know if I'm wasting my time in case this problem doesn't have an efficient solution.


texts: Two adjacent vertices in a polytope uniquely minimize some linear form

texts:
In linear programming, if we model the solution as a polytope, every vertex is a solution.

I'm trying to prove the following statement:

  If $x$ and $y$ are two solutions with $n-1$ joint constraints, there exists a solution vector $c$ such that, for each $v\in P$ (the polytope of the problem) that is different from $x$ and from $y$, we have $\langle c,x\rangle = \langle c,y\rangle < \langle c,z\rangle$.

Basically, this means that only $x$ and $y$ are the optimal solutions for the problem.  But why is it true? And what is the vector $c$ that exists here?


texts: Understanding time complexity of dynamic array implementation of stack

texts:
let me tell you first what is written in the book I am following.

If the array is full,create a new array of twice the size, and copy items.
At n=1,we do 1 copy operation,at n=2,we do 2 copy operation and at n=4 we do 4 copy operation and so on.
By the time we reach n=32,the total number of copy operation is $1+2+4+8+16=31$ which is approximately equal to $2n$  i.e (32).

Ok ! so far I got it. My question is that can't we say that since by the time we reach $n$ we have $2n-1$ copy operations ,time complexity would be $O(2n-1)=O(n)$?

further the books says

we are doing the doubling operation $\log n$ times .(OK)
For n push operations we double the array size $ \log n$ times .

here we performed 7 push operation and doubled the array  $\log 16=4 $ times so what does the above statement say?
Kindly help me calculate the running time in simplest way.


texts: Gyorgy E. ReveszExercise 1.1: Show the grammar $G$ generates the language $L$

texts:
The exercise says

"Show that the grammar $G = \langle\{S\}, \{a, b\}, S, \{S \to \lambda, S \to aSb\}\rangle$
generates the language $L = \{a^i b^i \mid i = 0, 1, 2, \ldots\}$."

Now, I'm new to this subject although I'm familiar with the theory of Turing machines and automata. I'm teaching myself (not in a class, completely independently) from scratch. Please go easy on me.

Now, two questions:

(1) I suspect the way to do this proof is by induction on $i$, which is to say induction on the iterations of letters in the alphabet or the length of the word formed by iterations of $a, b$. Is this assumption correct?

(2) If the assumption in (1) is not correct, what is the correct strategy?


texts: Practical example for recurrence relation of merge sort with more than 2 sublists

texts:
I couldn't wrap my head around for finding an example for the following recurrence.

  $T(n) = a T(n/b) + f(n)$ where $a \neq b$ and $b > 1$

If we divide n elements with b, it should give us a sublists each with size n/b

Could somebody please give me a practical example of this?


texts:
I'm working from a definition of the LL(1) property of context-free languages in order to build a LL(1)-computer, i.e., a program capable of determining whether a given context-free language is in LL(1).

The definition requires the disjointness of certain sets; each set is defined as an infinite limit, but practically calculated via fixed-point iteration of an inductive, case-based equation.

Present in these equations is the definition of a new operator to simplify the notation (let $\epsilon$ be the empty sequence):

$$\forall S,T : S \oplus T = \begin{cases}
  S & \epsilon \not\in S \\
  (S \setminus \{\epsilon\}) \cup T & \epsilon \in S
\end{cases}$$

I know this operator in latex as \oplus. In an attempt to write readable-code, I want to give this operator a name (and endow scala Sets with a trait that expresses this name).

Is there a traditional name for this usage of $\oplus$? If so, what is it?

Bonus points: if the name is, e.g., add, is there an acceptable word like addable with the meaning that two objects—mathematical or code—are capable of being added?


texts:
I have a vector $v \in \mathbb{N}^k$ and a set of vectors $R \subset \mathbb{N}^k$, with $k \ll \left\vert R \right\vert $.

I would like to find a way to obtain all the possible bases of $\mathbb{N}^k$ taking $k$ elements from $R$.

The ultimate goal is to find a decomposition of $v$ over a subset $S = \left\{ r_1, r_2, \ldots, r_q\right\} \subset R $ that will minimize a given cost function $f$.

Unfortunately the search space is really large ($\left\vert R \right\vert > 10^5$ even for basic problems), so I cannot just try to brute force a solution.

Is there any algorithm or theorem related to my problem that I could exploit?

UPDATE

It has been pointed out that $\mathbb{N}^k$ is not actually a vector space.
I guess that it would be more correct to frame the problem in $\mathbb{Z}^k$, although all the components of all the vectors in my problem must be non-negative.
I guess that a more correct statement is that $v \in (\mathbb{Z^+} \cup \left\{0\right\})^k$.

I forgot to specify an important condition: all the vectors in $R$ are such that the sum of their components does not exceed a given constant $T$.
In fact, $R$ is defined as

$R = \left\{r \in \mathbb{N}^k \mid \sum r_i \le T \right\}$

When I say "decomposition of $v$ ", I mean that I would like to find a set of vectors $S = \left\{r_1, r_2, \ldots, r_n\right\} \subset R \subset \mathbb{N}^k$ such that $v$ is a linear combination of the elements of $S$. I am also assuming that $ 0 \in \mathbb{N}$. In formula:

$v = \sum x_i \cdot r_i$

where $x_i \in \mathbb{R}$ (truth be told, I am especially interested in the solutions where $x_i \in \mathbb{N}$, although those are simply better solutions than the non-integer ones).

The cost function is still under development and thus I don't have a precise formulation to share right now.
Roughly speaking, it will be proportional to the cardinality of $S$, inversely proportional to the norm of each vector and inversely proportional to the number of non-zero components of each vector. Therefore, something essentially like this:

$ C(S) \propto \frac{\vert S \vert}{\sum \Vert s_i \Vert \cdot \sum V(s_i)}$

where $V \left(s\right)$ counts the non-zero components of $s$.


texts: Is it possible for a [futuristic] computer to contain the information of the whole universe?

texts:
(This is a question of information theory, data compression and entropy, so I believe it fits CS forum)

Does the fact that the computer itself is a part of the universe make it logically impossible for the computer to contain the information of the whole universe?

I want to know if it's possible to simulate the whole universe on a computer. This question is motivated by the hypothesis that we live in a simulation. If the answer to the question is negative, it means that a simulated universe inside another universe necessarily contains less information, so it's a smaller or less detailed universe.

Edit:

By the "information of the whole universe" I mean the position and state of all the elementary particles in the universe.

By the "contained in a computer" I mean the information of the whole universe must be retrievable from the computer by a human (or a transcendent form of conscious mind).


texts: Can a 32-bit processor work with a 64-bit size word?

texts:
In a 32-bit byte addressable memory system, each "row" has 4 bytes and each byte has a 32-bit address.

My question is: can I read and/or write word of length 64 bits from/to memory?
In other terms, can my word length be 8 bytes long or is the maximum number of bytes/word 4?


texts:
need some help with the following question:

I've watched a few youtube tutorials but I'm struggling to convert this specific CFG


texts: Up to what extent the hypothesis of piece wise constant intensity values is valid in ocean images?

texts:
Usually, in MR images one hypothesis research communities are making is,
" the spatial intensity distribution is
piecewise constant and that each tissue corresponds to a
unique grayscale level. Based on that hypothesis, a valid
correction method should lessen the standard deviation in
intensity for each tissue."(Paper below)

Belaroussi, B., Milles, J., Carme, S., Zhu, Y. M., & Benoit-Cattin, H. (2006). Intensity non-uniformity correction in MRI: existing methods and their validation. Medical Image Analysis, 10(2), 234-246.

Now, in case of underwater images, is THIS hypothesis valid considering the fact that artificial lighting conditions, ocean floors and objects as well as object colours may vary in any two subsequent frames?

What about the in-class variances, before and after the correction of bias/illumination?

Image courtesy: Woods and Hole Oceanographic Institute

For more images: habcam.whoi.edu/gallery/


texts: Are $A$ and $B$ necessarily be decidable if $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable and $A$ & $B$ being exhaustive?

texts:
I found the following question

  Suppose A and B are recursively enumerable languages such that $A∪B=Σ^∗$. Further, suppose $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable. Which of the following is true?
  A- It is possible that either A or B is decidable but not both
  B- None of them can be decidable
  C- Both of them are regular
  D- Both of them are decidable

My attempt: It is possible for $A$ & $B$ to be mutually exclusive and yet be exhaustive. Now this can happen even when one of them is not decidable. So $A$.

But answer given id $D$. Are my arguments flawed? If yes, how and where?

The source of the question is reputable test series, but still there are chances of it being wrong.


texts: Use of Myhill-Nerode Theorem to prove minimal number of states

texts:
I'm confused about how we can use the Myhill-Nerode Theorem to solve this problem, some pointers would be very helpful

Let $Σ = {\{a, b}\}$ and $C_k=Σ^*aΣ^{k-1}$

Prove that for each k, no DFA can recognize $C_k$ with fewer than $2^k$ states.


texts: Which has optimum performance? raw core or multithreaded

texts:
Let's say there's a single process performed in the machine which utilizes all available processors (whether physical or logical processors). The process use 100% processor utilization most of the time on all processors.
Which machine will perform better?

Machine with 2 cores, 1 thread per core (2 physical processors); or the
Machine with 2 cores, 2 threads per core (4 logical processors)

This is assuming everything (memory, clock speed, etc) is the same and the only thing that differ is the number of threads.
My initial thoughts would be that the former -- machine with 2 raw cores (1 thread) -- will perform better because it doesn't have context switching. Whereas the latter would have overhead on the context switching.
Which machine will perform better?


texts:
I'm looking for social community dataset.
There must be info about two social communities (two classes for classification), there one row is info about one person (age, sex, etc.). For example, info about university students and info about pupils from the same school.
What else: there must be enough columns, that can have only 0 or 1 value (or T/F, or something like this) - as much as possible.
Size of dataset is irrelevant, but I think I need more than 10000 rows (but not necessary). Maybe you know something like this or maybe how to google it? Thanks!


texts: 1-serializability theorem in database theory

texts:
In the paper "MVCC@TODS'1983 by Bernstein et al.", 1-serializability ($1$-$\text{SR}$) problem is defined as a decision problem:

  To decide whether an MV (multi-version) log $L$ is $1$-$\text{SR}$.

where,

  An MV (multi-version) log $L$ is $1$-$\text{SR}$ iff there exists a version order $\ll$ such that MVSG($L,\ll$) is acyclic.

I did not get the points of the following comment in page 475:

  Our problem corresponds to choosing versions at the same time as scheduling the operations.

How to understand this comment? Has not the schedule been fixed once an MV log $L$ is given? Are the terms "choosing" and "scheduling" related to implementations?


texts: Algorithm to find shortest path between two nodes

texts:
I want an algorithm similar to Dijkstra or Bellman-Ford for finding the shortest path between two nodes in a directed graph, but with an additional constraint.

The additional constraint is that there are $N$ sets of special edges with weight $0$ such that a path is not considered valid if it traverses one edge in a set but not the remaining edges in that set.

Note that these $N$ sets of edges are disjoint such that no edge belongs to more than one of the $N$ sets. The number of edges in each set is around 3 to 6. And there are a large number of these sets. About $50\%$ of edges belong to a set, the rest don't belong to a set and can be traversed normally.

Does such an algorithm exist? Can such an algorithm exist that is better than brute force?


texts: How to reduce MAX-2SAT problem to finding a cut in a graph

texts:
I'm trying to reduce the MAX-2SAT problem to finding a cut in a graph, with no luck so far.
Let me first show a description of the problem:
2SAT: Given a boolean formula $\varphi$ in a CNF form, where every clause has 2 literals (a variable or its negation), one should decide whether there is an assignment that will satisfy $\varphi$.
The 2SAT problem is in $P$.

MAX-2SAT: Given a boolean formula $\varphi$ in a CNF form, where every clause has 2 literals, and $k\in \mathbb{N}$, one should decide if there is an assignment that will satisfy at least $k$ clauses in $\varphi$.
This is an $NPC$ problem, and I'm trying to reduce it to finding the maximum cut in a graph:
MAX-CUT: Given $(G=(V,E), w, k)$, where $G$ is an undirected graph, $w$ is a weight function; $w: E\rightarrow \mathbb{N}$ and $k\in\mathbb{N}$, one should decide whether there exist a cut $(V_1,V_2)$, s.t its weight is at least $k$, meaning $k\leq \sum _{u\in V_1, v\in V_2}w(u,v)$.

I tried some obvious constructions that didn't work, like setting:
$G=(V,E)$
$V=\left \{ v_x|x\text{ is a literal in } \varphi \right \}$
$E=\left \{(v_x,u_z)|\text{ There exist a clause } x\vee z \text{ in } \varphi\right \}$
and finally setting $w(e)=1$  $\forall e\in E$

This obviously didn't work, since having $k$ satisfied clauses in $\varphi$ does not imply a $k$-weighted cut in $G$.
(If the above can be improved to achieve the desired reduction, I would love to get some guidance)
I looked around online, and found that it is possible to construct an "implication graph" from $\varphi$, where every clause $(x\vee z)$ in $\varphi$ is translated to the equivalent logical expressions: $\bar{x}\Rightarrow z$ and $\bar{z}\Rightarrow x$, and these, in turn, are translated to vertices $\bar{x}, z, \bar{z}, x$, and directed edges $\bar{x}\rightarrow z$ and $\bar{z}\rightarrow x$, but I just can't see how that helps, since, again, $k$ satisfied clauses in $\varphi$ does not imply $k$-weighted cut in $G$.
Any help would be greatly appreciated.


texts:
This question has been asked in the theoretical community, but deemed as too practical. I am moving it here, I hope it is on-topic.

I'd like to know more about real performances of data structures, in particular two families attract my interests:

hash tables
cache oblivious

My researches didn't find any "comprehensive" (let me use this adjective) book or article that describes the advantages and disadvantages of these two families. I have found the Intel's paper from this question, but it doesn't compare the two.

When is a hash table more performant than a cache oblivious data structure? What are the real use cases for a hash table, when is a cache oblivious B-tree (or simply binary) preferable?

The questions I'm asking are related not only on theoretical results, but also on real results on real computers.

I've read the book "Handbook of Data Structures and Applications", but it contains only theoretical limits, and it is not sufficient to me: I need to evaluate which data structures to implement on a real system.

Thanks for any pointers!


texts: Do functional algorithms require more memory than imperative algorithms?

texts:
Let's suppose we are counting words in string. We split it so what we have is an array of strings. I'll use Python as an example.

The imperative approach would as follows:

wordcount = {}
for word in words:
    wordcount[word] += 1

The functional would be:

uniquewords = set(words)
wordcount = [words.count(w) for w in words]

For each word w we are doing a full scan on the words array, while the imperative approach goes over each word just once. Am I right to suppose that the functional way of doing it will consume a lot more resources than the imperative one?


texts: Time complexity for searching $k-th$ element from starting and ending of a linked list

texts:
What are the time complexities of finding $8th$ element from beginning and $8th$ element from end in a singly linked list? Let $n$ be the number of nodes in linked list, you may assume that $n > 8$.

The answer is given as $O(1)$ and $O(n)$.
What I learnt till now is that searching operation in linked lists takes linear time since it doesn't have indexes like arrays. Then why does searching the $8th$ element would take constant time?
Further explanation for the answer is as follows :

  Finding 8th element from beginning requires 8 nodes to be traversed which takes constant time. Finding 8th from end requires the complete list to be traversed.

Can someone explain me the concept behind this?


texts:
Yes this is a homework problem, but I only need help setting it up, there are 7 parts to the question once I set it up:

  We want to build a function Y = 2X + 3 where X denotes a 3-bit
  unsigned value(x2x1x0) and Y = y4..y0 is a 5-bit value in hardware.
  Contruct its truth table where input bits are x2, x1, and x0 and
  output bits are y4 through y0.

The homework problem then asks for a bunch of other things which I can get. I just don't understand the question, how do you create a truth table based on a function and these input bits?

Should the truth table look something like this?

x2 x1 x0 y4 y3 y2 y1 y0
0  0  0  0  0  0  1  1
0  0  1  0  0  1  0  1
0  1  0  0  0  1  0  1
0  1  1  0  0  1  1  1
1  0  0  0  1  0  1  1
1  0  1  0  1  1  0  1
1  1  0  0  1  1  1  1
1  1  1  1  0  0  0  1


texts: Building segment tree to find minimum suffix sum in range

texts:
Let's say we have array $A$ of $N$ integers, each of them in the range $[-1, 1]$. We define an array $B$ of $N+1$ integers, such that $$B_{N+1} = 0, \\B_i = A_i + A_{i+1} + A_{i+2} + \dots + A_{N}= A_i + B_{i+1}$$

So now we want to build data structure over the array $B$ such that it will be possible to perform two types of queries:

1.Update single element in array $A$, again in the range $[-1, 1]$, note that this update will also change array $B$.

2.For given $L$ and $R$ for each $i$ in $[L, R]$ find $\min B_i$.

I think that this can be solved with segment tree, but I'm trying to simplify the implementation, as it looks pretty complex.


texts:
I'm writing insertion sort in scheme, but due to the difficulty of writing it recursively within the constraints of list processing of scheme, I made what seems like an insignificant change to the "find lowest" or inner loop.

I'll reproduce the algorithm here in Python (aka the universal psuedocode) to explain. I'll also use iteration so it's easier to understand.

def insertion_sort(list):
  for i in range(len(list)):
    for j in range(i + 1, len(list)):
      if list[j] < list[j]:
        list[i], list[j] = list[j], list[i]

The difference is that I repeatedly swap the old lowest with new lowest numbers as they're found, and reinsert the old lowest back into the list where the new lowest was.

Can I still (correctly) refer to this as insertion sort and is there a significant effect on efficiency?

Also, just in case there's anyone here who loves scheme:

(define lowest-to-front-helper
  (lambda (list lowest)
    (if (eq? (cdr list) '())
        (if (>= (car list) lowest)
            (cons lowest list)
            (cons (car list)
                  (cons lowest '())))
        (if (< (car list) lowest)
            (let ((temp (lowest-to-front-helper (cons lowest (cdr list)) (car list))))
              (cons (car temp)
                    (cdr temp)))
            (let ((temp (lowest-to-front-helper (cdr list) lowest)))
              (cons (car temp)
                    (cons (car list) (cdr temp))))))))

; Permutes list such that the lowest element is moved to the front. (Non-stable.)
(define lowest-to-front
  (lambda (list)
    (lowest-to-front-helper (cdr list) (car list))))

(define insertion-sort
  (lambda (list)
    (if (eq? (cdr list) '())
        list
        (let ((temp (lowest-to-front list)))
          (cons (car temp) (insertion-sort (cdr temp)))))))


texts: If we come to the situation when we have to insert again the original key into the original table, I believe we have found a cycle. Is there a way to prove this?


texts: What algorithm does OLA and UBER use for allotting taxis

texts:
More specifically :
lets say i have 5 taxis , each available for booking at t=0; i have two days (48 hrs) with me how can I maximise their booking . I may not be able to clarify the question , this was some interview question but the context is how to schedule the taxis for max profit. I gave a algo to run at t=0 but interviewer asked for a dynamic solution a solution that runs every time . I dont know how to do that any which topic of Computer Science deals with such problems .


texts:
Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ entries.

The original question was to count the number of islands in a given matrix. The author described a recursive solution ($\mathcal{O}(nm)$ memory).

But I was unsuccessfully trying to find a streaming (left to right, and then down to the next row) solution that dynamically counts islands with $\mathcal{O}(m)$ or $\mathcal{O}(n)$ or $\mathcal{O}(n+m)$ memory (there are no limits for the time complexity). Is that possible? If not, how can I prove it?

A few examples of expected outputs for certain inputs for the count function:

$
count\begin{pmatrix}
010\\
111\\
010\\
\end{pmatrix} = 1; %
count\begin{pmatrix}
101\\
010\\
101\\
\end{pmatrix} = 5; %
count\begin{pmatrix}
111\\
101\\
111\\
\end{pmatrix} = 1;
$

$
count\begin{pmatrix}
1111100\\
1000101\\
1010001\\
1011111\\
\end{pmatrix} = 2$

$
count\begin{pmatrix}
101\\
111\\
\end{pmatrix} = 1$


texts: is it correct to compute the average case time complexity of an algorithm by taking the mean of the best and worst cases ? My findings : for binary search, $\frac{\log (n) +1}{2}\in \Theta \left(\log (n )\right)\implies $ the average case is $\log (n).$


texts: Converse of pumping lemma for regular expressions

texts:
I want to come up with a language that satisfies the pumping lemma while not being a regular expression.

I thought of $\{0^i1^j: i > j > 0\} $. The pumping seems to work just fine, and this is not a regular expression, as  it would not be possible to create an automata that recognizes it. This last part is where I'm having a bit of trouble, as I think I have the right idea, but can't formalize it. This language is just a regular expression $\big(\{0^i : i \in \mathbb{N}\}\big)$ concatenated with something that is not a regular expression $\big(\{0^i1^i: i \in \mathbb{N}\}\big)$.

Is my thought process correct? Can this be generalized? If $L$ is a RE and $L'$ is not, then $LL'$ is also not a RE? I believe so, because we know that if $L$ is a RE then so is $L^r$. And so we end up with  $(L')^rL^r$, and we can use the contrapositive of the pumping lemma to prove this language is not regular. Any insight would be helpful!


texts: Combine the following IP Addresses into a single block

texts:
I was asked to combine the ip addresses into a single block:
16.27.24.0/26, 16.27.24.64/26, 16.27.24.128/25

I managed to convert the given ip addresses into binary:
00010000.00011011.00011000.00000000 | 00011010
00010000.00011011.00011000.01000000 | 00011010
00010000.00011011.00011000.10000000 | 00011001

I am not quite sure what needs to be done in order to convert it properly.
I believe that in this link it is explained what is supposed to be done. I should do it the way it is explained there. I am not able to access it, but whatever is shown in the preview, that is probably the way it would be gone about. Please help. Thanks


texts: Expression of the weakest precondition of a while loop

texts:
I am interested in computing weakest preconditions (WP) of loops.

If I refer to Wikipedia "Predicate Transformer semantics", the WP for e.g. total correction of a loop annotated with an invariant I is (as discussed here):

WP(while E do S done, R) =
    (1) I
AND (2) for all y, ((E /\ I) => WP(S,I /\ x<y))[y/x]
AND (3) for all y, ((not E /\ I) => R)[y/x]

I understand that it is not easy to get automatically the WP without annotating with an invariant, but how do we know that it is the weakest possible precondition ? Also, is it really impossible, by using different invariants, to get different preconditions with this definition?

In another textbook, I have the following definition:

WP(while E do S done, R) = I
if we can prove separately:
(1) (E /\ I /\ V=n) => WP(S, I /\ V<n)
(2) I => V>=0
(3) (not E /\ I) => R

Are these definitions equivalent?
In this definition, and if we prove the conditions 1-3 separately, is I really the weakest precondition, or a stronger approximate of the true WP?
It looks at first sight that this rule is easier to understand because there is no 1st order in the precondition, but how is it different?

I guess the question behind all this would be : given a simple example of code with a loop, what would be the easiest way to compute the weakest precondition?


texts:
I have to sketch an IP proof for the minSAT problem. The minSAT problem is define in this way:

For a given formulae find a satisfying assignment with a min subset of variables assigned to True;

My sketched IP protocol is:

Prover and Verifier share the input formula
Prover sends to the Verifier a set of variables assigned to True, which should be the minimum
Verifier checks if the given set indeed satisfies the formula. If it is the case, it chooses one variable, re-computes the formula and sends the new formula to the Prover

I would iterate this process untill the Prover gives an empty set or I reach a contradiction.

My questions are:

Is this a right protocol? If not, how can I exploit the cases in which the protocol doesn't work?
How can I evaluate the probability of completness and soundness for this protocol?


texts: Binomial coefficient to approach multi-way choices DP problem?

texts:
I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book. Not homework: i've already a solution, just considering if i'm ok with the theory.

  Suppose we want to replicate a file over a collection of $n$ servers $S_1, S_2
, \ldots , S_n$. Each server $S_i$ has a placement cost $c_i$ to place a copy of the file at $S_i$. If a user requests the file from $S_i$ and no copy is present, then servers $S_{i+1}, S_{i+2}, S_{i+3}, \ldots$ are searched in order until a copy is found, say at $S_j$ (where $j > i$). This results in an access cost $a_i$, where
  $$
a_i=
\begin{cases}
j-i \qquad \hbox{if $S_i$ does not contain a copy the file} \\
0 \qquad \hbox{ if $S_i$ contains a copy of the file}
\end{cases}
$$
  We require that $S_n$ contains the file, so that all searches will terminate.
  Given $I \subset \left\{1,\ldots, n − 1\right\}$, a subset of servers to place the file on, we define the total cost

  $$
c(I) = c_n + \sum_{i \in I} c_i + \sum_{i=1}^{n} a_i
$$

  To be the sum of the placement costs for each server that contains the file (recall that $S_n$ must contain the file), plus the sum of the access costs associated with all $n$ servers. Design a polynomial-time algorithm to compute a subset I of servers to contain the file that minimizes total cost.

My approach is to consider every possible choice, like for other problems e.g. segmented least squares, ending up with a $O(n^4)$ running time algorithm.

Anyway it looks like there is a better solution, given by the following recurrence:

$$
OPT(j) = c_j + \displaystyle\min_{0 \leq i < j}(OPT(i)+\binom{j-i}{2})
$$

With the initialitazions $OPT(0)= 0$ and $\binom{1}{2}=0$. The answer is given as usual by $OPT(n)$. This is to me very counterintuitive: why the binomial coefficient, and why the number $2$?.

Is it a standard way to approach similar problems?


texts: Is a set $B = \{y, \exists x \in A, f(x)=y\}$ recursive if A is a recursive set and f is a $N->N$ total computable function?

texts: Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I cannot find a proof (or counter-proof) that you can invert TCFs this way. AFAIK, all injective functions are invertible, but can we also invert a non-injective function and compute all the possible inputs that would result in the desired output?


texts: Is it possible to ever define $L(M)$ of a given Turing Machine, $M$?

texts:
In class, we were discussing creating a Turing Machine $M$ based on the set of input strings it should accept, i.e. define a Turing Machine that accepts only the input $\{ w\ \#\ w\ |\ w \in \{0,1\}^*\}$. However, we proceeded to discuss when a language is recursively enumerable vs machines that are deciders etc, and then started discussing the halting problem.

My question is : given a Turing Machine $M$, is it undecidable to construct its Language $L(M)$, since theoretically there could be an input that never reaches a reject or accept state? (My intuition tells me this reduces to the halting problem).

EDIT

If we accept the definition $L(M)$ as the set of all strings a given Turing Machine $M$ can accept, when I ask can we construct it, in the simplest way I suppose I mean can we list all of the input strings $M$ accepts (see @d'alar'cop's comment)?


texts:
Given a group $G$, the sumset of two sets $A,B$ is denoted as $A+B = \{a+b:a\in A,b\in B\}$. We have that $A+B$ has no multiplicities if $|A+B| = |A||B|$. For practically, let's say $G$ is integer addition modulo $N$.

We define an exact cover-eqsque problem. We let $[N] = \{0,1\dots N-1\}$.

Input: a set, $S$ of subsets of $[N]$

Output: a map $\phi: S \to 2^{[N]}$, such that $\bigcup_{A \in S}A+\phi(A) = [N]$, and $\sum_{A\in S} |A||\phi(A)| = N$

Can we show that this problem is NP-complete in terms of the parameter $N$?


texts: What happens if we expand the alphabet of a given Turing Machine?

texts: If we expanded the alphabet Sigma = { 0, 1, u, > } to Sigma' = { 0, 1, 2, u, > }.    How would the table change?     We're just learning about Turing Machines in class and I'm a bit confused. Is the table in the picture calculated in some way?


texts: Why is this verifier for primality wrong?

texts:
We are provided with the following verifier of primality:

Verifier for prime

Input: integer n ≥ 1
       integer d

if 1 < d < n and d divides exactly n then
    return ’no’
else
    return ’yes’

But the answer is that it is wrong:

  Note that in order to be a verifier it is required that for every n, n
  is a positive instance (that is, n is a prime) if and only if there
  exists one d such that the verifier with input n and d returns ’yes’.
  However, in the algorithm for Primes we have that n is a negative
  instance if and only if there exists one d such that the verifier with
  input n and d returns ’no’.

But I do not understand this answer or why "in order to be a verifier it is required that for every n, n is a positive instance (that is, n is a prime) if and only if there exists one d such that the verifier with input n and d returns ’yes’"


texts: Correctness of asymptotic expression from exact expression

texts:
I have the expression:
\begin{equation}
  |Q|f(n)|\Gamma|^{f(n)}
\end{equation}

Here is my solution to convert the above into an asymptotic expression:
$|Q| = 2^l$ for some $l\in\mathbb{R}$
$|\Gamma| = 2^k$ for some $k\in\mathbb{R}$

Therefore we have $2^lf(n)(2^k)^{f(n)} = f(n)2^{kf(n)+l} = f(n)2^{O(f(n))}$

Is this correct? I just want to verify my understanding of a discussion in Sipser's Theory of Computation text.


texts: Transform Image Point to Azimuth and Elevation

texts:
I'm working on an object tracker where I need to report the azimuth and elevation of targets. Both values should be scaled from degrees to unsigned 32-bit integers. For now I can ignore lens distortion, assume Z=0, and make an arbitrary North (the center of the image?).

The images are single frames taken at 60fps. I don't know the size of the object a priori, but I can assume that each pixel occupies a known fixed size because I really don't care about Z at this point.

Once I have the image coordinates how to I transform them to azimuth and elevation?


texts: Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?

texts:
$L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $

Is this language a context free language?
If yes give a PDA. If no, give a proof.

The pumping lemma for context free languages doesn't seem to work here.

Let $p>1$ be the pumping length. Let the string be divided into five parts according to pumping lemma as $w = uvxyz$.

For any string of the form $a^ib^j \ s.t.$:

$ j\lt i-1$ choose $v=a, \ x=\epsilon, \ y=\epsilon$
$ j\gt 2i+1$ choose $v=\epsilon, \ x=\epsilon, \ y=b$
$ j = i-1$ choose $v=a, \ x=\epsilon, \ y=b$
$ j =  2i+1$ choose $v=a, \ x=\epsilon, \ y=b$
$ j\gt i,\ j\lt 2i $ choose $v=a, \ x=\epsilon, \ y=b$


texts: Can we always transform a set of lines to a function?

texts:
If I have n lines in a programming language like Python (globally or inside a function):
..
..
# from here
..
..
..
..
# to here
..
..

or
def example():
    ...
    ...
    # from here
    ...
    ...
    ...
    ...
    # to here
    ...
    ...

can I always transform it to a function of the form s1, s2, s3 … = function(s1, s2, s3 ...), where:

s1, s2, and s3 etc are the local/global variables created/updated after the n lines gets executed.
function is almost the same code as the n lines above except it collects them and returns them?

As an example, in the below function:
def example():
    ...
    ...
    # from here
    ...
    ...
    a = 'c'
    b = 'd'
    ...
    ...
    # to here
    ...
    ...

I know I can do this:
def example():
    ...
    ...
    a, b = transform('a', 'b')
    ...
    ...

But my question is if I can extend this idea to any arbitrary n lines of code, abstracting them as an input-output block?
According to me, the only thing that happens after any n lines is executed, is a state change (as far as the program is concerned) - which can always be represented as a function with an input and output.
Am I missing something? Can someone please clarify?


texts: An algorithm to efficiently insert a list of elements into a binary heap ("bulk insertion")

texts: I wonder if there is any elegant algorithm for inserting a list of elements into a binary heap (at once) whose performance would be close to that of inserting elements one by one when there are only a few elements to insert, and which would still run in linear time in the worst case (when there is a lot of elements to insert).


texts: Are there any dynamic programming algorithms that combine solutions to sub-problems in a more 'dynamic' way?

texts: First of all, I now know that 'dynamic' has nothing to do with the dynamism of a dynamic programming algorithm. But I didn't before I studied them, and I was kind of disappointed that they all seem to rely on a pretty basic recursion. Are there any problems with more interesting optimal substructures?


texts: Constant folding vs. Constant propogation

texts: What is the difference between constant folding and constant propogation? They both seem to do the same thing, instead of saving constants into stack or evaluating a full arithmetic expression, they simply replace it with the result which can be obtained at compile time. What is the difference between two?


texts: Proving a language is regular or non-regular

texts:
I'm struggling a bit to understand two of the problems we were given in class. Could someone look over my work and maybe give me a few hints?

State whether the following languages are regular or not and prove your answer.
$$\{0^n1^m \mid m \geq 0 \text{ and } n = 2m+1\}$$
$$\{0^a1^b0^c \mid 0 \leq a \leq b \leq c \leq 100\}$$

The first one appears to me as non-regular as $m$ is not finite. Then to prove that it is not regular, I used the pumping lemma method with $0^P1^\frac{P-1}{2}$ as the string.

For the second language, I'm not really sure if it is regular or not. I can't come up with a DFA/NFA/RegExp for it nor can I figure out how to apply the pumping lemma method to it. Is it safe to use $0^P1^P0^P$ as the string and say that if $Y$ where $Y = 0^k, 1 \leq k \leq P$ is appears more than once (i.e. $XYYZ$), the resulting string is not in the language and thus the language is not regular?

Edit: I'm sorry if this question seems elementary. I've already read through most of the posts pertaining to this topic and some things were unclear to me. I was asking for someone to look over my work and make sure I followed the correct procedures. For instance, I'm still confused on the second question. The pumping lemma I used makes it seem like it is not regular but at the same time it is finite. Does that mean I used pumping lemma incorrectly? In what way did I use it incorrectly?


texts:
Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

What complexity class does this correspond to?

Related questions:

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? NL-complete?

What complexity class is this set of grammars? In between NL and P?

What complexity class is this set of grammars? RE?


texts:
I've learnt about complexity classes but my knowledge doesn't seem to help much when I am given a problem and need to decide it's complexity.

Here is the problem at hand:
A set of weights with the same dimensions but with different densities have to be ordered on a plank (on a straight line). The length of the plank is not enough to put everything in one line so you'd have to stack weights on top of each other. There are $n$ weights and there's space only for $m$, $m<n$ weights on the plank. The weight of each object is given.

The target is to stack weights such that the weights are spread across the plank as smoothly as possible. The following figure shows a sample (possible) solution for n=11 weights each having weight w1 to w11 and m=5.

The smoothness of the weight distribution is calculated by finding the average of all weights and summing up the deviation from this value at each spot.

Now definitely this is a combinatorial problem. And it is definitely a 'yes' 'no' answerable problem.

It seems to me that it's not in NP. Because given a solution, there is no way of saying in polynomial time that it's the correct answer. Is this right?

If so, does that mean it is in NP hard?

How can I really find which class it belongs to.

I'd appreciate it if anybody could help me with this problem.


texts: How to solve a recurrence relation with a sum?

texts:
How do I solve the following recurrence relation?

  $$
T(n) = 1 + \sum_{j=0}^{n-1} T(j).
$$

I thought of solving it by generating its recursion tree. I found that the height of the tree would be equal to $n$ but wasn't able to find the cost of each level.


texts: The throughput of the ALOHA protocol if the Binomial distribution was used

texts:
In all the examples of ALOHA I've seen, the Poisson distribution is used. Theoretically, how could the throughput be calculated if a Binomial distribution was used instead?

For example, in the case that the offered load follows a Binomial distribution with probability $p$, I know that the probability of $k$ attempts within $t$ time slots is as follows:

$$\Pr\big[k \text{ attempts within $t$ time slots}\big] = \binom{t}{k}p^k(1-p)^{t-k}\,.$$

I know that the throughput, $S$ is equivalent to $G$ (average offered load) multiplied by the probability of success:

$$S = G\cdot\Pr\big[\text{successful}\big]\,,$$

but what would this be in the case that a binomial distribution is used?


texts: Confusion about big-O notation comparison of two functions

texts:
On page 16 of this algorithms book, it states:

  For example, suppose we are choosing between two algorithms for a particular computational task. One takes $f_1(n) = n^2$ steps, while the other takes $f_2(n) = 2n + 20$ steps (Figure 0.2).

He then goes on to say:

  This superiority ... (of $f_2$ over $f_1$) ... is captured by the big-O notation: $f_2 = O(f_1)$, because ...

Now my problem is that in the original quote, he said that $f_1(n) = n^2$ steps and $f_2(n) = 2n+20$ steps, so thus $f_1 = O(n^2)$ and $f_2 = O(n)$ (big-O is defined in Section 0.3). But the second quote above states $f_2 = O(f_1)$, which means $f_2 = O(n^2)$ and contradicts his definition of big-O notation. What have I missed?


texts: Context sensitive language is context free

texts:
Problem of determining whether a context sensitive language is context free is undecidable.

How to prove it


texts: Appropriate optimization algorithm for constraints having NaN values

texts:
I am trying to solve a problem where some of the constraints have NaN values. Which algorithm can be used to handle this kind of problem.
In my example I have 3 nonlinear inequality constraints,
C(1)<=  0
C(2)<= 0
C(3)<= 0
If C(1) is not satisfied, C(2) and C(3) will have NaN value.


texts: Is there a formalization of a general version of the sweep line algorithm? If not is it easy to derive?

texts:
A well known algorithm in computational geometry is the sweep plane algorithm. I've been trying to find if there's a general version of the sweep plane algorithm  in $\mathbb{R}^n$, I don't need to implement it but I need to study how the general version would work.

If there's nothing you known in literature, how difficult is trying to formalize it?

I believe it could be formalized recursively (like sweeping hyper planes from dimension $n-1$ downto $2$. But I need to be sure.

Update:

I've been asked to elaborate a bit more...

In the best reference I know, the plane sweep is basically explained as "Imagine this plane that moves through event points, where something happens". The specific instance are almost 2D and 3D cases (involving problem like segments intersection, triangulation and voronoi diagrams), nothing is mentioned how the paradigm works in general.


texts: Length of an Edit Script and the Number of Deletions

texts:
I am reading the 1989 paper called "An O(NP) Sequence Comparison Algorithm" by Wu, Manber, Myers, and Miller.  The algorithm sounds like a good fit for a project I'm doing at work.  I have found some implementations in my target language that I could reuse, but I want to make sure that I understand the algorithm (and the code) because it is so crucial to my project.

I am a ways into the paper, and seem to be understanding it, but there's something important in the abstract that still doesn't make sense to me.  This is the relevant portion:

  Let $A$ and $B$ be two sequences of length $M$ and $N$ respectively, where without loss of generality $N \ge M$, and let $D$ be the length of a shortest edit script between them.  A parameter related to $D$ is the number of deletions in such a script, $P = D/2 - (N - M)/2$. We present an algorithm...

This relationship between $P$, $D$, $N$, and $M$ is not proven in the paper.  And when a try using it with a simple example (turning "xy" into "x", for instance), I get a nonsensical answer.  Can someone please explain the relationship?


texts: How exactly does a Max 2 Sat reduce to a 3 Sat?

texts:
I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after ci is satisfied, 7 out of 10 clauses are satisfied and if it is not satisfied, the 6 out of 10 clauses are satisfied.

Can someone explain to me in simple terms, and demystify what exactly the article wants to convey? Essentially, I have come to know that a max-2-sat problem is the same as a 3 sat problem. The question is I'm not able to understand why.

More formally, I wish to solve this problem:

  Consider the problem MAX2SAT described as follows.
  Given a 2-CNF (Conjunctive Normal Form) Boolean expression  (with m
  clauses, n variables) and an integer k, Decide if there is an
  assignment satisfying at least ‘k’ of the total clauses? Compute the
  complexity class (P or NP or NP Complete) of the MAX2SAT with
  justification.


texts: How do web browsers find out the MAC address?

texts:
While reading through my textbook, I discovered that if you want to access a particular web page, your web browser will find out the IP address of the web server that hosts the web page and try and connect to it. It will then transfer a copy of the web page to your computer so that you may view it.

However, my concern is... I have discovered that the IP address enables data to be sent to the device's local area network, but in order for the data to be sent to the device itself, the MAC address is needed to transfer data from the local area network to the device.

BUT, in my textbook, nowhere does it say how the computer's web browser finds out the MAC address of the web server. It says that the computer finds out the IP address of the web server by using the Domain Name System (DNS).

So, how does the computer find out the MAC address of the server?

Answers would be much appreciated.


texts: Question about NP problem certificates and P=NP

texts:
From my understanding a problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate.

My question is whether or not creating an algorithm to determine values accepted by a certificate for an NP problem can itself be considered an NP problem.

This problem is an example of what I had in mind (it's more or less a variation of SAT).

Imagine a padlock with N switches and each switch has a configuration 'UP' or 'DOWN'. The padlock can have anywhere between 1 and $2^N$ solutions (i.e. it may only accept one combination or any number of combinations up to and including all possible combinations) and both the total number of solutions and the solutions themselves are selected at random.

If there are $2^N$ solutions a solution takes $O(1)$ time to find since all inputs are valid.

However, if there is only 1 solution $O(2^N)$ time is required to find it.

If it is accepted that trying all combinations on the padlock requires $2^N$ combinations and that because the solution is random there is no way to guarantee a solution unless $2^N - 1$ combinations are tested by process of elimination.

Because the total number of acceptable solutions is not known until different candidates are tested against the certificate, the problem requires $O(2^N)$ time to solve.

To prove that the problem is solvable in NP, use an NTM to solve the problem by non-deterministically testing all valid combinations and accepting any valid solution. Takes $O(N)$ time to solve since every differing possible bit to test will branch into a new non-deterministic chain.

The certificate for the problem contains acceptable values for each 'swicth' (bit) at each location either 1 for 'UP', 0 for 'DOWN' or 'X' to accept any value at that location and takes $O(N)$ time to verify.

Is this valid?

If I'm correct and the problem above does fit in the class of NP it seems sufficient to prove that $P \neq NP$ but I'm fairly confident I made an error I'm not aware of and I'm not sure if my example can be properly classed as an NP problem.


texts: Which queue does the long-term scheduler maintain?

texts:
There are different queues of processes (in an operating system):

Job Queue: Each new process goes into the job queue. Processes in the job queue reside on mass storage and await the allocation of main memory.

Ready Queue: The set of all processes that are in main memory and are waiting for CPU time is kept in the ready queue.

Waiting (Device) Queues: The set of processes waiting for allocation of certain I/O devices is kept in the waiting (device) queue.

The short-term scheduler (also known as CPU scheduling) selects a process from the ready queue and yields control of the CPU to the process.

In my lecture notes the long-term scheduler is partly described as maintaining a queue of new processes waiting to be admitted into the system.

What is the name of the queue the long-term scheduler maintains? When it admits a process to the system is the process placed in the ready queue?


texts:
I'm trying to hash integers n = 4k(0,4,8,12,16...) into an array of linked lists of size 4 (chaining).
What is a good hasing function that guarantees a good distribution of the keys? that means to use all indexes of the array from 0 to 3.


texts: Is infinitely fast computer fundamentally impossible even theoretically?

texts:
This may get slightly philosophical, but consider the following program:

bool lampState = false;
TimeSpan timeout = 1;
while (true)
{
    lampState = !lampState;
    Thread.Sleep(timeout);
    timeout = timeout / 2;
}

DotNet Fiddle link for C# code

This is obviously an implementation of Thomsons lamp in C#.

So the question is what is the value of lampState after 2 seconds of execution?

Lets assume that no physical law prevents us from constructing an infinitely fast computer. Static code analysis shows that we will never exit the while loop. Does this mean that we can have an algorithm that is arbitrary fast, but not infinitely fast, not even theoretically (because we run in to a contradiction?


texts:
Let < M > be an encoding of a Turing machine.

L = { < M > | M is a Turing machine that accepts a string of length 2014 }

Above language is R.E(even though we have infinite TM's) as we have finite amount of strings of length 2014 and we can apply dovetailing method.

My doubt is can we apply dovetailing if we have infinite number of strings and infinite number of Turing machines ?


texts: How many rotations after AVL insertion and deletion

texts:
Is it true that inserting an element to an AVL tree requires $O(1)$ rotations?

How many rotations, does deletion from AVL require?

I've searched for these two questions with no luck so far.


texts:
While reading about interrupt mechanism, I understood that there is an IRQ signal line on the bus by which an I/O interface
raise an interrupt request.
There is an INTA signal line using which the processor indicates acceptance of to the interrupt request.The processor interrupts the program currently under execution, saves the current PC & PS in the stack and transfers control to the ISR meant for the I/O device concerned.
After completion of execution of the ISR the processor restores the saves PC & PS so as to resume execution of the interrupted program.
But can anyone help me to understand in depth about the mechanism for interrupt enabling and disabling.


texts:
Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort log n times. mergeRoutine is a tail call, and it doesn't add to the call stack.

The extra space I need equals to n + log n. How can the extra space be O(n)?

I think we just consider log n negligible.

public class MergeSort {

    private int[] array;
    private int[] helper;

    public MergeSort() {
        this.array = array;
        this.helper = new int[array.length];
    }

    public void sort() {
        sort(0, array.length - 1);
    }

    private void sort(int start, int end) {
        if (end > start) {
            int middle = (start + end) / 2;
            sort(start, middle);
            sort(middle + 1, end);
            mergeRoutine(start, middle, end);
        }
    }

    private void mergeRoutine(int start, int middle, int end) {
        for (int i = start; i <= end; i++) {
            helper[i] = array[i];
        }
        int k = start;
        int i = start;
        int j = middle + 1;
        while (i <= middle && j <= end) {
            if (helper[i] <= helper[j]) {
                array[k] = helper[i];
                i++;
            } else {
                array[k] = helper[j];
                j++;
            }
            k++;
        }

        // Copy the rest. Either of the while loops works, not both.
        while (i <= middle) {
            array[k] = helper[i];
            i++;
            k++;
        }
    }
}


texts: 3-SAT reduction to image matching problem

texts:
I have a research paper, Elastic image matching is NP-complete by Daniel Keysers and Walter Unger, that illustrates  the reduction from 3-SAT to an image matching problem in order to prove that this problem is NP-Complete. It says that from 3-SAT formula we construct an equivalent image matching problem using a cost function $f$ such that $c(A(o),B(o),f) \leq 0$ iff the formula $o$ is satisfiable. And reduction from 3-SAT is performed using 3 steps:

constructing the dependency graph $D(o)$
$D(o)$ is drawn in the plane
The drawing of $D(o)$ is refined to depict the logical behaviour of $o$.

We need to use components that act as building blocks for drawing the  graph, which are the representation of connectors, crossing, variables and clauses.

This is the basic idea. Before I try to understand the reduction I couldn't understand the basic components they are talking about. Any hints to help understanding the problem?


texts: About the pseudo polynomial complexity of the KnapSack 0/1 problem

texts:
I have read Why is the dynamic programming algorithm of the knapsack problem not polynomial? and other related questions, so this is not a duplicate but just a related pair of questions to clear some doubts.
A question that frequently arises when discussing the complexity of the dynamic programming solution for the KS problem is something like ¿Why $O(n \cdot W)$ is not considered polynomial?.
The common answer is that, by definition, we are concerned with the running time of an algorithm as a function of the size of the input. So, while is correct to say the running time is bounded by a polynomial in the value of $W$, is not polynomial in the size of $W$, because in fact what we have is $O(n \cdot 2^W)$.
Here we can also ask ¿Why not $O(2^n \cdot 2^W)$?, i.e. by the same reasoning $n$ should also be exponential in the length of the input. But the "trick" is that it seems $n$ is usually (always?) not considered part of the input at all. Instead, the input is (by convention i guess) just a list of $n$ weights, a list of $n$ values, and capacity $W$. Indeed, we don't need $n$ itself in the input.
Questions:

Suppose we have $n$ itself in the input, as nothing stops me of doing it in this way. The algorithm loops from $0$ to $n$ in the same way it loops from $0$ to $W$. Now, is correct to say the running time is $O(2^n \cdot 2^W)$ ?.
But if (1) is the correct, i dont think this algorithm with $n$ in the input have the same asymptotic behavior as the common one. How $O(2^n \cdot 2^W)=O(2^{n+W})$ compare with $O(n \cdot 2^W)$ ?.
Consider the usual naive recursive algorithm for the KS 0/1 problem. This is said to be $O(2^n)$, because in the worst case two recursive calls on $n-1$ are needed. In this case, $n$ is clearly in the input, but we are considering $n$ as a value when doing the recurrence analysis. So, considering earlier discussion, i'm tempted to say that in fact we have $O(2^{(2^n)})$ which is double exponential and not just exponential ... but does this make sense?


texts:
I am looking for familiar problems on strings of finite length over an finite alphabet, where a polynomial time algorithm is known.

To be more precise, let $\Sigma$ be a finite alphabet. I am looking for problems, where the input (or an important part of the input) is a set (or an ordered list) of strings $w_1,\dots ,w_m\in\Sigma^*$ (gladly $m=1$) and there are known algorithms to solve the problem in polynomial time in the length of the input strings (+ possible other input variables). It would be great to get references to the algorithms, too.

An example:
Given a nondeterministic finite automaton $M$ with $s$ states, which accepts the regular language $T(M)$ and a string $w\in\Sigma^n$. Is $w\in T (M)$? Obviously, this is possible in polynomial time in $n $ (and $s $).

Why do I want to know such problems?
I want to analyse, whether the polynomial time holds for some (possibly exponential) compressed representations of the strings in the length of the compact form or not.

I am interested in problems of all possible areas. It is also okay to post just one problem. I hope to get a bunch of interesting problems in addition.

Thanks a lot!


texts: Are there specific rules for programming languages applicable to Quantum Computers?

texts: What would be the requirements for programming languages that are used for quantum computers? Do standard procedural languages with their constructs be sufficient, and succinctly capture the computing capabilities of a Quantum Computer? To illustrate, languages such as Assembler would most likely be closest to the hardware, and the programmer programs to the Assemblers' specifications. CSP is an example of specification for concurrent processes. Are there any formalisms such as CSP for quantum computers, or even languages such as Assembly for quantum computers?


texts: Karp hardness of digraph coloring without monochromatic dicycle

texts:
Problem statement:

  Input: a digraph $G(V, A)$ and a natural number $k$

  Output: YES if it is possible to color all vertices of $V(G)$ by $k$ colors such that no directed cycle is monochromatic, NO otherwise

Is this an $NP$-complete problem?


texts: Smallest Number of Strings to Distinguish $n$ Pairwise $L$-distinguishable Strings

texts:
The following is a homework assignment. I am looking for criticism / feedback on my solution, and I have a specific question.

Suppose $L$ is a language over $\Sigma$, and $x_1, x_2, ... , x_n$ are
strings that are pairwise $L$-distinguishable. How many distinct
strings are necessary in order to distinguish between the $x_i$'s? In
other words, what is the smallest number $k$ such that for some set
$\{z_1, z_2, ...,z_k\}$, any two distinct $x_i$'s are distinguished,
relative to $L$, by some $z_l$? Prove your answer.

The book gives a hint, which reads as follows:

Here is a way of thinking about the question that may make it easier. Think of the $x_i$’s as points on a piece of paper, and think of the $z_l$’s as cans of paint, each $z_l$ representing a different primary color. Saying that $z_l$ distinguishes $x_i$ and $x_j$ means that one of those two points is colored with that primary color and the other isn’t. We allow a single point to have more than one primary color applied to it, and we assume that two distinct combinations of primary colors produce different resulting colors. Then the question is, how many different primary colors are needed in order to color the points so that no two points end up the same color?

I have surely addressed this question Here is my answer.

Solution: Coloring $n$ points so that no two points end up the same color requires $\lceil \log_2 n \rceil$ primary colors.
First enumerate the points using binary representations, and let each digit correspond to a primary color. Then we identify the combination of colors for a given point as all primary colors whose corresponding digit is 1. Each of the points has a unique representation, so each combination of primary colors will be unique.

What do you think of this response? Do you think it needs further explanation?
Also, I am having trouble translating this argument into the context of the original question. How can I better see that the problems are the same?


texts: Default scan order in SCAN and LOOK disk scheduling algorithms

texts: I've been learning various disk scheduling algorithms in Operating systems. I wanted to know if there was any default scan order in SCAN, C-SCAN, LOOK and C-LOOK algorithms, like towards higher cylinders or lower cylinders ? Or are they OS-specific ?


texts: (Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?

texts:
The following question is taken from Leetcode entitled 'Combination Sum'

  Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

  The same repeated number may be chosen from candidates unlimited number of times.

  Note:

  All numbers (including target) will be positive integers.
  The solution set must not contain duplicate combinations.

  Example 1:

  Input: candidates = [2,3,6,7], target = 7,
  A solution set is:
  [
   [7],
   [2,2,3]
  ]

  Example 2:

  Input: candidates = [2,3,5], target = 8,
  A solution set is:
  [
   [2,2,2,2],
   [2,3,3],
   [3,5]
  ]

To solve this problem, I applied dynamic programming, particularly bottom up 2D tabulation approach. The method is quite similar to 0/1 knapsack problem, that is, whether we want to use an element in candidates or not.

The following is my code:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not len(candidates):
            return 0
        dp = [ [1] + [0]*target for _ in range(len(candidates) + 1)]
        for row in range(1, len(candidates) + 1):
            for col in range(1, target+1):
                dp[row][col] += dp[row - 1][col]
                if col - candidates[row-1] >= 0:
                    dp[row][col] += dp[row][col - candidates[row-1]]
        print(dp[-1][-1])

However, my codes above do not give solution set. Instead, it gives the number of elements in solution set.

I attempted to generate solution set from my codes above but to no avail. Can anyone help me?


texts: Can nodes in red-black trees have one nil child and one non-nil child?

texts: I don't recall hearing that nodes in red-black trees can't have one nil child and one non-nil child. However, I did hear that red-black trees have a worst-case height of $2log_2(n + 1)$, where n is the number of nodes, and I don't see how this could be the case if nodes can have one nil and one non-nil child, as a tree could be constructed that is simply a straight line/linked list, which would have a height of n.


texts: Comparing $\log^\alpha n$ with $n^\beta$

texts:
I'm trying to solve a recurrence using the master method:

$T(n) = 10*T(n/3) + n^2\log^5n$

I set up the comparison

$n^2\log^5n$ and $n^{\log_3 10}$

and reduced them to:

$\log^5 n$ and $n^{\log_3(10/9)}$

I'm struggling to understand how these functions compare asymptotically.

From one side I understand that in general polynomials grow slower than logarithms, as written in a similar question here: Sorting functions by asymptotic growth.

However, I graphed both of the functions using a graphing calculator and it appeared that the logarithmic function grew faster than the polynomial, even at large n.

Basically, is it really true that $(\log n)^{\alpha} = o(n^\beta)$ for all $\alpha,\beta>0$? If it is, how would you go about rigorously proving it one way or the other?


texts: Can the intersection two non-recursive sets be recursive? Prove it

texts:
I am still really new to compsci theory and some of the topics are really hard to understand. For this Problem I would think that say we have two sets A and B and they are both non-recursive.
If we take  A ∩ B we would get the the matching inputs and since they are both from non-recursive sets wouldn't the  intersection also be non-recursive? or am I thinking about this the wrong way. Any help appreciated
Thanks


texts: Monte Carlo Tree Search in connect 5 tree design

texts:
I'm trying to create a mcts ai for connect 5 algorithm. However, I'm confused on designing the tree. Here is a quick description of the algorithm:

The initial state, S0 is the board state where the AI places the stone, or in other words, the AI's turn. Is it correct that each node should be the AI's turn, not the humans?

In the expansion phase, you need to "create child nodes". In my game, the child nodes would each be a place where an AI can make a move. However, if I want to select the next avaliable AI move, I need to know where the enemy, or the human places the stone before the next avaliable AI move. I improvised by making it 2-layered: for every avaliable human moves, add every avaliable AI moves after the human plays. Is this the correct way to do it?

This is my current tree structure in an
Example: Each state has info of where black and white "stones"are placed.
the AI plays white, and Human plays black. Black plays first. state S0 would be the first move of the game.

                S0(black stones:[(2,2)],white stones:[])
                        /                            \
                       /                              \
                      /                                \
S1(black stones:[(2,2)],white stones:[(1,1)])        S2(black stones:[(2,2)],white stones:[(1,2)]
    |                                                       |
S3(black stones:[(2,2),(2,1)],white stones:[(1,1)])  S4(black stones:[(2,2),(2,3)],white stones:[(1,2)]


texts:
I am trying to find a computable, injective and bijective function $f: \mathbb{N} \to A$ where $A$ is the set of all (finite) directed graphs up to isomorphism (also with no edge repetitions). Which means $A$ is containing equivalence classes defined by isomorphism.

i.e, given a graph (class) example $[G] \in A$ where $V_G = \{1,2\}$ and $E_G = \{(1,2)\}$ then if $G'$ is defined by $V_{G'} = \{3,4\}$ and $E_{G'}=\{(3,4)\}$ then $G' \in [G]$ and also if $G''$ is defined by $V_{G''} = \{1,2\}$ and $E_{G''}=\{(2,1)\}$ then $G'' \in [G]$.

In general $G' \in [G]$ if and only if $G'$ is isomorphic to $G$.

I need it to fulfill the restrictions:

If $|V_{[G]}| \leq |V_{[G']}|$ then $f^{-1}([G]) \leq f^{-1}([G'])$
If $|E_{[G]}| \leq |E_{[G']}|$ then $f^{-1}([G]) \leq f^{-1}([G'])$

I think the steps should be to give order to $[G], [G']$ such that $|V_{[G]}| = |V_{[G']}|$ and $|E_{[G]}| = |E_{[G']}|$ in some natural way, find how to calculate the number of $[G'] \in A$ such that $|V_{[G]}| = |V_{[G']}|$ and $|E_{[G]}| = |E_{[G']}|$ as function of $n=|V_{[G]}|, m=|E_{[G]}|$ and then somehow find $f$. Not sure how to go about these steps, or how to find $f$ in some other way?

Thanks for any help!


texts: How to simulate systems' unavailability?

texts:
I am simulating a system where the clients' unavailability is one big issue to the systems behavior.

I gathered the real system logs to analyze the unavailability of the clients in the deployment environments and I computed the values for Mean Time Between Failure (MTBF) and Mean Time To Repair (MTTR).

Now I want to simulate such a system failure in my simulator.
Currently what I am doing is as follows:

1. Every client rolls the dice every 1 minute (Uniform random in [0, 1])
2. If the number if larger than a specified probability (P_unavail),
   the client becomes unavailable for the next (T_unavail) minutes (i.e. (T_unavail) = 10min).

The simulation does not need to capture the whole details of the real world. Showing the trends (how often the failure occurs? how long does the repair take?) is indeed enough. However, the simulation method and parameters should not be arbitrary.

If any one who has some knowledge on it.

Is the method that I am using appropriate?
If yes, what values for P_unavail and T_unavail would be appropriate? Can I compute them MTBF and MTTR from the log analysis?
If no, could you give me any idea?

Thanks,


texts: how is an arbitrary dimension "reshaper" turned into a function given a linear index?

texts:
i have an arbitrary "reshaping" function which, given a linear sequential array can "reshape" it to 2D or 3D.  the order in which the X-dimension, Y-dimension and Z-dimension may all be changed, as well as the size of the X, Y and Z dimensions, may all be changed, at runtime.  consequently it is not possible to use static compilers or static allocation.

here is a function that, for the full sequential range, prints out a corresponding (remapped) set of indices:

(xdim, ydim, zdim) = (3, 2, 5)
lims = [xdim, ydim, zdim]
idxs = [0,0,0]
order = [1,0,2]

for idx in range(xdim * ydim * zdim):
    new_idx = idxs[0] + idxs[1] * xdim + idxs[2] * xdim * ydim
    print new_idx,
    for i in range(3):
        idxs[order[i]] = idxs[order[i]] + 1
        if (idxs[order[i]] != lims[order[i]]):
            break
        print
    idxs[order[i]] = 0

what i actually need is a function which, when it is passed an arbitrary index, returns one (correct) remapped index.

i suppose what i could hypothetically do is have a function that sets up the full array (at startup time), and indexes it.  i would however like to see an algorithmic version of the above.


texts: Is there a CPU architecture which allows early register access?

texts:
In Intel's x86 architecture, imul (integer multiply) usually has latency of a few clock cycles.  Those CPUs are very smart in filling the time (e.g., pipelining or out-of-order execution), but do any commercial CPUs simply let the program access the intermediate unfinished result?

To be realistic, one clock cycle after imul, the output register probably has not changed at all.  So, in this case, my question becomes: Is there any commercial CPU which would allow you to read that register in the following clock cycle though it still gives the old contents?

If the compiler plans for these latencies, it seems that this architecture might be useful.  It basically passes the burden of pipelining from the CPU to the compiler.  I'm sure this approach has a name, but I am just a curious beginner.


texts: Is the following extension of finite state automata studied?

texts:
Consider a finite state machine as usual, but every transition, it can also update an integer counter by adding or subtracting a number.
Say, a transition function of the form
$\delta(q,a) = (p,k)$
moves to the new state $p$, and add $k$ to the counter, where $k \in \mathbb{Z}$ (so $k$ can be positive, negative, or zero).

A string is accepted if the final state and the counter value is in $F$, where $F$ is a finite set of pairs of states and counter values.

Is this model known? I could not find any reference of this particular extension.


texts: Reducing SAT to a P problem in polinomial time

texts: Does reducing SAT in polynomial time to a P problem would mean that P = NP?


texts: algorithm complexity calculation T(n) = 2T(n/2) + n*log(n)

texts:
I guess I lack at understanding basic things at algorithm calculations, while learning for an exam.

at the result, does one write like O(ld n) or just log instead of ld ?
regarding the following calculation (not from me) at the yellow mark - why is it Theta(n) ? why not O(n) ? I dont get it..

big thanks in advance !


texts: Variation of interval scheduling algorithm with several job categories, only one from each can be used

texts:
I have a problem similar to the interval scheduling algorithm. The differences are:

The jobs have the same length.
There are several categories of jobs and only one job from each category can be chosen.
There can be no overlap in time between different categories.

I have illustrated the problem with a picture:

Each line is a job. Different color means that they belong to a different category. So I need to choose one of each colored line to try to cover as large an area as possible without any lines overlapping. Remember that lines with the same color should not be chosen twice. And yes, for the illustration the problem is trivial.

Does my problem have a name? Does it require a DP algorithm?