texts:
Consider the following problem: Given a weighted directed graph $G$, determine if $G$ has a cycle whose total weight is $k$. All edge weights are integer but might be negative. $k$ is not an inputted value. It's fixed and known beforehand to everyone. So $k$ is NOT an input to this algorithm.
I want to show the problem is NP hard, so this means I have an oracle that tells me whether or not a graph has a cycle whose sum of edge weights equals $k$ for a fixed, known value of $k$.
I thought about reducing from Hamiltonian cycle. So I want to show that I can use this oracle to solve Hamiltonian cycle problems.
Let $G$ be a graph. I want to see if $G$ has a Hamiltonian cycle. I try to construct a new graph to provide to the oracle but I'm not sure how to do so. I think it needs to have $k$ vertices so I tried doing casework on when $G$ has more or less than this many vertices.
I can show that I can solve Hamiltonian cycle problems with $k$ vertices by constructing a new complete graph where edge weights are $1$ if it was in the original graph and a really large nunber otherwise. Then running the oracle on this graph returns true only if there's a Hamiltonian cycle with $k$ vertices. But this doesn't handle the general case. Is this proof fine?
But I'm stuck. Any help is appreciated.


texts: genetic algorithm with different categories of parameters

texts:
I am trying to use a genetic algorithm to solve a problem. However, I find it difficult to represent the chromosomes in my problem. In the problem, I have two categories of parameters, and each gene inside the chromosome has a specific range of values.

For example, Category $A$ has chromosome $X$ that has the following genes:
$x_1$, $x_2$, $x_3$, $x_4$, where

$x_1$ takes value between $1$ and $5$ (inclusive).

$x_2$ takes value between $10$ and $30$ (inclusive).

$x_3$ takes value in the set $\{1,4,6,10\}$.

Also, Category $B$ has chromosome $Y$ that have genes with different values.

The difficulty here is how can I encode the chromosomes $X$ and $Y$ with the different ranges of values?


texts:
The a^n was pretty easy:

function powN(a, n) {
    if(n == 0) return 1;
    return a * powN(a, n - 1);
};

But somehow I got stuck on a^(2^n), any suggestions or even a hint?

I need a recursive algorithm that solves: a^(2^n).


texts: Function to generate longer bit-sequence from shorter sequence with certain properties

texts:
im not familiar with the terminology of computer-science which makes it pretty difficult to search for the problem I have.

I'm looking for a function that generates a sequence of bits (B) of a given length (i.e. 1024 bit) from a chosen bit-sequence (A) (i.e. 32 bit).

This function needs to have the following properties:

The relation A->B has to be unique
A slight change of A (i.e. 1 bit) results in a slight change of B (~1024bit/32bit = ~32)

While searching I came across hash-algorithms but they achive kind of the oppisite I want to do. They shorten a sequence and a small change of the first one results in a big change of the other one.

Do you know of such a function or do I have to come up with something myself?

Example (with fewer bits):

Let bit-sequence A be given as 0b0101 (integer-representation: 5).
Let function F map A to B so that B = 0b1001 0010 0101 0111 (example). Here, B can be split into 4 4-bit integers (9, 2, 5, 7).

Changing 1 bit of A from 0b0101 (5) to 0b0100 (4) results in 4 changed bits of B so that the resulting bits are 0b1011 0000 0101 0110 (integer: 11, 0, 5, 6).

The 4 integers contained in B will be used in further computations and I'm looking for function F.


texts: If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I know if a type 3 grammar is $LR(1)$, $LL(1)$, $SLR(1)$, etc. without constructing any parse tables?


texts: Finding all "basic" cycles in an undirected graph?

texts:
Say you have a graph like

a — b — c
|   |   |
e — f — g

and you would like to find the cycles c1, {a,b,f,e}, and c2, {b, c, g, f}, but not c3, {a, b, c, g, f, e}, because c3 is not "basic" in the sense that c3 = c1 + c2 where the plus operator means to join two cycles along some edge e and then drop e from the graph.

I invented my own terminology in the above but basically I want to find all cycles in a graph that cannot be decomposed into smaller cycles. Does this problem have a name? Is there a known best algorithm for solving it?

I understand that enumerating all cycles runs in exponential time because there may be an exponential number of cycles but my intuition is that the number of basic cycles as defined above is related only  polynomially to the number of edges in the graph.


texts: What is the error when using Levenshtein distance on flattened binary trees?

texts:
I need to calculate the edit distance between many pairs of binary trees. Unfortunately this is computationally expensive.

The trees are stored as a flattened list of indices into node and terminal lookup tables. The particular flattening structure is the pre-order encoding format (pseudo code: flat(tree) = [id(root)] + flat(left) + flat(right)).

If I calculate the Levenshtein distance between the flattened trees, rather than between trees:

How big will my error be? (Difference to tree based distance)
Would other flat structures be more accurate?


texts: Recognizer to check if the language of a Turing machine contains a finite subset

texts:
Let $B = \{ 123 \}$.

Note that $B$ is finite.

Let $L = \left \{ \left\langle M \right\rangle | M \text{ is a Turing machine such that } B \subseteq L(M)  \right\}$.

Is it sufficient to show that $L$ is recognizable by checking if $M$ accepts on input $123$, and therefore $\left\langle M \right\rangle \in L$?


texts: Turing Machine 'marking' specific portion of encoding

texts:
Given a turing machine $T$ that receives an encoding of another turing machine and a word $<M><w>$, can $T$ 'run' through the encoding and 'mark' specific transitions/states?

For example, if I want to show that the language $L = \{<M><w>\}$ such that when we run $w$ in $M$ we will visit at least two unique states different than the starting state.

Now for this, I suggested this algorithm, but I am not sure it is even compuatable:

  Given the encoding $<M><w>$, we will run through the encoding and 'mark' all states that can be reached from the starting state of $M$, if two or more states have been marked after finishing, accept, else, reject.

I know that since this an encoding of a turing machine and a word, we indeed -can- run through the encoding. But can we really do the 'marking' operation? if so, how?


texts: What is the meaning of 'breadth' in breadth first search?

texts:
I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this:

  Breadth-first search is so named because it expands the frontier
  between discovered and undiscovered vertices uniformly across the
  breadth of the frontier.

However, I'm not able to understand the meaning of this statement. I'm confused about this word "frontier" and breadth of that frontier.

So, can someone please answer this question in a way which is easy to understand for a beginner like me?


texts: Finding the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k

texts:
Say I had a list of numbers in the range of 1-20 for example: [5, 16, 17, 3, 2, 14, 4, 9, 11, 19], and an integer k (let's say k = 40)

How would I find the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k?

I believe this algorithm is NP complete.

Just think of the problem as a bin packing algorithm but instead of saying that the total value of items in the bin must not exceed the bin's capcacity, I am saying that the total value of items in the bin must be exactly equal to the bin's capacity. Also, we are trying to maximise the number of bins.

Example scenario:

Say I have a list: [1, 2, 2, 3, 5, 6, 5] and k=7, then some example values of S would be:

[(3+2+2), (6+1)] - 5 and 5 left over

[(5+2), (5+2), (6+1)] - 3 left over

As you can see, the second solution is optimal because it produces 3 partitions rather than 2.


texts: Double hashing - probe count probabilities

texts:
From TAoCP, Vol. 3 by Knuth we know that expected (mean) probe counts for hash tables with open adressing and double hashing collision-resolution are:

$1 \over 1 - \alpha$ - for unsuccessful search
${1 \over \alpha} ln({1 \over 1 - \alpha})$ - for succesful search

Where $\alpha$ is load factor.

Are there expressions for probabilities of making exactly $i$ = 1,2,3,.. probes?


texts: How would I go about determining popularity and relevance among articles and use it to improve my search algorithm

texts:
Disclaimer:
First of all I've had a lot of trouble finding the right stack exchange site for this question and I don't know if it's correct here either.

The Problem:
I'm working on a search algorithm for a django powered website which allows people to write articles on various subjects and search for articles on the webpage.

I've got a database in which I store articles for people to read on a website. I'm storing each article with a bit of information like:

Articles:

A title.
A predetermined category where the writer can choose from when adding
an article (sports, economy, politics).
Tags which the writer of the article can input themselves.
Length of the article in characters
A short description
Dated added
Date updated

I've a few easy ways a user can search an article based on the title ( for example shortest first or newest first)

I'm now working on adding a way to search based on popularity but I have a hard time to determine what I define as popular.

I'm saving article views in a different database table which contains:

Views:

User ID
article ID
Timestamp

Each row inside this table is considered 1 view so I can see exactly when certain articles are doing well in terms of amount of views it gets. If I would search for an article with the most views in the database it would look something like this in django:

Article.objects.order_by('-views')[:30]

In this case views is stored in the table, However I store it in a different table so I can have the functionality described above.

The problem however is that if I have 1 article which is a few years old with a high number of views, for example lets say there has been a sports event (like the Olympic games of 2014) and a lot of people have read the article but the article is no longer very relevant as this same event has been done again (that would be the Olympic games of 2018 happening this year).

Now lets say someone searches for popular articles about the Olympic games. Even though the articles about the Olympic games of 2014 have gathered more views than those of 2018 (as they have been written roughly 4 years ago and therefor have had more time to gather views)

In this case the more relevant articles should be presented to the user before the more popular articles.

My Potential Solution:

I'm thinking of adding a column to the article table for memorizing the 'importance' of each article, then I can have Importance be determined by other factors

for example if I want to have the amount of views be a factor for each view importance gets a bit higher, but if the view has been within the last week it might count as 2 views. therefor favoring more actual articles slightly more over articles with more views but written a few years ago. this also allows me to for example measure the time each reader spends on an article and have that influence importance as well.

However I'm not sure if this would be the best way of doing things as there are a few problems like:

If importance is stored in the database it has to be updated regularly and periodically which may cause performance problems whenever the user accesses an article while the database is updating it's articles importance.
Calculating the importance in real time every time a user doe a search will also take a huge amount of processing power if the amount of users is very high, it will also probably cause a lot of redundancy whenever 2 users search for the same articles and the exact same importance factor is calculated twice.

How would I go about implementing this way of sorting the search results without needing lots of processing power? Is this the best way to do it? How do other search engines handle this problem?


texts:
Detecting the regions where a car has been damaged and the extent to which it has been damaged is a very interesting problem. It has potential applications in automatic auto insurance claims. Currently I'm trying to tackle this problem and am looking for papers/ideas for the same.

I am currently modeling the problem as a segmentation task which can classify each pixel into three classes - background, car, damaged car.

More details:
I don't have a lot of data to just train a deep network on. I managed to gather around 700 damaged car images and there are multiple datasets for undamaged cars link. I've tried to generate synthetic data in Unreal using this project, but I'm afraid learning on synthetic data won't generalize to real world images.

Additionally, I found multiple startups working on the same idea but I couldn't find any info on how they're doing it link link. I also found a thesis which aims to do the same link. But it's quite old, and doesn't exactly tackle the actual problem.

I am looking for more ideas on how to formulate the problem and any previous work (like weakly supervised segmentation). Please let me know if you know of any. Thanks!


texts: Proof of correctness recursive reverse digit function

texts:
This is an attempt to understand better recursion.
The following recursive function returns the integer obtained by reversing the digits of an input integer. I'm trying to prove its correctness:

public static int reverse(int n)
{
    return reverse(n, 0);
}
public static int reverse(int number, int reverted)
{
    if (number!=0)
        return reverse(number/10, reverted*10 + number % 10);
    else
        return reverted;
}

The program requires the integer input to be strictly positive, and the program clearly terminates because n is decreasing. Moreover, we have the relation

reverse(xy, z) = z*reverse(xy) = z*reverse(y)*reverse(x)

How should I proceed to complete a formal proof of correctness for recursion?


texts: What do the ∀ and ∃ symbols mean in the Axiom of Choice?

texts:
On the Wikipedia page for the Axiom of Choice the following statement is given:

$(\forall x^\sigma)(\exists y^\tau)R(x,y)\rightarrow(\exists f^{\sigma \rightarrow \tau})(\forall x^\sigma)R(x, f(x))$

Most of it seems fairly straightforward, except for the meanings of the symbols that look like 180 degree rotated 'E' and 'A'


texts: Is there a uniform way of giving for any mathematical formula a hypercomputer that computes it?

texts:
Some mathematical formulas directly suggest an algorithm for computing it (even if sometimes an inefficient one).
For example, if we recursively define $\sum_{i=1}^nx_i=x_n+\sum_{i=1}^{n-1}x_i$, then this directly suggests a recursive algorithm for computing the sum. In fact we might even have a functional programming language where this is a valid program.
But some mathematical formulas are not even decidable, let alone suggest a specific algorithm for deciding it. For example, let $X$ be an uncountable set and $T\subseteq \mathcal P(X)$ an uncountable set. Then for example the property $\phi:\forall A_1,A_2 \in T, A_1\cap A_2 \in T$ is in general undecidable because the sets are uncountable, so we cannot check this for all sets $A_1,A_2$ (note this is a proporerty for $T$ to be a topology). However, we can imagine checking this with a hypercomputer: Execute a thread for each pair $A_1,A_2$, and check if $A_1\cap A_2\in T$. This will be an uncountable number of parallel threads. Then take an uncountable AND between the results of these threads.
Note that this is a "natural" algorithm, in the sense that we didn't make any specific implementation decisions.
Can we generalize this? I.e.

Is it possible, within some formal language for mathematics (e.g. calculus of constructions/calculus of inductive constructions) that can define any mathematical objects, to define a semantics for any mathematical formula that may use some form of hypercomputation to compute that formula?

Is there a name for this idea so that I can look it up?


texts: Is this “cut condition" sufficient for unique minimum spanning tree?

texts:
Given a connected, undirected, weighted graph $G$, the following "cut condition"

  For any partition of the vertices of $G$ into two subsets, the minimum-weight edge with one endpoint in each subset is unique.

is not necessary for $G$ to have a unique minimum spanning tree.

However, is this "cut condition" sufficient for $G$ to have a unique MST?

Related post: Is this "cycle condition" sufficient for unique minimum spanning tree?


texts: Logic Question - Why is This an Implication?

texts:
I have a question about predicate logic. Suppose we have the following predicates:

$\text{Study}(x,y)$: x studies y

$\text{Comp}(x)$: x is a computing student

I want to encode the following sentence in predicate logic: "Some, but not all computer students study logic."

A potential answer is:

$$\exists x(\text{Comp}(x)\land \text{Study}(x,l))\land\neg \forall x(\text{Comp}(x)\implies \text{Study}(x,l))$$

Why is there an $\implies$ and not a $\land$? Is this formulation correct?


texts: Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem

texts:
I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$
with base case $T(n) = 1$ if $n \leq 1$.
I know that the solution is(with the help of the Master Theorem) $$\Theta(n*log^2(n))$$
I tried without the Master theorem and witht the help of the substuition method I got the following expression
$$T(n)=n+2*n*\sum_{k=0}^{log_{3}(n)-1}log(\frac{n}{3^k})$$
How can I convert this expression into a valid $\Theta(n*log^2(n))$ expression ?


texts:
I am working on showing that 3-colorability is NP-complete. I read a few articles and walkthroughs on this but none are really clicking. I get to this part

  "Then for every variable xi that appears in the instance of Satisfiability, we connect a
       vertex xi to a vertex xi, and we connect both xi and xi to red. This is illustrated
       below for a case where there are (only) 3 variables."

I think what they mean is something like this:

x1----x1*     x2----x2*      x3----x3*
 \   /         \   /          \   /
  \ /           \ /            \ /
   R             R              R

But my question is, what exactly is this step doing?

With a little bit more thought, is this step just showing that given xi to be one color, then xi* has to be another, but also cannot be R, as they are both connected to it?


texts:
I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them.
After each merge operation, the graph should remain acyclic.
Let's say my graph contains blue nodes and white nodes.

A and B are connected, they may be merged:

The above graph is DAG.
Merging node {A,B} with node {D} is illegal since it creates a cycle!

My current algorithm is based on union-find.

For each blue node b:
   Make-Set(b)
For each two connected blue nodes a,b:
   Union(a,b)
For each set://Created at the previous step
   merge all nodes of the set

The bug is the output graph contains cycles. How can I avoid merges that create cycles in the graph?
Before each Union, I need to check that it "safe". Safe means that after merging cycle will not be created.
I can find all passes between the set of a and set of b before Union but this solution is too expensive (time complexity).
I can't use solutions with a quadratic time complexity since my graph is too big.
Edit:
We can merge nodes according to topological order but the following case will be messed (D):

Nodes A, B, and D may be merged, but we will merge only A and B.
Max Cluster example: at the graph below the cluster is {A, B, C, D, E}


texts:
So I am stuck:

I have this algorithm from which I need to find a loop invariant but I just can't get my head around it :

main_f = x
follow_up = x
while (follow_up < y):
   follow_up = follow_up + 1
   main_f = main_f + follow_up

return main_f

So basically I have a list of values of this function(main_f):

Initialisation : i = 0 , main_f = x

Iteration 1: i = 1 , main_f = 2x+1

Iteration 2: i = 2 , main_f = 3x+3

Iteration 3: i = 3 , main_f = 4x+6

Iteration 4: i = 4 , main_f = 5x+10

Iteration 5: i = 5 , main_f = 6x+15

And basically it goes on and on like this in a while (main_f < y) loop;

The loop invariant is certainly a sigma from i=x to y  with the "x" part:
(i+1)x but i can't find the formula that fits the integer part I got after the iterations.

Thanks in advance for your help


texts: outside of bitcoin, how does a network negotiate what the next blockchain should be?

texts:
There are two problems I see with negotiating the next block chain:

which transactions to include in the chain (because consider transaction T which has propagated through exactly 49% of the network at the time the next block is negotiated)
which proposed block to consider the next legitimate block in the chain, because even assuming all nodes have all transactions, what's to stop every node from attempting to propose the next block, thus forcing the network to attempt to propagate and resolve N different block collisions.

In bitcoin, number 2 above is easily resolved by intentionally imposing conditions on the resulting hash of the blockchain such that it is computationally difficult to derive the hash, and thus collisions (where 2 nodes propose a valid block/hash at the same time) are very rare.

Outside of bitcoin, I'm skeptical as to how new blocks are announced and agreed upon. If you have a blockchain structure where a new block should be announced at an artificial time interval of every 10 minutes (assume the network is time sync'd) then what's to stop all your nodes from attempting to propose many different next blocks all at once? In a general blockchain network that isn't bitcoin, I don't see any restriction like #2 above that reduces the ability for many nodes to come up with their own proposed blocks and to stop them from trying to announce these blocks to the network.

Also, assuming we can resolve this issue ^ and manage to negotiate which block to use as the next one in the chain, we're assuming here that the contents of all the proposed blocks are also equal. How can a network negotiate the next block if 49% of nodes contain a transaction that the other 51% of nodes do not?


texts: Placing small circles randomly inside a larger circle, where no two small circles intersect

texts:
Sorry if this is the wrong place to ask, was unsure...let me know if it belongs some where else.

So i am trying to work out a way to write an algorithm to place a series of small circles of a set radius (all the small circles have the same radius), inside a larger circle.

The small circles cannot overlap each other or overlap the main circle's perimeter, and they are placed randomly inside the main circle.

I am wanting it to then populate as many circles as it can until it is not possible to place any more circles without overlapping another.

This obviously means that each run through depending on the random placements will potentially give different amounts of maximum number of circles inside the big circle - thats fine, and thats some what the point.

Does any one have any advice how i might approach the logic for this?


texts: Equivalence preserving operator from CTL* to LTL

texts:
The question is about an operator that transforms any CTL* formula ${\psi}$ into a (not necessarily equivalent) LTL formula ${A\psi^d}$, where $d$ means syntactically removing all $A,E$ quantifiers from ${\psi}$.

Is it true that this operator preserves logical equality, i.e.
${\psi_1}\equiv_{CTL*}{\psi_2}\implies {A\psi_1^d}\equiv_{LTL}{A\psi_2^d}$ ?


texts: Disproving well-quasi-order by providing an infinite anti-chain

texts:
I am currently studying the theory behind Well-Quasi-Orders. However I am having some issues in understanding how an infinite   anti-chain can be produced to disprove the claim that a partial order $P$ is a w.q.o.

In particular I am wondering whether it is  logically sound to   present  as proof not the infinite anti-chain  but rather an algorithm to produce it.

More specifically, I've been trying to solve  an exercise from the following lecture
which asks whether the class of $P_{3}\text{-free}$ graphs is a w.q.o or not on the induced subgraph operation $\leq_{i}$

I've proved that said class contains unions of  cliques and defined an ordering of this set as follows  $P=\lbrace G_{0},G_{1},G_{2},.... \rbrace$ with $G_{i}$ representing all  $P_{3}\text{-free}$ graphs on $i$ vertices  (and graphs in $G_{i}$  being  represented in a  touple-like alpharithmetic form $(a_{1},....,a_{i})$ such that $a_{1} \leq a_{2} \leq.... \leq a_{i}$ to avoid repetitions and $\sum_{j=1}^{i} a_{j}=i$ to define  an order. For example $(0,0,2,2)$ $\in G_{4}$  encodes the graph with two disconnected $P_{2}$ components.

I have defined an algorithm $B$ that produces an anti-chain that grows bigger and bigger at each step

The algorithm uses gadgets  defined as $B_{a,c}$ which  represent the graph  with $c+1$ connected components, the first $c$ of which are $K_{1}$(i.e a sole vertice) and the last component representing $K_{a}$

The steps of my algorithm are the following:

Define $L$ as the sequence
Add $B_{a,0}$ to $L$    ($a$ any number $>$ 0)
repeat $\infty$ times:

4.Replace each  item  $B_{a,c} \in L$ by $B_{a^{'}=a+1 + 10^{6},c}$ and produce $L^{'}$  this way.

5.Let $X=B_{a^{'},c}$ be the graph with the maximum $c$  amongst those in $L^{'}$

6.Add to $L=L^{'}$ the graph $B_{a^{'}-2,c+1}$

Certainly, this algorithm does create an   anti-chain( in each step I create a graph with more connected components yet less  vertices). However I am not sure that such  a technique is valid for disproving w.q.o  on the infinite anti-thesis claim because of the fact that it works on a step by step basis.

Any help is appreciated. Thank you very much!


texts: Is it true that the potential method is usually the inverse of the accounting method in the context of amortized analysis?

texts: I remember reading this somewhere (will post the source as soon as I find it), but was wondering, if anyone knows why this is true or has maybe an example to portray why this is the case.


texts: Is it correct to say that CPU's only compute threads?

texts:
New to the world of parallel computation. Would it be correct to say that CPU's are actually thread calculators? My understanding currently: a process is composed of multiple threads and a single core on a cpu is capable of executing instructions from 1 thread at a time, sometimes a bit more when taking into account hyper-threading, but essentially it is computing threads. When the CPU, along with  all of its cores, are done calculating all of the threads that belong to a specific process then that process would be considered complete.

So like an analogy would be:

A CPU is like a monkey, with N number of mouths (cores). Each mouth is responsable for eating a long chain of bananas (threads) out of wooden crates (processes). We can increase the rate at which some program is finished/emptied, by hooking up more banana chains from it to an empty and waiting core/mouth. A program is called complete if the wooden crate is emptied of all bananas.

Would this interpretation be correct?

Below is an illustration of my current understanding

also what are some of the practical differences (programming-wise) of what I can/cannot do with spawning new processes vs threads. I always see something along the lines of processes have their own memory while threads share it but what do they really mean by that? Like in python, can I just go like from thread_a import var_something?


texts:
Referring to Tim Roughgarden's Lecture Note - 2 (page 11) on CS261 at Stanford following statement and the para seem quite confusing.

Claim: d(f) never decreases during the execution of the Edmonds-Karp algorithm.

https://www.youtube.com/watch?v=uM06jHdIC70

Can anybody shed some lights on it?

  Suppose the Edmonds-Karp algorithm augments the current flow f by routing flow on
  the path P . Because P is a shortest s-t path in Gf
  , it is also a path in the layered graph Lf
  .
  The only new edges created by augmenting on P are edges that go in the reverse direction
  of P . These are all backward edges, so any s-t of Gf
  that uses such an edge has at least
  d(f ) + 2 hops. Thus, no new shorter paths are formed in Gf
  after the augmentation.


texts:
A very tricky problem in graphics rendering is drawing thin lines ($1px$ width) that do not look jaggy. The only implementation I have seen that is very good is that in Mathematica, but their algorithm is proprietary.

Is there a well known algorithm for anti-aliasing thin lines?


texts: Find equal length subsequences with maximum difference of sums, for given maximum subsequence length

texts:
The problem is the following. Suppose we have a sequence of n non-negative numbers, each element with index i having its own value, value[i].
 We want to put some cells in a subsequence Plus, and some cells in the subsequence Minus.

Not all the elements have to be in one of these subsequences, one might not be in any one of them, but the two subsequences are exclusive.

Of course, the elements of each subsequence must have the same relative order in the subsequences as they had in the starting sequence.

The element with the lowest index in the starting sequence that is included in some subsequence (not necessarily the first one, as we can leave arbitrarily many elements unselected - not included in any subsequence - between two selections), has to be part of the Minus subsequence - that is, the first element of the Minus sequence must have a lower index than the first element of the Plus sequence in the starting sequence.

When an element of the  starting sequence is put in the Plus subsequence, the element with the immediately higher index that will be selected (not necessarily the next one, we might leave some elements unselected as described above) HAS to be put in Minus, and vice versa - that is, no two selected elements might be in the same subsequence, if there is no other selected element between them in the original sequence belonging to the other subsequence, so in essence the elements of the two subsequences form "pairs" (two elements of the Minus and Plus with the same indexes in the respective sequences), that might have non-selected elements between them, in the starting sequence. The Plus and Minus subsequences have to be of the same length, but that length must be at most a given value K.

Given that V = sum(Plus) - sum(Minus), I want to find out what is the maximum V possible, given the starting sequence.

V can also be 0, if, for example, the contents of the starting sequence are larger the larger the index.

What I have come up with so far, is a dynamic programming algorithm with memoisation, having a n*2*K array to store the computed results, and eventually computing as many calls of the Recursive function to get the final result. The pseudocode is as follows:

Recursive(i,prev_selection,remaining_selections):
    if remaining_selections<=0 or i>n:
        return 0

    if computed[i,prev_selection,remaining_selections] != EMPTY:
        return computed[i,prev_selection,remaining_selections]

    if previous_selection  == Plus:

        GoesToMinus = Recursive(i+1,Minus,remaining_selections) - value[i]

        IsNotSelected = Recursive(i+1,Plus,remaining_selections)

        computed[i,prev_selection,remaining_selections] = max(GoesToMinus,IsNotSelected)

        return computed[i,prev_selection,remaining_selections]

    else if previous_selection == Minus:

        GoesToPlus = Recursive(i+1,Plus,remaining_selections-1) + value[i]
        //Selections are only decreased when selecting a Plus
        //Remember that Minus is always selected first

        IsNotSelected = Recursive(i+1,Minus,remaining_selections)

        computed[i,prev_selection,remaining_selections] =  max(GoesToPlus,IsNotSelected)

        return computed[i,prev_selection,remaining_selections]

The result is found by executing Recursive(1,Plus,K). The space as well as the time complexity in this is Θ(n*K).

Can you suggest some algorithm with better complexity? I feel like I am missing some property of the problem that can speed things up.


texts: Binary search with alternative comparison cost

texts:
I have a sorted array $A$ of non-arbitrary elements. Now, I have another element $c$ and I want to find out where it belongs in the sorting of $A$. The cost of comparing $c$ to $A_i$ is $\Theta(i^2)$. I do not directly care about the number of comparisons, I just want to minimize the sum of the costs of the comparisons in the expected case (worst-case would also be nice).

Let's assume that each element in $A$ is unique and that $A$ does not contain $c$.

What is the optimal algorithm?


texts: PageRank and EigenTrust: How small should epsilon be?

texts:
For probabilistic algorithms such as PageRank and EigenTrust, the stopping case is given as $|R_{t+1} - R_{t}| < \epsilon$ (i.e. convergence is assumed). Neither the papers on EigenTrust or PageRank, or the PageRank wiki page, give any clear indication of what $\epsilon$ should be.

I believe it might be something to do with the damping factor $d = 0.85$; specifically $\epsilon = 1 - d = 0.15$, but  I can't be sure.

How is $\epsilon$ determined, and if it's nothing more than an abitrary value $0 \leq \epsilon \leq 1$, how would you choose a sensible value?


texts: How to analyze the worst case of weighted quick-union method on union-find

texts:
Here is exercise 1.5.15 in Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne.

  Show that the number of nodes at each level in the worst-case trees for weighted quick-union are binomial coefficients. Compute the average depth of a node in a worst-case tree with $k = 2^n$ nodes.

Here are my questions:

1) What is the worst-case tree for weighted quick union?

2) How I compute the average depth of a node in this worst-case tree with $2^n$ nodes?

I tried to show through induction that the number of nodes at each level for the worst-case tree in weighted quick-union are binomial coefficients (the first level has $\frac{1!}{0!(1-0)!} = 1$ node). From there I tried to think about how, generally, there are at most $\frac{n!}{r!(n-r)!}$ nodes at the next level. However, I'm unable to think of reasons as to how this makes sense.

Any help with this question is appreciated.


texts: To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$

texts:
I have done the proof until the point when $T(n) \leq cn^{\log7}$.

But when it comes to finding the value of constant $c$, I am getting stuck.

The given recurrence relation is $T(n) = 7T(n/2) + n^2$.

Since we already calculated the solution above which is $cn^{\log 7}$.

Inductive step:

Now we have to prove that $T(n) \leq c n^{\log7}$ where $c$ is a positive constant.
If we consider that the solution holds good for $n/2$ then we can prove that it works  for $n$ also:
$$T(n/2) \leq c(n/2)^{\log7}.$$
Substituting these values in the recurrence relation:

$$
\begin{align*}
T(n) &\leq 7c/(2)^{\log7} \times (n)^{\log7} + n^2 \\
     &\leq cn^{\log7}, \text{ since $7/(2)^{\log7}$  is constant so can be ignored and $cn^{\log7} \gg n^2$ for large $n$} \\
     &\leq cn^{\log7} \text{ assuming $c$ is a constant $\geq 1$.}
\end{align*}
$$

Finally to find constant $c$,

$$(7/(2)^{\log7}) \times cn^{\log7} + n^2 \leq cn^{\log7}. $$

I am not able to find appropriate $c$ for which the condition holds true.


texts: Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)?

texts:
I am approaching a problem where, among other things, I will have to repeatedly check if a point is within a (set of) polygon(s) in the 2D plane.

the polygons are either convex or star-shaped with a non-singular kernel
if multiple polygons, they touch each other (have at least a side in common with another polygon of the set)
the point moves accoring to a phisical process, so it will not "jump" in the plane, but its movement in the plane will be continuous
another system will keep the point within the area defined by the union of said polygons, but this might occasionally fail
I need to know which polygon is bounding the point
Polygons are given in advance and output of a pre-process that can be expanded

I know these solutions, in particular the "draw a line starting from your point and count the intersections" and the "sum the angles for each subsequent pair of vertices and check if it is 2$\pi$", but:

both solutions require a lot of computation if one has complex polygons and several polygons
those solutions are for the general case, where there is no dynamics involved, but a static point in a static polygon.

Is there a computationally optimal solution for the scenario I am considering? I think that leveraging the solution of the previous timestep should help in skipping/avoiding some computations in the next cycle, meaning that a "full" solution needs to be computed only at initialization.
Or am I stuck with running a full check at each cycle?


texts:
According to De Boor's algorithm, a B-Spline basis function can be evaluated using the formula:

$$ B_{i,0} =
     \left\{ \begin{array}{ll}
   1  & \mbox{if } t_i \le x < t_{i+1} \\
   0 & \mbox{otherwise}
          \end{array}
     \right.
$$

$$
  B_{i,p} = \frac{x-t_i}{t_{i+p}-t_i}B_{i-1,p}(x) +
            \frac{t_{i+p+1} - x}{t_{i+p+1}-t_{i+1}}B_{i+1,p-1}(x)
$$

where the function $B$ is defined for $n$ control points for the curve of degree $d$. The domain $t$ is divided into $n+d+1$ points called knots (in the knot vector). To evaluate this, we can define a recursive function $B(i,p)$.

The B-Spline itself is represented as,
$S(x) = \sum{c_iB_{i,p}}$.

To evaluate this, the algorithm in Wikipedia tells us to take $p+1$ control points starting from $c_{k-p}$ to $c_p$, and then repeatedly take each consecutive pair's weighted average, ultimately reducing to one point.

I find this algorithm fine for one or two evaluations; however, when we draw a curve, we take hundreds of points from the curve and connect them to make it look smooth. The recursive formula still requires up to $(p-1)+(p-2)+(p-3)...$ calculations, right? (To take the weighted averages)

In my research, however, we need to evaluate only one polynomial - since the B-Spline is ultimately composed of $p+d+1$ basis polynomials (as I'll show).

Suppose we take a knot vector $[0, .33, .67, 1]$ and control points $[0, 1, 0]$ (degree $1$), then we can represent the basis polynomials as:

$$c_0B_{0,1}= 0, \mbox{ if } 0\leq x<.25, + 0, \mbox{ if } .25\leq x < .5 $$
$$c_1B_{1,1}= 4x-1, \mbox{ if } .25\leq x<.5, + \,\,-4x+3, \mbox{ if } .5\leq x < .75 $$
$$c_2B_{2,1}= 0, \mbox{ if } .5\leq x<.75 + 0, \mbox{ if } .75\leq x < 1 $$

Now, we can flatten them to produce:
$$S(x) = \sum{c_i B_{i,1}} =
     \left\{ \begin{array}{ll}
   0  & \mbox{if } 0 \le x < .25 \\
   4x-1 & \mbox{if } .25 \le x < .5 \\
         -4x+3 & \mbox{if } .5 \le x < .5 \\
   0  & \mbox{if } .75 \le x < 1 \\
          \end{array}
     \right. $$

Now, if we were to calculate $S$ at any $x$, we can directly infer which polynomial to use and then calculate it in $d$ multiplications and $d+1$ additions.

I have implemented this calculation using explicit Polynomial objects in JavaScript. See https://cs-numerical-analysis.github.io/.

Source: https://github.com/cs-numerical-analysis/cs-numerical-analysis.github.io/blob/master/src/graphs/BSpline.js

I want to know why people don't use the algorithm I described. If you calculated the polynomial representation of the B-Spline and then flatten it out, it will be a one-time cost. Shouldn't that one-time cost be offset by remove the unnecessary recursive averaging?


texts: When do we use parallel algorithms for enumerating combinations?

texts:
I know that combination is used in many areas. But do we really need parallel version of algorithms for that? If so, where do they used?

Here is a famous example of parallel algorithms, Adaptive and Optimal Parallel Algorithms for Enumerating Permutations and Combinations by S. G. AKL.


texts:
How can you specify the "inverse" of a word, so:
let's say a word consists of a's and b's the language is:
$ww^{-1}$
the second word is the same as the first but every a is replaced by b and every b by a


texts:
$L_1=\{a^n\mid n\ge1\}$ is regular and
$L_2=\{a^{n^2}\mid n\ge1\}$ is non-regular.
We know that $L_1\cap L_2$ is regular but,
here $L_1\cap L_2=L_2$; and $L_2$ is not regular. How is this possible?


texts: Why is the throughput (performance) of the Aloha protocol ≈ 0.18?

texts:
I've read in a few places (like here that the throughput - that is, the amount of good useful messages relative to capacity - of the ALOHA protocol for networks is roughly 0.18%.

But its not clear how we arrived at that number.

Can someone explain it?


texts: Augment B+ Tree to support given search query

texts:
Given a B+ tree with M=3. We assume that the tree is static and it is not necessary to update the B+ tree. Also we know that all key-value pairs are stored in the leaves of the B+ tree. Internal nodes contain copies of keys stored in the leaves.

For simplicity we can assume that an internal node with d children holds d keys. The i-th key stored in the node u is the smallest key stored in the i-th child of u.

Now, we need to extend it to support given query named osearch(x,ef).

We are given a pointer to a leaf that holds the key $ef$ > $x$ and we search for the key $x$. Let $x−$ denote the largest key stored in the tree that is smaller than $x$. Let $df$ denote the number of elements between $x−$ and $ef$; if $x$ is smaller than all keys in the tree, then $df$ is the total number of keys that do not exceed $ef$.

Now we need an algorithm that answers queries osearch(x,f) in O(log $(df)$) time. That is, the time to answer a query osearch(x,f) must be logarithmic in the number of elements between ef and x−.

How to augment the B+ tree to answer this query ?


texts:
I have this question I found regarding n-gram modeling in the Speech and Language Processing textbook by Daniel Jurafsky:

  Suppose we didn’t use the end-symbol </s>. Train an unsmoothed bigram grammar on the following training corpus without using the end-symbol </s>:
  <s> a b
  <s> b b
  <s> b a
  <s> a a
  Demonstrate that your bigram model does not assign a single probability distribution across all sentence lengths by showing that the sum of the probability of the four possible 2-word sentences over the alphabet
  {a,b} is 1.0, and the sum of the probability of all possible 3 word sentences over the alphabet {a,b} is also 1.0.

Please can you verify that is my approach correct?


texts: Is it possible to transfer a point from one camera to another, given n corresponding points?

texts:
I have 2 images of a scene taken at one moment by two identical cameras (similar cameras intrinsic parameters) by to arbitrary locations and at two arbitrary orientations (different cameras poses).
On the images n points correspondence p_i1={x_i1, y_i1, z_i1}↔p_i2={x_i2, y_i2, z_i2}, i=1,2,...,n are given. Let for simplicity z_i1=z_i2=f for all the points.

Is it possible at any number of corresponding points n to derive a transformation relation from one camera view to another so that for an additional point p_01 known only at one image to be able to locate it on the second image p_02?

My guess is (due to the fact that projection on a camera sensor plane is 3d-to-2d) it is not possible! And at most one may find a line on the 2nd image on which the additional point could be positioned.

I know that the task is solved with a homography matrix for two cameras having one center.
I know it must be solvable for the case of all the points being coplanar.

But is it possible for arbitrary positioned cameras and arbitrary situated (non-coplanar in world frame) corresponding points?


texts: Find which vertices to delete from graph to get smallest largest component

texts:
Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component.

I assume for large $n = |V|$ and large $k$ the problem is difficult (NP-hard), but I am interested in small values of $k$ ($k \in \{1, 2, 3, 4\}$).

For $k = 1$, I think it is possible to find best vertex $\{v^*_1\}$ to remove by performing single depth-first-search of the graph (i.e., checking articulation points).

For $k = 2$, it would be possible to find best vertices $\{v^*_1, v^*_2\}$ by performing $n$ depth-first searches (each of them for graph $G_i = G / \{v_i\}$). A similar approach could be applied in the case $k > 2$.

I wonder if there is any better solution than that.

(Related: counting the minimum number of vertices without necessarily enumerating them)


texts: Are all partial functions partial computable?

texts:
If we have some function $f\colon \mathbb{N} \rightarrow \mathbb{N}$ that is not total, i.e. for some values $x \in \mathbb{N}$, $f(x) = {\perp}$, is $f$ always partial computable? By partial computable I mean there exists a program that $f(a)$ is defined for $a \in \mathrm{dom}(f)$ and $f(a)$ is not defined for $a \notin \mathrm{dom}(f)$.

I expect that this isn't the case but cannot come up with a counter example.


texts:
In Extended Backus-Naur Form (EBNF) there is one form called a "special sequence" which is surrounded by questions marks ?...?

What does this mean?


texts:
There is a lot of information online on this specific topic, but I still don't quite understand how to delete elements from a B-tree.

For example, given the following tree, how would we delete 26 and 63?

Is there a general approach?


texts: What is the knowledge required to understand the formal definition of a Turing Machine?

texts:
As a computer science student I consider is essential to completely understand how a Turing machine is defined.

What mathematical knowledge is required in order to understand the formal definition of a Turing Machine, as explained in this Wikipedia link.


texts:
Suppose we have the following schema:  Drinkers(name, addr, phone, beersLiked)

Also suppose $\text{name} \twoheadrightarrow \text{phone}$. Consider the following tuples:

 Sue a p1 b1

 Sue a p2 b2

What other tuples must also be in  Drinkers ? Would it be:

 Sue a p2 b1

 Sue a p1 b2


texts: What can be said about the given language?

texts:
$L = \left \{ ab^{n}a^{n}|n>0 \right \} \bigcup  \left \{ aab^ka^{2k} | k>0 \right \}$

What can be said about the given language L ?

According to me, I think it is CFL and not DCFL as I tried to somehow parse it through a NPDA but not sure though.


texts: Reasons for choosing register number and address sizes in an Instruction Set

texts:
Why would it be suitable to design an instruction set  with 2-bits allocated for the register number and 10-bits allocated for the memory address? Would introducing a cache change this? (If possible I'd like to know why or where to find an explanation on this.)

If it helps an example would look like this 0001 xxyy yyyy yyyy and an instruction would be the opcode 0001 (Load) register xx from memory address yy yyyy yyyy.


texts: From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

texts:
I am reading one of Guido van Rossum's essays on optimization in Python.

We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward algorithm.

def f3(list):
    string = ""
    for character in map(chr, list):
        string = string + character
    return string

Guido claims that the following algorithm avoids the quadratic behavior in the string concatenation.

def f5(list):
    string = ""
    for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
        s = ""
        for character in map(chr, list[i:i+16]):
            s = s + character
        string = string + s
    return string

How does this actually help and what is the significance of the value 16 in f5?

f5 does not actually turn out to be faster, but I want the intuition that went into trying this strategy of optimization.

Note: we can assume that we are working with a list of length exactly 256.


texts: Pumping Lemma: is it valid to "multiply the product of powers" in this case?

texts:
I need to show that

$\qquad \displaystyle S = \{(10^p)^m \mid p \geq 0, m \geq 0\}$

is not a regular language using pumping lemma.

Can I multiply the product of the powers and express it to: $S = \{ 1^m 0^{pm} \mid \dots \}$ and apply the pumping lemma where I pump 1's then say that the language doesn't accept the new string?


texts: Where does the FLP impossibility proof depend on allowing a single process failure?

texts:
Question
I'm reading the FLP impossibility paper.
I think I understand the idea of the proof, and I don't have questions about it.
However, it seems like the assumption of having at most, a single faulty process is not used in the proof.
Put another way, if we remove this assumption and forbid process failure, the proof still seems to hold.
This can't be correct, because then it wouldn't be possible to construct a protocol that succeeds with no faulty processes.
However, it is possible, and a protocol meeting this criterion is supplied in section 4.
My question is therefore: which part of the proof relies on the condition that one process can fail?
My best effort at an answer
Definitions
For reference, the assumption in question appears in the definition below:

A run is admissible provided that at most one process is
faulty and that all messages sent to nonfaulty processes are eventually received.

Also relevant is the definition of a deciding run:

A run is a deciding run provided that some process reaches a decision state in
that run.

I'll also use my own definition, below:

A run is 0-admissible provided that no processes are faulty and that all messages sent to nonfaulty processes are eventually received.

Approach
I want to show that, by changing the definition of admissible to that of 0-admissible, the proof is no longer correct. Therefore, it would rely on the at most one failure part of the admissible assumption.
Lemma 2
Lemma 2 ("P has a bivalent initial configuration") references this assumption. In particular:
$C_0$ and $C_1$ are $0$-valent and $1$-valent initial configurations, respectively. They differ only in the initial value $x_p$, of a single process $p$.

Now consider some admissible deciding run from $C_O$ in which process $p$ takes no steps, and let $\sigma$ be the associated schedule.
Then $\sigma$ can be applied to $C_1$, also, and corresponding configurations in the two runs are identical except for the internal state of process $p$. It is easily shown that both runs eventually reach the same decision value. If the value is $1$, then $C_0$ is bivalent; otherwise, $C_1$ is bivalent.

Both cases above being a contradiction, proving the lemma.
Replacing admissible with 0-admissible in Lemma 2
I'd hoped that replacing admissible with 0-admissible would show the proof no longer works.
For simplicity, I'll only consider the case where $N = 2$.
Now consider the (modified) line of the proof:

Now consider some 0-admissible deciding run from $C_O$ in which process $p$ takes no steps.

0-admissibility implies the following:

Process $p$ cannot be faulty
Process $p$ must have received all messages sent to it
A decision state is reached

By non-triviality, the schedule $\sigma$ must not initially be in a deciding state.
Now, we know from (1) and (2) that no messages can have been sent to process $p$: Either it would have taken steps to receive them (violates assumptions), or it didn't receive them (violates 0-admissibility).
Therefore, we can ignore process $p$ and focus on the remaining process. I had assumed that it being deterministic implies the configuration must be univalent, but I can see a problem.
Namely, the deterministic process can introduce nondeterminism by sending a message to itself, and measuring the time taken to receive it. This effectively generates a random integer, which can be used to randomly choose an answer.
Even if it were right, this seems like a very complex answer to a simple question - have I missed something obvious? Is there another part of the proof where the assumption of faultiness is required more explicitly?


texts: Every regular language has a finite index

texts:
For a language $L$ over an alphabet $\Sigma$, we say that two words $v,w \in \Sigma^*$ are equivalent, denoted $v\sim w$, if for every word $z \in \Sigma^*$, $vz \in L$ iff $wz \in L$. We define $[w]_L$ to be the equivalence class of $w$ under this relation. The index of $L$ is the number of equivalence classes of strings in $L$.

How can I prove that every regular language has a finite index?
can I use the Myhill-Nerode theorem?

I tried to use the fact that if $\delta^*(v) = \delta^*(w)$ then $v \sim w$.


texts: Why do heuristic functions only approximate the real value of the cost?

texts: As stated in the title I'm wondering why do heuristic functions only approximate the real value of the cost? I understand it can never overestimate, but can it ensure the cost is accurate?


texts: Partition of a set of integer into 3 subsets of approximately equal sum

texts:
I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes:

"A hard working mom bought several fruits with different nutritional values for her 3 kids, Amelia, Jessica and Bruno. Both girls are overweight, and they are very vicious and always leave poor Bruno with nothing, so their mother decided to share the food in the following manner:

Amelia being the heaviest one gets the most amount of Nutritional Value.
Jessica gets an amount equal or less than Amelia
Bruno gets an amount equal or less than Jessica, but you need to find a way to give him the highest possible nutritional value while respecting the rule ( $A \geq J \geq B$ )"

One of the test cases given by my teacher is the following:

The fruit list has the following values { 4, 2, 1, 8, 11, 5, 1

Input:
7   -----> Number of Fruits
4 2 1 8 11 5 1 ----> Fruits Nutritional Values

Output:
1 11  ---->  One fruit, their nutritional values sum for Amelia
5     ---->  Position of the fruit in the list
3 11  ---->  Three fruits, their nutritional values sum for Jessica
1 2 6 ---->  Position of the fruits in the list
3 10  ---->  Three fruits, their nutritional values sum for Bruno
3 4 7 ---->  Position of the fruits in the list

Note: I am aware that there are several ways of diving the fruits among the kids, but it doesn't really matter as long as it follows the rule $A \geq J \geq B$.

I'm trying to make a program in C# that solves this kind of problems but I need an efficient formula to make this work. Generating all the subsets is out of the question because it is very consuming task. The list of fruits can have up to $50$ elements, $2^{50}$ is a huge number.


texts: The 0-1 Knapsack problem - Regression equation

texts:
I'm trying to figure out the regression equation for the 0-1 Knapsack problem recursive algorithm:

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
   // Base Case
   if (n == 0 || W == 0)
       return 0;

   // If weight of the nth item is more than Knapsack capacity W, then
   // this item cannot be included in the optimal solution
   if (wt[n-1] > W)
       return knapSack(W, wt, val, n-1);

   // Return the maximum of two cases:
   // (1) nth item included
   // (2) not included
   else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
                    knapSack(W, wt, val, n-1)
                  );
}

What I have is only the answer but I don't really know how to get to it:

T(n) = 2T(n) + O(1) = O(2^n)

Any ideas?


texts: Is 95% of code really non-semantic fluff?

texts:
According to A Study of Wheat and Chaff in Source Code, 95% of code is "chaff", or "non-core functionality", whatever that means. Is this really a sensible study? Does the IT World article correctly represent the original paper? It's hard to believe 95% of the code I write is "non-core". Maybe an example would help.

The original paper is A Study of “Wheat” and “Chaff” in Source Code by Martin Velez, Dong Qiu, You Zhou, Earl T. Barr and Zhendong Su.


texts:
Which of the following modes of data transfer is the fastest?

a. DMA

b. Interrupt-based

c. Polling

d. All are equally fast

I do not have the answer, so I cannot check, that's why I am posting here.

I think the answer is D. All are equally fast. In all data transfer cases the speed of data transfer is same, but in case of DMA we save CPU time by that we improve the efficiency of CPU since data transfer job is done by DMA. Is my understanding correct ?


texts: How to express complexity of two functions considering it is the same in big O notation

texts:
I have two functions. a and b.
Both have linear complexity O(n).
fcn a (items)
    loop items -> item
        ...

fcn b (items)
    loop items -> item
        ...

    loop items -> item
        ...

    loop items -> item
        ...

Though b obviously takes 3 times longer to run than a for the same input.
Is there any other notion / technical way to express the difference?
Or is it normal to say "it takes 3 times longer but still O(n) in time so w.e, let's move on"


texts: Joint typicality and distance between the vectors

texts:
In the book by Cover and Thomas,the author says that

We first review the single-user Gaussian channel studied in Chapter 9.
P
Here Y = X + Z. Choose a rate R < 12 log(1 + N
). Fix a good ($2^{nR}$ , n)
codebook of power P . Choose an index w in the set $2^{nR}$ . Send the
wth codeword X(w) from the codebook generated above. The receiver
observes Y = X(w) + Z and then finds the index ŵ of the codeword
closest to Y. If n is sufficiently large, the probability of error Pr(w $\neq$ ŵ)
will be arbitrarily small. As can be seen from the definition of joint typ-
icality, this minimum-distance decoding scheme is essentially equivalent
to finding the codeword in the codebook that is jointly typical with the
received vector Y.

I am unable to mathematically see how $(X^n,Y^n)$ being jointly weak typical implies that distance between $X^n$ and $Y^n$ is smaller  than other possible $X^n$ with which $Y^n$ is not typical? The author had proved the capacity using jointly weak typicality.
To be more exact, can someone please how vectors $(x_1^n,y^n)$ chosen IID from $P_{XY}$  staisfying the first condition satisfies the second:
$$ \frac{-1}{n}\log \Pr{(x_1^n,y^n)}  \approx H(X,Y)$$
$ dist(x_1^n,y^n) < dist(x_k^n,y^n) \forall x_k^n \neq x_1^n$ and $x_k \sim P_X $
The second condition is the minimum distance condition. $dist()$ can be any valid measure I guess.


texts: How can I make my algorithm more efficient?

texts:
I came across an algorithmic problem. I do not know how to do it optimally.
The problem is as follows:

There is an increasing array $A$ of size $n_1$

There is an array $M$ of queries of size $n_2$
where $1 \le n_1, n_2 \le 10^7$

For each query element $m \in M$, it is required to find the count of elements in array $A$ that are strictly less than the query element $m$.
For example:

$A = [1,2,3,5]$
$M = [4,2]$
for $m = 4$ answer $3$
for $m = 2$ answer $1$

My idea works for a $O(nlogn)$. The algorithm is simple; for each request I do a binary search in array $A$. But can it be faster? Maybe B-tree?


texts: Can there be a context-sensitive pumping lemma?

texts:
A "pumping" property (words of a certain length imply the existence of loops in the language-defining mechanism) are known to exist for regular and context-free languages and a few more (usually used to disprove a language's membership to a certain class).

Within the discussion around this question, Daisy's answer suggests that there can't be a pumping lemma for context-sensitive languages - since they're so complex.

Is that true - can it be shown that there can't be some type of pumping property - and is there a good reference for that (or against that)?


texts: Words generated by CFG whose parse tree contain even number of $X$

texts: Let $G$ be a context-free grammar with set of terminals $A$. Let $X$ be a non-terminal in $G$. Is the language of words over the alphabet $A$ with a syntax tree in which the non-terminal $X$ appears even number of times is context-free?


texts: Can smart recursive search find all optimal solutions for Closest String?

texts:
Consider the Closest String problem:

  Input: Strings $s_1, \dots, s_m \in \Sigma^n$ and $k \in \mathbb{N}$.

  Question: Is there $s \in \Sigma^n$ for which $d_H(s, s_i) \leq k$
    for all $i \in [1..m]$?

We denote with $d_H$ the Hamming distance,
a string metric.

Since this is an NP-hard problem, no efficient algorithm is known. One non-trivial
approach is this:

Choose $s \leftarrow s_{i_0} \in \{s_1, \dots, s_m\}$ arbitrary.
Let $d \leftarrow k$.
If $s$ is a (feasible) solution, stop and answer "yes".
If $d < 0$ or $d_H(s, s_i) > k + d$ for some $i \in [1..m]$, stop and answer
"no".
Else, pick any $s_j$ with $d_H(s,s_j) > k$.
Pick indices $P \subseteq \{ i \mid s[i] \neq s_j[i] \}$ with $|P| = k+1$.
Recurse (i.e. branch and go to step 2) on
$s \leftarrow s[1] \cdots s[i-1] \cdot s_j[i] \cdot s[i+1] \cdots s[n]$ and
$d \leftarrow d-1$
for every $i \in P$; answer with the logical disjunction over the answers.

One can show that this (abstract) algorithm solves Closest String in time
$O(mn + nk \cdot k^k)$ (in the uniform RAM model).

Now, if $k$ is chosen minimally, the algorithm clearly constructs an optimal
solution along the way. The question then is: considering the non-determinism
in steps 1, 3 and 4, can the algorithm find every optimal solution?

Note how the algorithm stops whenever it encounters a feasible solution, so
some solutions are "hidden" behind feasible ones -- of course, we do not explore
the whole search space. For instance, on $(\{000,111\}, 2)$ the algorithm finds
some optimal solutions only starting in $000$, others only from $111$ --
but all can be found.

Are there instances for which some optimal solutions hide "in the middle"? Formally,

$\qquad\displaystyle \exists w \in \mathrm{Opt}\
                     \forall s_i\
                     \exists w' \in \mathrm{Opt}.\
                     d_H(w', s_i) < d_H(w, s_i)\quad$?

I have tried proving the opposite without success. In particular, we know that
every optimal solution has to have distance exactly $k$ to at least one input
string; combining several such pairs using the triangle inequality
led me nowhere.
Needless to say, I have not been able to come up with an example of "hidden" optimal
solutions, either.

So which is it? Can above algorithm (non-deterministically) enumerate all optimal
solutions, or can there be hidden ones?


texts:
Func5(n)
1 s=0;
2 i=6;
3 while (i < n^(5/2)) do
4    j=4;
5    while (j < 5i) do
6        s=s + i - j;
7        j=j + 9 ;
8    end
9    i=4 * i ;
10 end
11 return (s);

So far I got the upper bound for this function is O(n^(5/2)log(n)) and I am not sure if or not this is the closest upper bound we can get. And I have no clue how to show the lower bound with the same function.


texts: Using amplification lemma to decrease error probability gives 0 as divisor

texts: I am attempting to work through an example of how to select an error bound, and then determine the number of simulations necessary by the amplification lemma to obtain the desired error bound. I have probabilistic Turing machine $M$ with an error probability of $.5$. I'd like an error bound of $.25$, so I will bound the error probability by $2^{-t}$, where $t=2$. According to my textbook, I need to choose a $k$ such that $k \ge t/f$, where $f=-log_2(4e(1-e))$, where $e$ is the error probability. As $M$ has an error probability of $.5$, $e=.5$. Substituting into the equation gives: $-log_2 (2(.5))=-log_2(1)=0$. The problem is when I go to select a $k$ such that $k \ge t/f$, I get $0$ as a divisor. Are there other restrictions on the calculation? Or, am I just doing something wrong?


texts: Is there a way to test if two NFAs accept the same language?

texts: Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA.  If I do a search through every path of the NFA, will that work?  Although that will take a long time.


texts: Karatsuba multiplication on numbers with odd length

texts:
I am learning about Karatsuba-Ofman multiplication. I don't quite understand how to multiply two numbers with odd length.

Let's take two 3-digit numbers $a = 234; b = 857$ with base $B = 10$ and length $n=3$.

The first step is to split split $a$ and $b$ at position $n/2$. However, since $n=3$ where do I split it? Does it even matter?

Later in the algorithm I have to multiply $((a_1 + a_0) \cdot (b_1 + b_0) - (a_1 \cdot b_1) - (a_0 \cdot b_0)) \cdot B^{n/2}$. Would that mean, with $n=3$, I have to multiply by $B^{1.5}$?


texts: Trouble understanding how to create a grammar parse tree

texts:
I'm starting an online Computer Science class called Advanced Programming Languages, and the book asks me to create a parse tree and generate a grammar from it.  Here are the exact instructions:

  To verify that a string of characters belongs to a language defined by a grammar, we must create a parse tree that shows that the string can be generated by the grammar.

<list> -> <item> , <list> | <item>
<item> -> <left> <item> <right> | <left> <right>
<left> -> A| B | C
<right> -> x | y | z

  Choose a string that is in this language and create a parse tree that demonstrates that your claim is true. Identify another string that contains some of these terminals symbols but is not in the language.

I think I know how to get started, but I keep getting confused by examples in the book and examples online.  Is there a general method to use when approaching this?

I began it this way:

            <list>
         /          \
      <item>      <list>
    /    |    \
<left> <item> <right>
  |    /
  A  <left>

But I get confused on the next iterations of the item.  Any hints?


texts: Regular Expression and NFA: each block of five consecutive symbols contains at least two 0's

texts:
Consider the alphabet {0, 1}. How do I find the regular expression for the set of all strings such that each block of five consecutive symbols contains at least two 0's?
Here, by block I mean a given set of concurrent substrings. For example, for a string "0011010", the first five characters are "00110", which satisfies the above condition. The next block leaves out only the first character of the given string, giving me "01101", which again satisfies the condition.
I also need help in converting the regular expression into an NFA.


texts: Difference between Lamport timestamps and Vector clocks

texts: Lamport timestamps and vector clocks sound like almost the same thing. Both are used to determine the order of events in a distributed system. What are their key differences?


texts: Why is discrete mathematics required for data structures?

texts:
Data Structures is the second CS course taught at Columbia University and it lists Discrete Mathematics as a Co-Req.

I have a BSEE and have not taken any discrete mathematics and am having a hard time understanding why I need to take this to do things like create data structures?

Is this just so the university can cram useless info in my head and make more money, or is there a real relation to discrete math and data structures?


texts:
Consider the searching problem:

Input: A sequence of $n$ numbers $A=(a_1, a_2, \ldots , a_n)$ and a value $v$.
Output: An index $i$ such that $v = a_i$ or the special value NIL if $v$ does not appear in $A$

Write pseudocode for linear search, which scans through the sequence, looking for $v$. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
The algorithm is clearly very simple to prove. However could someone prove the correctness of the algorithm using a loop invariant? Note the "three necessary properties" are:

Initialization: It is true prior to the first iteration of the loop.

Maintenance: If it is true before an iteration of the loop, it remains true before the

Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.


texts:
I am doing a problem on fixed parameter tractability where in we are given a graph G=(V,E), and an integer k, and the k-clique edit problem asks whether there exists a set U i.e a subset of V such that G-U is a clique and I need to show that the k-clique edit problem is FPT.

Now as far as I could think of , this problem can be solved using vertex cover.First I try for k=1,and thus X a subset of V is a clique. Now if I take the compliment graph G' and try for k=1, then V-X is a vertex cover. Now the problem is how do i go about phrasing the answer. I know the concept behind the problem, but I am struggling with writing it properly.


texts: How to prove that this defined language is regular?

texts:
Suppose that $L$ is a regular language and $0<\alpha<1$ and $\alpha \in Q$. Define $L_\alpha$ as

$$L_\alpha = \{\omega \in \Sigma^* \mid \exists \omega_1 \in  \Sigma^* .\omega\omega_1 \in L,\frac{|\omega|}{|\omega\omega_1|}=\alpha\}$$

How do I prove that $L_\alpha$ is regular?

Here is my attempt. If we assume that $D$ is the automaton that recognize $L$ with $Q=\{q_0,...,q_n\}$, if $\delta(q_0,\omega\omega_1)\in F$ and $\delta(q_0,\omega)=q_i$  we can define  $D_1$ such that $\delta_1(q_0,\omega)=r_{i-1}$ (for $r_i \in F_1)$, but the problem is I can't define $\delta_1(q_0,a) $for $a\in \Sigma$.


texts: Conway's Game Of Life Problem Parallel (OpenMP)

texts:
I am currently working in solving Conway's Game Of Life problem for a Parallel and Distributed Computing course.

The problem is a little bit different form the original, in the sense that instead of having a 2D representation of the cells we have a 3D one, each cell is represented by three ints. When considering neighbours, only the x + 1, x - 1, y + 1, y - 1, z + 1 and z - 1 are considered (no diagonals).

The input of the problem is constituted by the size of the cube (size) where the cells are present, followed by a list of  positions of live cells.

The number of cells, is in the order of O(size^2), and the space is in the order of O(size^3).

My current implementation uses C++ maps, in which a key is a tuple with x, y and z, and the value is an integer telling in that position the cell is alive or not. My current approach is to just go through every position available in the cube and check the number of neighbours and update that position accordingly, but i believe this is not ideal because the number of live cells is in the order of O(size^2) and not O(size^3).

My question is how would you improve this solution ? Is there a better data structure to use ? Considering that I have to build an OpenMP implementation (shared memory) for very large input cases (size > 10000).

Thank you !


texts: Find Number of even subarrays $O(n)$ [explanation needed]

texts:
So I found a solution to this problem here http://marcodiiga.github.io/number-of-even-sum-subarrays but I am unsure of exactly how it works. I get the premise that in order to have an even sum it must be even or even + even or odd + odd. However, I am not sure how this person manages to take into account the fact that these subarrays need to be contiguous and how just tracking the number of cumulative sums that are even/odd as you iterate through the array is good enough

Outlining his algorithm:

initialize sum, odds to 0 and evens to 1.
iterate through the array.

at each index i, do sum = (sum + A[i]) % 2

if sum is 0, increment evens, else increment odds

Lastly, return (evens * (evens - 1) / 2) + (odds * (odds - 1) / 2)

The algorithm works... I just have no idea how.


texts:
Forgive the naïveté that will be obvious in the way I ask this question as well as the fact that I'm asking it.

Mathematicians typically use $\exp$ as it's the simplest/nicest base in theory (due to calculus). But computers seem to do everything in binary, so is it faster on a machine to compute 2**x than Math::exp(x)?


texts:
I did study applied math and dealed almost exclusively with the creation of ode/pde solver code. Now, I want to increase my knowledge in some aspects and I want to learn some basic algorithms like A*, MinMax, ... (not limited to searching; I am also interested in the basics of optimization and machine learning) and their implementation.

Is there a good resource (book, online course) available for me to learn this from? Any help is appreciated. I have no other CS-related background except my math degree.


texts:
Let $a\uparrow^{n} b $ denote the indexed version of Knuth's up-arrow notation ($a \uparrow\uparrow \dots \uparrow b$ with $n$ arrows), with $a, b, n$ positive integers.

Is there a generalized algorithm to compute $a\uparrow^{n} b$ modulo a prime efficiently? How does the complexity of such an algorithm depend on $n$? What if we restrict $a$ and $b$ to also be prime, or if we remove the requirement for $p$ to be prime?


texts:
Hopefully this is the right section. I need to prove that $2^{(log(n)^{1/2})}$ is $O(n^a)$. From the basic principle of Big-O notation, I know I need to find two numbers $c$ and $N$ so that $f(n) \le c\cdot g(n)$ for all values of $n \ge N$. In this case, $f(n)$ is $2^{(log(n)^{1/2})}$, and $g(n)$ is $n^a$.

The first problem in the set had me prove that $2^{n+a}$ is $O(2^n)$. For this problem, I had separated the $f(n)$ to $2^n \cdot 2^a$. I was guided by another user to set $c = 2^a$. This way, with $g(n) = 2^n$, $cg(n) = 2^a2^n$, which is obviously $\ge f(n)$, $2^{n+a}$, for all values of $n \ge 0$. This problem, however, I don't find as easy.

Could someone point me in the right direction? I've been trying to rearrange the problem and solve it for a while now.


texts:
As far as I understand, the structure tensor is:

$$
M = \sum_{(x,y) \in W} \begin{bmatrix} I_x^2 & I_xI_y \\ I_xI_y & I_y^2 \end{bmatrix} =
\begin{bmatrix} \sum_{(x,y) \in W} I_x^2 & \sum_{(x,y) \in W} I_xI_y \\ \sum_{(x,y) \in W} I_xI_y & \sum_{(x,y) \in W} I_y^2 \end{bmatrix}
$$

How do I compute $I_x^2, I_y^2, I_xI_y$. I used Hadamard product for compute $I_x^2, I_y^2, I_xI_y$. But if I use Hadamard product, I will get $\det(M) = 0$. I'm stuck in here for too long. Can anyone help?


texts: Greedy algorithm for even item distribution

texts:
I have this problem where I need to design a greedy algorithm. The problem is as follows:

A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply $c_i$ of chocolates. Furthermore, the factory would like to have the same amount of chocolate in each store. Therefore, they hired a truck driver to haul chocolates between the stores, but the driver eats two chocolate bars for each kilometer he drives.

Calculate the largest amount of chocolate $C$ they can have at each store.

Input: The position $p_i$ and chocolate supply $c_i$ of each store. The positions are in increasing sorted order.

Output: The largest amount $C$, such that each store can have a chocolate supply of at least $C$ after the truck driver has hauled between the stores.

I have a problem with identifying the greedy choice property for the problem. So far I came up with the following:

The greedy choice can be the minimum arithmetic mean of two neighbouring stores minus the delivery cost divided by $C$, but it has to be larger or equal to 1. I came up with the following equation:
$$\min\{\frac{\frac{1}{n} \cdot (c_i + c_{i_{neighbour}} - delivery_{cost})}{C}\}$$

Where the delivery cost is $2\cdot |p_i - p_{i-1}|$.

I am not sure if this approach is the right one. I am open for hints and partial solutions.


texts:
Suppose P vs. NP is independent of ZFC. Then there cannot be an efficient SAT solver, otherwise it would constitute a proof for P = NP. Therefore P $\ne$ NP.

What we see here is that independence implies unequality. So why is independence a big deal? It is just one way to show P $\ne$ NP. See Scott Aaronson's paper Is P Versus NP Formally Independent?.


texts: Role of computational power in recent AI developments

texts:
Today Google's AI won its first game of Go against Lee Sedol, one of the best Go players on the planet. Image interpretation and self-driving cars are other recent success stories in machine learning. I was under the impression that these advances are largely the result of better algorithms and novel ideas, but some of the guys in my university were claiming these advances are mainly due to increased computational power. Neural networks in particular are an old concept that was largely forgotten for decades and now we're doing all sorts of cool new things with it.

What is the role of computational power with regards to recent successes in artificial intelligence?


texts: Sublinear Homomorphism Property Testing Counter Example

texts:
This is a homework question, so I'm not looking for answers, just general guidance.

I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of homomorphisms from $\left(\mathbb{Z}_{n}, +\right)$ to $\left(\mathbb{Z}_{n}, +\right)$ (where + is the modulo addition) in particular.

Since $$f:\mathbb{Z}_{n}\to\mathbb{Z}_{n}\ is\ a\ homomorphism\iff\forall x\in\mathbb{Z}_{n}:\ f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$$
(I've managed to prove that), it is suggested to property test $f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$.

To counter that suggestion it is said that for a sufficiently large $n$, $$f:\begin{array}{lll}
\mathbb{Z}_{n} & \to & \mathbb{Z}_{n}\\
x & \mapsto & x\ \left(mod\ \left\lceil \sqrt{n}\right\rceil \right)
\end{array}$$ maintains $f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$ for $1-\frac{1}{\sqrt{n}}$ fraction of the $x\in\mathbb{Z}_{n}$ (managed to prove that), but that $f$ is $1-\frac{1}{\sqrt{n}}$-far from any homomorphism (where $\epsilon$-far means that in order to get a homomorphism out of $f$ we have to change at least $\epsilon n$ outputs of $f$).

We're asked to show a counter example of a function that passes the test for $1-o\left(1\right)$ fraction of the inputs, but is $\frac{1}{100}$-far from homomorphisms, which is a bit easier.

So I wanted to show $f$ as my example. I managed to prove what I wrote so far, but I'm still trying to prove $f$ is $1-\frac{1}{\sqrt{n}}$-far.

What I've tried:

Assume by contradiction that $\delta\left(f\right)<n-\sqrt{n}$ (where $\delta\left(f\right)$ is the distance from homomorphisms), that is there exists $h$, an homomorphism, with less than $n-\sqrt{n}$ different (compared to $f$) outputs.

I've divided into 2 cases.

First case is $h\left(1\right)=f\left(1\right)$ which means $h\left(1\right)=1$. It is easy to get a contradiction this way, since then there exists $x>\sqrt{n}$ such that $h\left(x\right)=f\left(x\right)$ (otherwise, contradiction to $\delta\left(f\right)<n-\sqrt{n}$). Since $h$ is a homomorphism, we get $$h\left(x\right)=\underset{i=1}{\overset{x}{\sum}}h\left(1\right)=\underset{i=1}{\overset{x}{\sum}}1=x\neq f\left(x\right)$$

Now the other case where $h\left(1\right)\neq f\left(1\right)$ is where I'm stuck. It's hard for me to get intuition since apparently this is only true for large $n$'s, which makes it hard to look at basic examples. I'm not even sure dividing to these cases is the best approach, and would love some help. Thanks!

Edit:

As requested, a link to the survey by Ronitt Rubinfeld.
Only managed to find it in ps format.


texts: Using substitution method to prove asymptotic lower bound of $T(n) = T(n-1) + \Theta (n)$

texts:
I try to prove that the asymptotics of the recurrence
$
T(n) = T(n-1) + \Theta (n)
$
is
$
T(n) = \Theta(n^2)
$.

By $\Theta$, I mean tight bound from above and below.

I can write the equation like this:
$$
T(n) = T(n-1) + \Theta (n) = T(n-1) + cn.
$$

I'm having a hard time proving the lower bound with this method, do you have any idea how?

What I did for Upper bound is:

Assume:
$$
T(n-1) \leq c(n-1)^2, \quad c \in R
$$

Therefore:
$$
T(n) \leq c(n-1)^2 + cn = cn^2 - 2cn + c + cn = cn^2 - cn + c \leq cn^2
$$

Therefore I get:
$$
T(n) \leq O(n^2)
$$

For $O$, by which I mean just an upper bound.

So, how do I prove a matching lower bound using this method?


texts: Relative vertex capacity in max flow algorithm

texts:
I am designing a network for a max flow and would appreciate the following feature:

Say there is a flow incoming to a vertex. I would like to consume some specified amount of that flow and let through the rest. Unlike vertex capacity, which says "let though at most N units of flow", I need to "let through everything but N units of flow".

An example:

Vertex of relative capacity 10
Incoming flow = 15. Outgoing flow will be 15 - 10 = 5.
Incoming flow = 10. Outgoing flow will be 10 - 10 = 0.
Incoming flow = 5. Outgoing flow will be 5 - 10, which is less than 0, so 0.

Does such a feature exist? And if yes, which edges/vertices/edge capacities do I need to add/remove/modify and how?

Thanks a lot!


texts: Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?

texts:
Pure Prolog (Prolog limited to Horn clauses only) is Turing-complete. In fact, a single Horn clause is enough for Turing-completeness.
However, pure Prolog is incapable of expressing list intersection. (Disequality, dif/2, would allow it to do it, but dif/2 is not Horn, unlike equality).
This seems like a paradox, at first glance. Is there a simple explanation?


texts:
Given a sequence of pairs $(a_1, b_1), (a_2, b_2), ..., (a_n, b_n)$ such that $a_1 \le a_2 \le ... \le a_n$ (i.e, sorted in ascending order by $a$'s), we solve the longest increasing subsequence problem for $b$'s. Now suppose the length of the longest increasing subsequence is $X$.

If we now sort the initial sequence by the second component and solve the LIS problem for $a$'s, is the length of this sequence also equal to $X$?

Intuitively I think this is true, but I don't know if it really is.


texts: How to prove that $n$ sets have maximum of $2^n-1$ disjoint subsets when you have operations $\cup , \cap , \setminus$?

texts:
I just found out that you can have $2^{2^n-1}$ different subsets, made from $n$ sets, using operations $\cup , \cap , \setminus$.

That is because when $n=2$, for example, you have 3 disjoint subsets: $A\setminus B, B\setminus A,A\cap B$ and then you can union those things together in $2^3-1$ different ways (plus the empty set) to get $8$ different unequal sets.

My question is, how to prove that the number of those disjoint subsets is $2^n-1$.

Pictorial definition of what disjoint subsets are:

In the picture above I have enumerated disjoint subsets of $2$ and $3$ sets. As you can see their number is $2^n-1$.


texts:
I am reading Chapter 8 NP-complete problems in  Algorithms by Dasgupta et al and looking at some questions at the end of the chapter.
My own questions are below (after the image with the textbook questions). Note that I am not asking what the solutions are (those may be for separate questions) but rather the approach that makes the solutions right compared to what is in the chapter. My confusion  is in the difference between reductions and generalizations.

In the questions above, we are saying that a special case of any of the problems above are NP-complete complete. This seems like a misnomer though. Shouldn't this be a specialization rather than a generalization?

Another part of my confusion is how these so-called generalizations compare or contrast to reductions. Are we saying that some (special) version of a problem is NP-complete and therefore all the other instances are NP-complete? I thought that we needed to show that all instances of the problem are the NP-complete problem.

Regarding the direction of reductions: we reduce from a NP-complete problem (the hard problem) to the problem that we have at hand. For example, in the reduction from 3SAT to independent set we reduce from 3SAT that we know is NP-complete to what we have at hand, the independent set - did I misunderstand? Are these reductions generalizations? I thought that they were for all instances of the independent set.

Are generalizations reductions?


texts: Is the class of non regular languages is closed under complementation?

texts:
This is the question I am asked and I am currently proving it using proof by contradiction something like this:

Let's take some language L which is non regular.
Let's assume compliment of L i.e. $(L^c)$ is regular.
Since we know that regular languages are closed under complementation, complementation of $(L^c)$, i.e. $(L^c)^c$ must be regular.
Now  $(L^c)^c$ is  $L$ means $L$ is regular which contradicts the assumption.
So, our assumption that $L^c$ is regular must be false.
Hence, we can prove that $L^c$ is not regular.

Is this a correct approach to deduce?

Using same result I have to state true/false for the following two statements and support by giving proof.

The class of non regular languages is closed under union.
The class of non regular languages is closed under intersection.

How do I solve these two statements using the result above? Any hints would be helpful.

Thanks.


texts:
I am working on the following exercise:

  Consider an undirected complete graph $G(V,E)$ and positive real numbers $a_1,a_2,\ldots,a_n$. The task is to find a MST with respect to the edge weights $w_e = a_ia_j$ for each $e = \{i,j\}$. Provide an algorithm that solves this problem that is as efficient as possible.

It is safe to say that just using Kruskal's or Prim's algorithm will not be sufficient here. So we should use the special structure of $w$. I came up with the following idea:

Sort the edges in increasing order according to their edge weights. This can be done in $\mathcal{O}(\lvert E \rvert log(\lvert E \rvert))$ time.
Traverse the edges, starting from the smallest and add it to $T$ if it contains an unvisited vertex. Mark the newely visited vertices. This can be done in $\mathcal{O}(\lvert E \rvert)$ time.

But  this algorithm is not as efficient as possible for it has $\mathcal{O}(\lvert E \rvert log(\lvert E \rvert))$ time complexity. The problem here is the
procedure in step 1. Could we somehow leave it out?


texts: How to convert two conflicting objective functions into a single objective function

texts:
I have two objective functions say f1 where I have to minimize (X+Y) and another function f2 where I have to maximize (A-B). The two functions are conflicting.

I need to convert them into a minimization problem involving one single objective function using the weighed sum approach where the final form would become f3 = Min {uf1 (+ or-) vf2} where u+v=1.

I am not sure what would be the sign before vf2 ? I wonder if it should be f3 = Min {uf1 + vf2} or f3 = Min {uf1 - v*f2}.

Thanks in advance.


texts: Proof that multi-armed bandit optimization has exponential regret if loss function is general

texts:
I was reading Robert Kelinberg's paper on Nearly Tight Bounds for the Continuum-Armed Bandit Problem
There is a section where he says:

"For a d-dimensional strategy space, any multi-armed bandit algorithm must suffer regret depending exponentially on $d$ unless the cost functions are further constrained. (This is demonstrated by a simple counterexample in which the cost function is identically zero in all but one orthant of $R^d$, takes a negative value somewhere in that orthant, and does not vary over time.)"

Here $d$ is the dimension of the set of strategies (values that we can pick at each time step).

I can't really see why that is the case, that with that given cost function you get exponential regret. Can you please help me understand how the proof would go?


texts: What is the set of all minimal 3CNF formulas?

texts:
Definition: A minimal 3CNF formula is an unsatisfiable 3CNF formula with minimum clauses connected by conjunctions, where each clause is disjunction of 3 literals, that is if any of it's clauses is removed from the formula, then the 3CNF formula becomes satisfiable.

For some natural number n, where n is the number of atomic variables, what is the set of all minimal 3CNF formulas? Is it finite? If it is finite then what is it's cardinality, i.e. how many different minimal 3CNF formulas is possible?

In a minimal k-cnf formula, there should be 2k different
k literals clauses exactly, so in a minimal 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

That's what I think anyway, but correct me if I am wrong.

Note that for k-cnf formula n≥k, so in 3CNF formula n≥3.


texts: Is this combinatorial optimisation problem similar to any known problem?

texts:
The problem is as follows:

We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a fixed integer $n$.

We now wish to overlay $n$ rectangles of dimensions $w \times h$ on the grid such that the total sum of the values of cells in these rectangles is maximized.

The following picture is an example of a two-dimensional grid with two such rectangles overlayed on it (the picture does not demonstrate the optimal solution, just one possible overlaying where $w = h = 2$ and $n = 2$)

The rectangles cannot intersect (otherwise we would just need to find the optimal position for one rectangle and then put all the rectangles in that position.)

In the example above the total sum of values in cells would be $-2 + 4.2 + 2.4 + 3.14 + 2.3 -1.4 + 1 - 3.1$

Is this similar to any known problem in combinatorial optimisation? so that I can start doing some reading and try to find ways to solve it.

Some more background for those interested:

So far the only ideas I had are either a greedy algorithm (which would find the best location for the first rectangle, then find the non-overlapping loctaion for the second rectangle etc.) or some metaheuristic such as genetic algorithms.

In reality I wish to solve this problem with a grid which has around a million cells and tens of thousand (or even hundreds of thousands) of rectangles, though it is not necessary to solve it in a short time (i.e it would be acceptable for the algorithm to take hours or even days.) I am not expecting an exact solution but I want to get one which is as good as possible given these constraints.

Cheers!


texts: Operations on OBDD: negation through Shannon's expansion

texts:
I have a problem with the application of the Shannon expansion for to obtain the negation of a formula boolean, than will need for implement the negation operator on OBDD (Order Binary Decision Diagram) that is, show that:

$\qquad \displaystyle \neg f(x_1,\ldots,x_n) = (\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1})$

where $f|_{x_i=b}$ is the function boolean in which replaces $x_i$ with b, that is:

$\qquad \displaystyle f|_{x_i=b}(x_1,\ldots,x_n)=f(x_1,\ldots,x_{i-1},b,x_{i+1},\ldots,x_n)$.

The proof says:

$\qquad \displaystyle\neg f(x_1,\ldots,x_n) = \neg((\neg x_1 \wedge f|_{x_1=0}) \vee  (x_1 \wedge f|_{x_1=1}))$.

Applying the negation (skip the intermediate steps), we get:

$\qquad \displaystyle (x_1 \wedge \neg x_1) \vee (\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1}) \vee (\neg f|_{x_1=0} \wedge \neg f|_{x_1=1}) $.

Now $(x_1 \wedge \neg x_1)= \mathrm{false}$ can be dropped, which leads to

$\qquad \displaystyle (\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1}) \vee (\neg f|_{x_1=0} \wedge \neg f|_{x_1=1}) $

which in turn is, finally, equal to

$\qquad \displaystyle (\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1})$.

Why does this hold?


texts: Why more and more handcraft lex do not use regular expression any more?

texts:
Recently I read the source code of Clang, and found that it just do the lex thing  by reading characters one by one and manually do the matching. But both my teacher when I'm in college and the book "Compilers Principles, Techniques, and Tools" take lots time to illustrate how to build a regular expression state machine, and I remember the tool Flex also build a state machine (correct me if I'm wrong). I think it's easy to lost in the manually matching code and if there's something changed in a language, it is a little difficult to update the matching code.

So why nowadays people prefer to manually do the matching rather than use regular expression? Is this because the table generated by the regex tool too big if the token table is complicated? Or is this an efficiency trade-off?

p.s. Evidence for "more and more":

Clang
Gcc (as long as they abandoned flex/bison)
OpenJDK
Python
Protobuf

What interesting is, the author of protobuf wants to use regular expression, but give up due to open source project get better keep independent, I think this counts a reason.


texts: Clock page replacement algorithm - Already existing pages

texts:
When simulating the clock page replacement algorithm, when a reference comes in which is already in memory, does the clock hand still increment?

Here is an example:

With 4 slots, using the clock page replacement algorithm

Reference list: 1 2 3 4 1 2 5 1 3 2 4 5

Initial list would look like this:

-> [1][1]
   [2][1]
   [3][1]
   [4][1]

The next reference to insert would be 1, then 2. Would the hand still point at 1 after 1, and after 2 ? In other words, after inserting the 5, would the clock look like this :

-> [5][1]
   [2][0]
   [3][0]
   [4][0]

?


texts: Decide whether a set of inequalities is solvable

texts:
Let $\{x_1, ..., x_n\}$ be a set of $n$ distinct variables, and suppose given a finite set of $m$ inequalities such that, for all $1 \leq i \leq n$, the $i$-th inequality is of the form: $$y_i + a_i \leq z_i + b_i$$ where $y_i,z_i \in \{x_1,...,x_n\}$ are variables and $a_i, b_i \in \mathbb{Z}_{\geq 0}$ are non-negative integers.

Problem: To decide whether the set of inequalities can be satisfied by assigning integer values to all the variables ($x_i \in \mathbb{Z}$ for all $i$).

Question: Can the problem be decided in polynomial time?

Idea: Consider the directed multigraph whose nodes are the variables $\{x_1,...,x_n\}$ and there is an edge $y_i \to z_i$ of weight $b_i - a_i$ associated to the $i$-th equation. Conjecture: the inequalities can be satisfied if and only if the graph has no directed cycles of negative weight. For the 'only if' direction note that having a cycle of negative weight means that $x_j \leq x_j - k$ for some variable $x_j$ and $k > 0$. I have no idea whether 'if' direction holds, or how to prove it.

Note: I encountered this problem when attempting to solve constraints imposed by a type inference mechanism dealing with expressions that may belong to different "levels".


texts:
I'm trying to setup a primary and secondary on call schedule with 6 people.

I'm trying to schedule people to be on call, so that they will be paired with everyone and they have the longest "break" between their schedules.

Ex for one rotation:

week:      1 2 3 4 5 6 7 8 9 10 11 ...
primary:   1 2 3 4 5 6...?
secondary: 3 4 5 1 2 4...?

Week 1 has people are {1,3}
Week 2 has people are {2,4}

Person 1 has a two week "break" before they're on shift again.
Person 2 has a two week "break" before they're on shift again.

Also, a person can't be both primary and secondary on the same week, ex: {3,3}.

What's the best way to generate a sequence like this, for any number of people so that they have the longest "break" between their shifts, and they are paired with someone different as much as possible?