texts: Divide-and-conquer algorithm to takes a set of itineraries and returns desirable itineraries

texts:
I've been given a question that states I will be given a set of itineraries, which are basically tuples in the form (cost, time) for airplane flights. An itinerary dominates another itinerary if its cost and time are less than the second itinerary's. If there exists an itinerary that dominates the current itinerary, then the current itinerary is considered undesirable. Otherwise, it is desirable. The algorithm gets a set of itineraries S and must output all desirable itineraries using divide-and-conquer. I need to calculate the time complexity/solve the recurrence relation.

Here is some pseudo-code of the algorithm:

Itinerary[] removeUndesirables(Itinerary[] initArr, int start, int end)
{
    Itinerary[] arr = initArr;

    // If 4 or more itineraries in set…
    if (arr.length > 3)
    {
        int middle = (start + end) / 2;

        // Recursively split and remove undesirable itineraries.
        Itinerary[] leftHalf  = removeUndesirables(arr, 0, middle);
        Itinerary[] rightHalf = removeUndesirables(arr, middle + 1, end);

        // Combine the two halves. Combining takes worse-case O(n)
        arr = combine(leftHalf, rightHalf);
    }

    // For each itinerary in range arr[0] -> arr[n – 1]…
    for (int i = 0; i < arr.length; i++)
    {
        // For every itinerary after the current in range arr[1] -> arr[n]…
        for (int j = 0; j < arr.length; j++)
        {
            // Compare arr[i] and arr[j], skip if i == j. Remove
            // arr[i] if found undesirable.
        }
    }

    // Return the combined set that has been purged of undesirables.
    return arr_2;
}

// Get desirable itineraries by remove all undesirable ones.
Itinerary[] searchForDesirableItineraries(Itinerary[] arr)
{
    return removeUndesirables(arr, 0, arr.length);
}

I am stuck on the recurrence relation, however.

Comparing all itineraries in the set for undesirableness takes O(n^2) time.
Search left half of size n/2 for undesirables. This takes worse-case
T($(n/2)^2$).
Search right half of size n/2 for undesirables. This takes worse-case
T($(n/2)^2$).
Combining the two half-sets takes, worst-case, O(n) time (where n is
the number of elements originally).

$T(n) = 2T((n/2)^2) + O(n^2) + O(n)$

$T(n) = 2[2T((n/4)^2) + {n^2}/4] + n^2 + n = 4T((n/2)^2) + {3n^2}/2 + n$

$T(n) = 4[2T((n/8)^2) + {n^2}/16] + {3n^2}/2 + n = 8T((n/8)^2) + {7n^2}/4 + n$

$...$

$T(n) = 2^kT((n/{2^k})^2) + {2^k - 1}/{2^{k-1}}n^2 + n$

Setting $(n/{2^k})^2 = 1$ and solving gives $k = log(n)$, where $log()$ is base 2.

If I plug $k = log(n)$ into the original recurrence equation, I get $2^{log(n)}T(1) + {(2^{log(n)} - 1)}/{(2^{log(n) - 1})} n^2 + n$, which I simplify to $2^{log(n)}T(1) + 2n^2 - n$.

$2n^2-n$ doesn't make sense to me. I expected my algorithm to be $n^2log(n)$. Why is my recurrence relation wrong?


texts: Is the class of Turing-recognizable languages closed under Homomorphism?

texts:
Would this proof work?

Given a language $L$ that is Turing recognizable and a TM M that recognizes it and a homomorphism $f$, we build a NTM M' that recognizes $f(L)$,

M' looks like this:

On input $w$ :

-Non-deterministicly feed words from $\Sigma^{*}$ to $f$ until you obtain w.

-run M on $f^{-1}(w)$, if M accepts accept, otherwise reject.


texts:
Consider the following in untyped lambda calculus
( \ x. x x ) ( \ g. \ f. g f )

Even though each variable is uniquely named reducing this will require an $\alpha$-renaming.
( \ x. x x ) ( \ g. \ f. g f )
( \ g. \ f. g f ) ( \ g. \ f. g f )
( \ f. ( \ g. \ f. g f ) f )

The bolded f is ambiguous since it is could refer to one of two bindings.  (If you are of the opinion that this sort of ambiguity resolves to the closest binding you can run it another step in which case we end up with two fs in the same context referring to different bindings)
My question is whether there also exists such an expression, that is one that has unique variable names which requires alpha renaming, in simply typed lambda calculus.  The given example does not work because ( \ x. x x ) would require an infinite type in STLC.


texts:
The Maximum Diversity Problem calls for choosing $m$ items from a list of $n$ items, such that the diversity defined as some metric distance between items is maximized.

I have a simpler problem, which I was hoping I could solve in a simpler manner. In my case I have a list of $n$ items each with a certain non-unique key. I want to chose $m$ items from my list so that the maximal number of items per key is minimized.

e.g., if my list is:

('a', 5), ('b', 4), ('c', 2), ('a', 6), ('b', 5)

and we must choose $m=3$ items, an optimal solution would be a list containing one item for each key.

Is there an algorithm for doing this that is simpler than those for the Maximum Diversity Problem?


texts:
I have an unweighted undirected graph.How is it possible in this graph for each vertex to find the length of the shortest cycle containing it?

P.s
This graph have not non-tree edge, but it have a cycle. What can be considered subtrees of the vertical 10? How will the algorithm work when the BFS reaches 16 and 17?


texts: Why can there be no reductions from NP-complete problems to P problems under P ≠ NP

texts: Under the assumption that $P \ne NP$, why is it impossible to reduce a problem that is known to be NP-complete to a problem that is known to be of polynomial time complexity? What kind of fundamental theorems would this contradict if it was possible?


texts: Theoretical lower bound of finding number of occurrences of a target integer in a sorted array

texts:
Given a sorted array of integers and a target integer, find the number of occurrences of the target integer.

It is well-known that a binary search has time complexity $O(\lg n) $ where $n$ is the size of the array.
For example, given an array $[1,2,3,3,4,5]$ and a target $3,$ the algorithm should return $2$ since there are two copies of $3$ in the array.

  Question: Is there a faster algorithms which has time complexity less than $O(\lg n)?$ Otherwise, is there a proof to prove that $\Omega(\lg n)$ is the theoretical lower bound?


texts:
I am a computer science under graduation student, and was going through some Go Back N ARQ (Computer Networking) videos on YouTube, and got a doubt in a question, which according to me should have a different answer than what the instructor on the video is arriving at (given that no other comment in the comments section of the video raises the same doubt, I am pretty sure I have had some problem in understanding the protocol). I would be greatful for any help. The question goes as follows:

Given a connection oriented communication between two hosts that are following the Go back N protocol, with sender's window = 3, and assuming that every 5th packet transmitted by the sender is lost (no acknowledgements are lost), what are the total number of transmissions required by the sender host? Assume that the packets to be sent are numbered 1-10.

The sequence of transmissions by the sender that I am getting is (final answer = 16):

1,2,3; 4,5,6; 5,6,7; 8,9,10; 8,9,10; 10

Meanwhile, the instructor in the video gets it like this (final answer = 18):

1,2,3,4,5,6,7,5,6,7,8,9,7,8,9,10,9,10

I would appreciate if someone could point out where I am going wrong in understanding the protocol.
Thanks!


texts: Immutable data structures for 2d+ lattices

texts:
I would like to find an immutable/persistent data structure that allows  efficient updating for 2d (or higher) lattices/arrays/matrices, and reasonable performance when appending in any direction. Updates would be typically be localized to certain areas.

I could probably make do with mapping a 1d vector onto 2 dimensions, but is there something better?

Background: I would like to implement a kind of cellular automaton where history is preserved to a degree.


texts: Are dictionaries and associative arrays the same thing?

texts: With respect to abstract datatypes (ADTs), are the terms "dictionary" and "associative array" perfect synonyms or are there slight differences between them?


texts:
Subset sum is given by this question:
"The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?"

My question is: If the numbers in the set are functions of other numbers, is that still subset sum? For example
The set {1,2,3} where the first number is X, the second is X+1, third is X+2 and so on. So it is a general set.

Is this allowed?


texts: How can we formulate an anti-knight Sudoku as an exact cover problem?

texts:
Formulating standard Sudoku as an exact cover problem is easy and well documented. All of the constrained groups contain every digit which makes it natural to express the problem this way. Wikipedia claims without citation that:

Although other Sudoku variations have different numbers of rows, columns, numbers and/or different kinds of constraints, they all involve possibilities and constraint sets, and thus can be seen as exact hitting set problems.

How would one formulate other variants as exact cover problems with an incidence matrix? I'm focusing on the anti-knight variant, but with the goal of learning about expressing arbitrary variants.
The anti-knight Sudoku variant includes all of the standard rules, and additionally requires that no two squares which are a knight's move (in chess) apart may contain the same digit. I don't know how to approach this because a constraint between two squares cannot be expressed as requiring all digits to be present in some permutation. I can imagine a version of Algorithm X that solves this by removing additional rows by manual application of the anti-knight rule, but I believe Wikipedia is claiming this constraint should be expressible in the matrix alone without modifying the algorithm.
Is Wikipedia's claim that all variants can be expressed this way correct, and how would one approach the anti-knight example?


texts: Running time for Testing Polygonal Neighbours for Intersection or Inclusion

texts:
I was reading this  paper by Shamos, M.I, on "Geometric Intersection Problems" (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.366.9983&rep=rep1&type=pdf) , and was trying to understand it's Theorem 6, which says " Whether any two of N convex k-gons intersect can be determined in O(N(k+log N log k)) time."

I was stucked on the point 3 (Inclusion and intersection tests), in which the author says that " When a polygon is inserted, it ,it must be tested against its immediate neighbors for inclusion or intersection. As we have seen before, each such test can be done in O(k) time. "

I do not understand how is that possible. Theorem 5 of the same  paper states that determining an intersection of two k-gons takes O(k log k) time.

If the author is talking about something else, then I didn't get that.
Any help appreciated.
Thanks.
Moon


texts:
I am trying to understand the use of symmetry in pattern databases (Heuristics, single agent search). This is too specialized of a topic to find common videos or explanations in general. I read the paper Pattern Databases by Joseph C. Culberson and Jonathan Schaeffer (University of Alberta) in Computational Intelligence, Volume 14, Number 3, 1998.

In the paper, they explain the different kinds of symmetries we can use on the 15-Sliding Tile Puzzle such as Horizontal, Vertical and Mirror. But what I do not understand is how exactly are we going to use those symmetrical configurations of a puzzle to find a good lower bound on the estimated cost of a state from the goal.

I would really appreciate if anybody can explain the process of using symmetry in pattern databases or can point toward a good explanation.


texts: What is the meaning of max() in intro. to algorithms?

texts:
I'm reading chapter 3(growth functions) of CLRS and in giving an example of proving theta for a standard quadratic function the book gives the following value for $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a})$ .

I'm confused regarding what "max" means in this context. The quadratic function is $an^2 + bn + c$ and the constants give are $c_1 = a/4, c_2 =7a/4$.

I'm thinking it might mean which ever of the parameters yields a larger value?


texts: Assume there is a set {1,...,n} of person. For each person i, a set $A_i$ of items are available for exchange. A is the set of all items. The value of item j to person i is $v_{ij}$ and assume all values are positive integers. The question is, does there exist a pair of person who can both make profit by exchanging some of their items in $A_i$.Formally:$\exists$ i and i' and $S_i\subseteq A_i$ and $S_{i'}\subseteq A_{i'}$ such that $\sum_{j\in S_i} v_{i'j}>\sum_{j\in S_{i'}} v_{i'j}$ and $\sum_{j\in S_{i'}} v_{ij}>\sum_{j\in S_{i}} v_{ij}$ I'm not sure whether this question is NP-Complete or there exists a polynomial-time algorithm?


texts: How to use different size features in SVM?

texts:
I want to train a support vector machine with some features. The problem is, one of the features is 1-dimensional (only an angle) and the other is an LBP Histogram, an 58-dimensional vector.

Therefore if I concatenate them, like this (in MATLAB) :

f = [lbp_histogram; angle];

I got a 59x1 vector, I can train SVM with these vectors, however, in this case the "weight" or "importance" of angle feature is 1/59, whereas lbp has 58/59 weight. What if I want to give them equal weights? Or better, I want to adjust the weights for best performance.
How can I change the weight?

The only 2 options I have in mind is :

Scale the angle feature with the weight like this :

angle = angle * w_angle
angle = angle ^ w_angle

Do you reccomend one of these, or any other way that I can make angle as important as lbp_histogram?

I hope I stated my problem clearly,
Thanks for any help.


texts: Problem with the mapping reduction from $A_{TM}$ to $HALT_{TM}$

texts:
Sipser provided the following proof to prove the mapping reduction from $A_{TM}$ to $HALT_{TM}$, it in fact tried to build a mapping function:

My problem is the way this proof works. The function must take $<M,w> \in A_{TM}$ and produce $<M',w'>$  if and only  if $<M',w'>\in HALT_{TM}$ We know by the hypothesis $<M,w>\in A_{TM}$. The machine $M'$ runs $M$ on an input $x$ not the input $w$. Now what if $<M,x>\notin A_{TM}$ and $<M,w>\in A_{TM}$? then $M'$ will output the loop while since $<M,w>\in A_{TM}$ the output must be accept. As a result the output $<M',w>$ which is supposed to be in $HALT_{TM}$ is not truly corresponded to the input. I would be appreciated if you explain about my problem.

Thanks


texts: Understanding sequential solution for the TAOCP 3 Million Men problem

texts:
The problem and solution of interest is described here: What does > mean in this TAOCP solution?

Can anyone explain following points in that solution:

How exactly we can build (x[i], x[i+2]) for 1 <= i <= N-2 ?
What exactly means "merge G with it"? Provide exact algorithm for merging these two files.
How steps 1-4 are executed? Is it:

if (condition 1) {
    ....
}
if (condition 2) {
    ....
}
if (condition 3) {
    ....
}
if (condition 4) {
    ....
}

or

if (condition 1) {
    ....
}
else if (condition 2) {
    ....
}
else if (condition 3) {
    ....
}
else if (condition 4) {
    ....
}

?


texts:
Assume that we have these bigram and unigram data:( Note: not a real data)
bigram:

#a(start with a) =21
bc= 42
cf= 32
de= 64
e#= 23

unigram:

# 43

a= 84

b=123

c=142

f=161

d=150

e=170

what is the probability of generating a word like "abcfde"?
I think for having a word starts with a the probability is 21/43. How about bc? is it like bc/b?


texts: What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element?

texts: Consider the recursive quick sort with random pivoting i.e. each time a random pivot element is chosen uniformly. When this randomized algorithm is being applied to an array with n distinct element, what is the probability that the smallest and the greatest element will be compared during run of the algorithm.


texts: Name for a function on formulae that does not break the structure of given formula

texts:
I have two logics, $L_1$ and $L_2$, and a mapping $f: Formulas_{L1} \rightarrow Formulas_{L2}$, and want to argue that the mapping is "nice", in the sense that it is structure-preserving. But I do not know the right name for this concept.
The formulas of these logics are generated by a grammar, and thus the two languages form two term algebras. The mapping satisfies $f = g \circ h$, where $h : Formulas_{L1} -> Formulas_{L2'}$ is structure-preserving, in the sense that it is an injective homomorphism between the two term algebras,
and the language of $L2'$ is a sublanguage of the language of $L2$ (Therefore, $Formulas_{L2'} \subset Formulas_{L2}$). The function $g : Formulas_{L2'} \rightarrow Formulas_{L2}$, however, is not a homomorphism: it just wraps the given formula in a nonterminal which is not present in the grammar of $L2'$. However, $g$ still does not break the structure of the given formula; intuitively, it just wraps it in some container. Maybe 'functor' from category theory is a related concept? An example of that function would be: $g(t) = \textit{one_plus} \: t$.
What is the right term/name for the sense in which $g$ does not break the structure of a given formula? How can I argue that $Formulas_{L2}$, thanks to $g \circ h$, extends the syntax of $Formulas_{L1}$; i.e., that $g \circ h$ is an embedding of the syntax of $L1$ into the syntax of $L2$?


texts: I've studied this lots, and they say overfitting the actions in machine learning is bad, yet our neurons do become very strong and find the best actions/senses that we go by or avoid, plus can be de-incremented/incremented from bad/good by bad or good triggers, meaning the actions will level and it ends up with the best(right), super strong confident actions. How does this fail? It uses positive and negative sense triggers to de/re-increment the actions say from 44pos. to 22neg.


texts: Explanation of a specific recurrence with respect to Master Theorem

texts:
Concerning the Master Theorem. I have found the following equation as the base of analysis:

$\quad T(n) = aT(n/b) + \Theta(n^k)$

but I also found the following:

$\quad T(n) = aT(n/b) + \Theta(n^k\cdot\log_p n)$

where the base $p$ is a real number.

Can anyone explain the second equation? I understand the proof with the first equation but can not understand the second formula.


texts: Is the problem of deciding whether a Context free grammar generates exactly K strings is decidable?

texts:
I am reading "Introduction to Theory of Computation" by Michael Sipser. One of the exercise problems asks to verify whether  the problem of deciding whether a Context free grammar generates exactly K strings is decidable?

This problem has two parts

K can be infinite (I know how to solve this. If the grammar has any
kind of     loop then it will generate infinite number of strings
thus k=infinite.
K can be finite. I don't know how to solve this. Any Ideas?


texts:
hello and thank you for helping me understand the following:

I really don't understand this, why if language $A \in BPP$ then $A≤_P\#SAT$?

language A is in BPP class, if for a probabilistic turing machine M, M outputs 1 for all $x \in A$ in a probability $\geq 2/3$, and for all $x \not \in A$ M outputs 1 in a probability of $\leq 1/3$ and of course M must run in a polynomial time on all inputs.

so if $A \in BPP$, why does it mean that $A≤_P\#SAT$? if M is reduced to boolean F, it means that we'll get output of 1 in a probability of $\geq 2/3$ for every $x \in A$? why?

can someone please show me algorithmically or mathmatically why if language $A \in BPP$ then $A≤_P\#SAT$? quite lost

thank you, would appreciate if you could explain along.


texts: Closure properties between two languages from different grammars

texts:
We know that if we have two languages produced by one regular grammar, then any language produced from the union, intersection, and so on would be regular.

What if we have a regular grammar that produces language A and a different regular grammar that produces language B. Then could the closure properties still be used in order to produce another regular language C?

For example, is $A\cap B$ a regular language (intersection)? Is $A\|B$ a regular language (concatenation)?


texts:
Continuing from this question: the buckets of water problem.
(All the definitions can be found there, so I will not repeat them).
As seen there by Yuval's answer, the problem is NP-Hard.
I was attempting to prove its NP-completeness, and while doing so - I was suddenly not sure whether or not it belongs to NP.
Because the witness is most likely to be a series of actions (filling buckets etc ...), and that might be too long.
Of course, we can change the definition of the language, in such a way we will limit the number of actions to be polynomial or make it part of the input (with a slight adjustment to represent the number of actions in unary, so it won't be log of the number's value).
But, I find it interesting to ask if this is a must?
And if we do not change anything - Can we tell for sure it is not NP? That there is no better (polynomial) witness.


texts: Construct two functions $f$ and $g$ satisfying $f \ne O(g), g \ne O(f)$

texts:
Construct two functions $  f,g:   R^+ → R^+ $ satisfying:

$f, g$ are continuous;
$f, g$ are monotonically increasing;
$f \ne O(g)$ and $g \ne O(f)$.


texts: Find a minimum-weight perfect 2-matching

texts:
How would one find a minimum-weight perfect 2-matching of a general graph? Is it possible to use standard matching techniques like Blossom V?

A minimum-weight perfect 2-matching of a graph G is a subgraph M of minimal total edge weight, such that each vertex in G is incident by exactly 2 edges from M.


texts: Big O of an algorithm that relies on convergence

texts:
I'm wondering if its possible to express the time complexity of an algorithm that relies on convergence using Big $O$ notation.

Is it fair to say that we can't reason about an algorithm's scalability based on input size if we also have to rely on convergence - unless there's some facet of the algorithm's manner of convergence whereby we can mathematically prove that the number of iterations to reach convergence is related to input size (essentially showing that convergence of the algorithm is a function of the input size $N$)?

For instance, I'm using an algorithm called TextRank, which is based on PageRank - except each vertex is a sentence instead of a webpage and each edge represents the similarity between two sentences (or vertices). The algorithm iterates over the vertices in the graph, carrying out a computation to calculate the score of each vertex for an indefinite amount of iterations until the difference between scores from one iteration to the next is below a threshold (we've reached convergence).

I'm thinking that we cannot reason that an input of size N sentences will always converge in the same manner. Two different bodies of text with say $30$ ($N=30$) sentences, could theoretically require a noticeably different number of iterations over the graph to converge.

Is it possible to represent the limiting behaviour of the function in a polynomial expression due to reliance on convergence?


texts: What are applications to sort plain integer arrays?

texts:
A lot of research and engineering effort is put into finding fast methods
to sort an array of integers; e.g., Java's runtime library has highly-tuned
methods to sort arrays of each primitive type (see java.util.DualPivotQuicksort).

What are real-world applications of these methods?
What are algorithms that build on plain integer sorting?

Let me clarify: I am not asking of applications of sorting per se, I am well aware that there is plenty of them. But it seems to me, most actually require to sort more complex data types with additional data.
Typically these objects/records are sorted with respect to some key field, which might well be an integer, but this is not quite the same as sorting only an array of plain integers.
In particular, sorting keys with auxiliary data would not be possible using the Java methods in java.util.DualPivotQuicksort.


texts: Subtracting lower-order term to prove subtitution method works

texts:
Substation method fails to prove that $T(n)=\Theta(n^2) $ for the recursion $T(n)=4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2$.

I don't understand how to subtract off lower-order term to prove that substitution works.

Came up with: $T(n) \leq cn^2 - bn^2$

Assume it holds for $T(n/2) \leq c(n/2)^2 - b(n/2)^2$

$T(n) \leq 4(c(n/2)^2 - b(n/2)^2) + n^2 = cn^2- bn^2 + n^2 $

However, there is no way to solve $cn^2- bn^2 + n^2 \leq cn^2 - bn^2 $ for $b$


texts: How to solve recurrence T(n) = 5T(n/5) + n/ lgn

texts: It can't be solved with master method. The result seems to be T(n) = Θ (nlg lgn), but I have a problem to prove it. Could you help please?


texts:
I'm in a data structures class, and am working on an assignment right now that asks me to find the theta complexity of certain loops. I missed class the day we were introduced to the topic, and everything I can find online expects more prior knowledge than I feel I have. Can someone just explain this in beginners terms for me? I don't know what Big-O or theta even refer to in this notation. I think I have a loose idea of what "complexity" refers to (a measure of how efficient code is, depending on how long a function will take in different circumstances?)

The problem in question:

Demonstrate the $\Theta$-complexity of the functions below. In order to demonstrate that $f(n) = \Theta(g(n))$ you must find two constants $C_1$ and $C_2$ such that
$$ C_1g(n) ≥ f(n) ≥ C_2g(n). $$

a.) $f(n) = n^3 - 3n^2 + 5$.

b.) $f(n) = 2\log_2 n - 4$.


texts: metaheuristics vs exact and traditional algorithms

texts:
Recently, my friend has submitted a paper and solved a problem with an exact method. Surprisingly, a reviewer asked him why he used an exact method instead of the popular metaheuristics algorithms! We replied to the reviewer based on our knowledge as follows:

"We use metaheuristics when solving the problem is hard and when we could not evaluate the exact solution in a short time. Where the problem is easy to solve, using metaheuristics is incorrect because of an inexact solution and also spending more time. Moreover, unlike metaheuristics methods, we can do sensitivity analysis in an exact method."

Now, the referee accepts this content providing that authors add some related references!
Although I think the above reasons are true, I need some references to prove them in this special situation.


texts: Sweeping integrated into memory allocation: Why only fixed size objects?

texts:
In our language design book, it is mentioned that GC sweep can be integrated into allocation, such that when you call malloc for example, you sweep until you find a fitting object, which you then return (i.e. sweeping is not a different procedure).

It, however, also mentions that this is only viable when the objects all have the same size. Why is that? It seems to me that it should be possible, since the sizes of the objects are known from the metadata etc.


texts: Converting If-else integer equation to Linear Programming

texts:
I have an if-then-else condition with three binary variables A, B and C:

if A + B = 1 then C = 0

How do I express this as an integer linear program with equality constraints?


texts: Create a turing machine for log base 2 of n

texts:
How would someone create a Turing machine that computes ⌈log2(n)⌉?
I know that:
n = 1, 2, 3, 4, 5, 6, 7, 8, ...
f(n) = 0, 1, 2, 2, 3, 3, 3, 3, ...
And that I want the input tape to have n 1's in it to represent the number i.e. 8 would be
###11111111###
How would the the turing machine for this be created?


texts: Find the first integer with exactly $n$ divisors

texts:
For given positive integer $n$ find the first number $x$ with exactly $n$ divisors. For simplicity of the problem we can assume that $x$ will always fit in integer size and $n \leq 1000$.

Example

If $n=4, x = 6, \text{ divisors of 6 are } \{1, 2, 3, 6\}\\n=6, x=12, \text{divisors of 12 are } \{1,2,3,4,6,12\}$

I was thinking because the number should have at most 1000 divisors we should brute force them in some way, but I cannot think how it could be done.


texts: Finding the maximum bandwidth along a single path in a network

texts:
I am trying to search for an algorithm that can tell me which node has the highest download (or upload) capacity given a weighted directed graph, where weights correspond to individual link bandwidths. I have looked at the maximal flow problem and at the Edmond-Karp algorithm. My questions are the following:

Edmond-Karp just tells us how much throughput we can get (at the sink) from source to sink if any of the paths were used. Correct?
Edmond-Karp does not tell us which path can give us the maximum flow. Correct?


texts: Finding a trapdoor function for the 3-partition problem

texts:
I am working on a cryptography project. Let's say I want to build a public key cryptosystem using the 3-partition problem, which is NP-Complete, as a basis (just like RSA uses integer factorization).

Now, I am having trouble coming up with a trapdoor function that helps me enconde it. Let's say I have $T=\{t_{1}, t_{2},...,t_{3n}\}$ and a solution $S=\{S_{1}, S_{2}, ..., S_{n}\}$, where every $S_{i}$ contains 3 elements of $T$ and $\sum_{k=1}^{3} S_{ik} = \sum_{k=1}^{3} S_{jk}=x$.

Now, let's assume the user creates $T$ and $S$, and of course also knows $x$. He can use either $x$ or $S$, or both, as a private key, and send $T$ and the public key for enconding.

I want to find a "function" that in one way requires finding $S$ or $x$ from $T$, and the other way can be done only with $T$. That is, given a plaintext $p$, $f(p, T)=c$ and $g(c, S)=p$ (I don't know if $f$ and $g$ have to be inverse of each other necessarily).

The cryptisystem does not have to be super-secure or have no flaws, I'm just looking for a function/encoding that does this in whatever way. For example, the MH knapsack cryptosystem uses some kind of alternate way to write the subset sum problem as a sum like $V=a_1x_1,..., a_nx_n$.

Thanks for reading.


texts:
I'm trying to find a good solution to the following problem:
Given a set of 3d real number coordinates inside a cube, I want to group them into containers. The containers should contain all elements that are in predefined distance to at least one of the other elements. Should two elements be closer than a predefined distance, they are to end in the same container.
Note: Two elements that are further apart may end in the same container e.g. if they are both close to a different element

The most straight forward solution I can think of is to go through all points, and compare them with all other points that haven't been visited before to find out if they are in proximity, but it seems rather inefficient.

I tried to find a solution online, but (maybe because I'm missing the correct keywords) can't find any. I stumbled upon k-d-trees and similar concepts but as far as I understood they don't help much here. Are there good algorithms out there that can take care of this or does anybody have a suggestion on what I could do?

Below is a (badly hand drawn) illustration of a possible 2d case with reference distance d marked in blue and the two groups I want to end up with in red. Thanks in advance for any help.

Edit: as pointed out in the comments, this problem can be thought of as finding connected components of a graph. The graph nodes are the points from the data set and two nodes are adjacent if their distance is smaller than the reference value. The problem I see is that establishing the edges seems to be O(n^2), because I don't see a way that doesn't require me to do pairwise checks on all points of the set, is that correct?


texts: what does "reduce A problem to B problem in polynomial time" mean?

texts:
It is kind of NP-complete problem.
For example,

A problem:
Given a sequence of numbers, return the maximum value within these numbers.
B problem:
Given a sequence of numbers, return start index and end index of the maximum sum segment within these numbers.

To show how to reduce A problem to B problem in O(n) time.
Does this means we could solve A problem by solving B problems?
It seems a little bit strange for this case.


texts: Help with model answer for time complexity

texts:
Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n?
I tried to write this in python to understand when it would be n-1 and the answer is always n. I am assuming that the loop counter in pseudo-code is evaluated one more time than the body is executed as is said in the Cormen book.
My thinking is that if the length of n is 1, the loop evaluation is still tested so regardless the answer would still be n, even if the loop body itself did not run.
Max(A)

1 MaxInt = A[1]
2 index = 2
3 while index ≤ n // Why is the best n-1 here?
4   if MaxInt < A[index]
5     MaxInt = A[index]
6   index = index+1
7 return MaxInt

I know it has to be something very simple but I cant seem to work it out as testing with 1 or 1000 the answer I get back for a count is always n-1 (0, 999) and if I assume that the loops asserts a final time that is + 1, so 0 + 1 = 1, which is n and 999 + 1 = 1000 which is n.


texts: Minimal number of comparisons - sorting $6$ elements

texts:
I've been thinking about sorting $6$ elements with the minimal possible number of comparisons. I can do it in $10$ comparisons but I've no idea if this is optimal. Or is there a better algorithm ?

Algorithm
1. Sort $a_1, a_2, a_3$ and $a_4, a_5, a_6$.
Number of comparisons: $3+3=6$.
2. Merge two subarrays.
Number of comparisons: $3 + 3 - 2 = 4$.
Total number of comparisons: $6 + 4 = 10$.


texts:
I've read numerous links on the fact that wang tiles are turing complete, and details about them (links at end).

However there is little talk of how to actually place the tiles.  One place i read mentioned (paraphrasing) "by placing tiles only where they are uniquely able to fit, you'll evaluate the program", but I'm finding there is actually ambiguity in what tiles can fit where.

Another link mentions that they personally place tiles in a spiral pattern, and when they hit a spot that needs a tile which doesn't exist (isn't valid) they backtrack and make a different choice earlier on.

Does anyone know if there's any reliable algorithm for placing the wang tiles when simulating turing machines with wang tiles?

I first believed that i could just go tile by tile, systematically matching empty spots to tiles that would fit there, but there are times when it is ambiguous which tile should go there.

Please let me know if more information is needed, such as a specific case when it's ambiguous, and I will provide it.  Thanks!

Links I've read include:
http://www.math.oregonstate.edu/~math_reu/proceedings/REU_Proceedings/Proceedings1989/2_Michie89.pdf

https://moyix.wordpress.com/2012/04/06/computing-with-tiles/

How to convert a Turing Machine program to a tiling using Wang Tiles?

http://grahamshawcross.com/2012/10/12/wang-tiles-and-turing-machines/

https://because0fbeauty.wordpress.com/2014/02/28/wang-tiles-1/


texts:
It is said that attributes supply some semantic information to the grammar. Meantime, the same attributes let you to resolve ambiguities. Text books agree that it is worth haveing a CF grammar which admits ambiguities because the ambiguities will go away anyway once you evaluate your AST with attributes anyway. For this reason it is useless to invent an intractable CS grammar for your language.

This strongly associates ambiguities with context sensitivity in my mind. However, there is an expert in the field who states brazen faced that context sensitivity is absolutely irrelevant to ambiguity but supplies no support to ground his statement. Can you untangle the conflicting opinions by some light?

I cannot refrain from asking the same question in the following form. My mind is highly influenced by this description the of grammar type comparison in "Parsing Techniques: A Practical Guide"

  Type n grammars are more powerful than Type n+1 grammars, for n =
  0,1,2”, and one often reads statements like “A regular (Type 3)
  grammar is not powerful enough to match parentheses”. It means that
  more powerful grammars can define more complicated boundaries between
  correct and incorrect sentences. Some boundaries are so fine that they
  cannot be described by any grammar (that is, by any generative
  process). This idea has been depicted metaphorically in Figure 2.33,
  in which a rose is approximated by increasingly finer outlines. In
  this metaphor, the rose corresponds to the language (imagine the
  sentences of the language as molecules in the rose); the grammar
  serves to delineate its silhouette. A regular grammar only allows us
  straight horizontal and vertical line segments to describe the flower;
  the result is a coarse and mechanical-looking picture. A CF grammar
  would approximate the outline by straight lines at any angle and by
  circle segments. The result is stilted but recognizable. A CS grammar
  would present us with a smooth curve tightly enveloping the flower,
  but the curve is too smooth: it cannot follow all the sharp turns, and
  it deviates slightly at complicated points; still, a very realistic
  picture results. An unrestricted phrase structure grammar can
  represent the outline perfectly. The rose itself cannot be caught in a
  finite description; its essence remains forever out of our reach.

  A
  more prosaic and practical example can be found in the successive sets
  of Java programs that can be generated by the various grammar types:

  The set of all lexically correct Java programs can be generated by a regular grammar. A Java program is lexically correct if there are no
  newlines inside strings, comments are terminated before end-of-file,
  all numerical constants have the right form, etc.
  The set of all syntactically correct Java programs can be generated by a context free grammar. These programs conform to the
  (CF) grammar in the manual.
  The set of all semantically correct Java programs can be generated by a CS grammar. These are the programs that pass through a Java
  compiler without error.
  The set of all Java programs that would terminate in finite time when run with a given input can be generated by an unrestricted phrase
  structure grammar. Such a grammar would incorporate detailed
  descriptions of the Java lib and the Java run-time system.
  The set of all Java programs that solve a given problem cannot be generated by a grammar (although the description of the set is
  finite).

I see that CF can generate the syntactically valid programs and you need CS grammar to accommodate the semantics of the language. This more complete grammar can resolve if x(y) is a call of a function or type conversion. It will also iron out the associativity ambiguity in a+b+c telling that difference between (a+b)+c and a+(b+c) is immaterial. For this reason I think that CF -> CS also resolves ambiguities. Why telling that context sensitivity and ambiguity are orthogonal after that?


texts: Does computational complexity theory take into account problems with subjectivity in the verification of a solution?

texts:
When we discuss P vs NP we are looking at the difference between problems that are easily solved versus easily verified (wrt polynomial vs exponential time).

But in both cases these are black-and-white results. We do/don't solve the problem, we do/don't verify the problem.

What about cases where there is subjectivity to the verification? Problems where 2 people don't agree on the solution, since the solution may depend on context, environment, etc.

Does computational complexity deal with the subjectivity in verification, or are all problems modeled as black-and-white results?


texts: What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

texts:
Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not.

For example, consider the following two trees:

Example trees T and U are isomorphic.
An isomorphism (bijection) is described in the table below:

  T          U
  1          2
  2          4
  3          1
  4          5
  5          3
  "white"    "green"
  "blue"     "white"

Below are some things to know about the problem:

Nodes are colored
edges are not colored.
Nodes are free to be any
color. Adjacent nodes are allowed to be the same color.
which node is
the root node of each tree cannot be changed.
children are un-ordered.
the tree is not necessarily a binary tree. a node could have 3 children, 4 children, 5, etc...

Formally, a colored tree is a tuple (VS, ES, root, color_set, color_map) such that:

VS is the vertex set
ES is the edge set
(VS, ES) is a undirected tree
root is a element of VS
color_set is a set of objects called "colors"
color_map is a mapping from VS to color_set
every element of  color_set appears in the range of color_map at least once. That is, every color is applied to at least one node.

colored trees T and U are isomorphic if and only if there exists a bijection, PHI from the vertex set of T, VT, to the vertex set of U, VU such that:

the root of one tree is matched to the root of the other tree
for all nodes v, w in VT, {v, w} is an edge in tree T if and only if {PHI(v), PHI(w)} is an edge in tree U
for all nodes v, w in VT, v and w are the same color in tree T if and only if PHI(v), PHI(w) are the same color in tree U


texts: What is the complexity of finding a regular expression equivalent to a given DFA?

texts:
I had taken a course long ago on complexity theory. I only remember basic things,
so I am reading "Introduction to the Theory of Computation by Michael Sipser". The book in its first chapter introduces DFA and NFA.

If we are given a DFA $D$ where $\sum=\{0,1\}$ ( the alphabets ), then how difficult is the  problem of finding a regular expression of the language that $D$ recognises?

By difficulty I mean to which class does this problem belong like NP,PSPACE etc ( sorry for vague definition of difficulty, I only have a broad understanding of what classes NP,PSPACE etc are as of now ).


texts: Regular Expression: L= {w | every even position of w is '1'}

texts:
I am trying to solve a regular expression of binary string where every even position is a '1'

I've solved this for an odd position: (1(0+1))*(1+ε)

How would it look like for an even position then? Thanks in advance.


texts: If EXP = NEXP, can we say anything about P and NP?

texts: I found one older question asked about this but without any responses.


texts:
I have reached a chapter in the notes I am following where a program written in C++ is using a Monte Carlo method to estimate $\pi$. It mentions a 'seed', but does not say what this is. I have tried finding out what a seed is online, but I only seem to get results about 'why you should/shouldn't use a fixed seed', and unfortunately they have left me none the wiser as to what a seed actually is.

What is seed in this context?


texts: How do program types such as natural numbers figure into the Curry-Howard Isomorphism?

texts:
In Coq, the nat, the type of natural numbers, has type Set. By the Curry-Howard Isomorphism, all propositions of type Prop are types of corresponding proof terms. How do nats or other instances of Set figure into this isomorphism?
In other words, is there a correspondent for Sets in the Curry-Howard isomorphism, as there is for Props and proof terms, or are they outside the things that have correspondents in the Curry-Howard Isomorphism?
Sorry for the imprecise wording, I'm struggling to express my question clearly, probably because of a poor understanding of the Curry-Howard Isomorphism, happy to be corrected on any misunderstandings I have expressed above.


texts:
Can anyone simplify the meaning of families of types index by a type. It looks i get it but quite not understood it. What do you mean by a "family" ?

I understand index by a value (n length sequence) then what you mean by index by a type. Any example how you index by a type ? Thanks.


texts: Enumerating the elements of an integer lattice $\mathbb{Z}^n$

texts:
The elements of $\mathbb{Z}$ can be enumerated as $0, 1, -1, 2, -2, 3, -3, \ldots$. Similarly, the points of the lattice $\mathbb{Z}^2$ can be enumerated

$$(0,0), (1,0), (0,1), (-1,0), (0,-1), (2,0), (1,1), (0,2), (-1,1), \ldots$$

I would like to extend this algorithm to $\mathbb{Z}^n$. Is there a simple way to do that?

Note that the ordering of the elements may vary. The only condition should be that if $B_1$ and $B_2$ are two closed balls in the metric $L^1$ on $\mathbb{Z}^n$, and $B_1 \subset B_2$, then all the elements of $B_1$ should be enumerated before any element of $B_2 - B_1$.


texts: Algorithm for searching string with wildcards

texts:
I'm trying to find efficient algorithm for checking if string with wildcards contains given substring.

The parts of the string are separated with a "." character.

So for example I have

ab.cd.*.efg

And I want to check for given strings, if they are substrings of string above, for example to match with those:

ab
b.c
cd.qq <- "qq" is replacement for wildcard
d.qwe.ef <- "qwe" is replacement for wildcard

What is the best algorithm to use?


texts:
I came across the following interview question

  There are 2N people a company is planning to interview. The cost of
  flying the i-th person to city A is costs[i][0], and the cost of
  flying the i-th person to city B is costs[i][1].

  Return the minimum cost to fly every person to a city such that
  exactly N people arrive in each city.

The solution to this involves greedy approach, where we sort the array based on the "profit" parameter. profit of choosing city A for a candidate i is defined as costs[i][1] - costs[i][0] and choose the top half elements from the sorted array to go to A and rest to B.

What if this question is modified to 3 cities and you have find optimal partition of n/3 chunks? Will greedy algorithm still work?


texts: Why is it important for functions to be anonymous in lambda calculus?

texts:
I was watching the lecture by Jim Weirich, titled 'Adventures in Functional Programming'. In this lecture, he introduces the concept of Y-combinators, which essentially finds the fixed point for higher order functions.

One of the motivations, as he mentions it, is to be able to express recursive functions using lambda calculus so that the theory by Church (anything that is effectively computable can be computed using lambda calculus) stays.

The problem is that a function cannot call itself simply so, because lambda calculus does not allow named functions, i.e.,

$$n(x, y) = x + y$$

cannot bear the name '$n$', it must be defined anonymously:

$$(x, y) \rightarrow x + y $$

Why is it important for lambda calculus to have functions that are not named? What principle is violated if there are named functions? Or is it that I just misunderstood jim's video?


texts: Does this proof work for infinite regular languages

texts:
My proof was deemed false because it does not work for infinite regular languages, but I don't understand why.

Prove: "If we remove one string from any nonempty regular set, the resulting set is still regular.

I used to lemmas:

A set containing only one string is trivially a regular language
The union operator is closed in the class of regular languages

Given these two lemmas, I made the claim that any regular language $L$ can be written in the form
$$L = \bigcup_{e \in L}\{e\}$$

Then, one picks an arbitrary string $r \in L$ to remove, and expresses $L$ in the same manner with $r$ distinct:
$$L = \bigcup_{e \in (L - \{r\})}\{e\} \cup \{r\}, \quad r \in L$$

Finally, we simply remove $r$ from the union and obtain:
$$L' = \bigcup_{e \in (L - \{r\})}\{e\}$$

$L'$ is also regular by the two lemmas introduced earlier.


texts: Floyd's Cycle Detection Algorithm Proof In Laymen

texts:
I came across the algorithm question of detecting a cycle in a linked list, but the solution has to be constant space O(1).
I have looked through various proofs proving that:

If there is a cycle, at some point the tortoise and the hare will meet. I understand that at some point, both will be within the cycle, but how do we know that they will eventually meet?
The time complexity will equal O(N), where N = # of nodes.

I do not care about the case where we want to find the START of the cycle, only about proving that if there is a cycle, then the two pointers will meet at a point within the cycle, and that the time complexity is O(N).
None of these proofs make intuitive, logical sense to me.
Can someone PLEASE explain the two bullet points above in an intuitive manner?
If there is math in the proof, it would be great if you could explain all parts of the proof that would not make logical sense to someone without a CS degree.  Thanks!


texts: Extracting a spanning tree from a directed acyclic graph with minimum total distance between terminal nodes

texts:
I have a directed acyclic graph that has uniform edge weights. I would like to extract from this graph a spanning tree (an arborescence) with the property that the total distance between all pairs of leaf nodes (the sum of combined distances from each pair's nearest common ancestor) is minimized.

What I'm ultimately trying to accomplish is to find the best way of ordering the leaf nodes in such a way that the most closely related nodes are closest to each other in the list. If I can find the spanning tree as described, I can easily order the leaf nodes in the way I need.

Can anyone point me to a solution to this problem other than just brute force optimization?

Note that the tree that I seek does not need to span all nodes in the graph, only all leaf nodes and the root node. Also I'm willing to adopt a solution that is not globally optimal if it avoids the need for a brute force search. At the moment I'm investigating an approach involving searching and pruning paths beginning at the leaf nodes.


texts: Are there any paradigms that describe how to save program state checkpoints that can be restored later?

texts:
I was wondering if there were any paradigms that describe how to save "state checkpoints" in a program so that a user may go back and reopen a program to the given state.

In my situation I see that there are many ways to do it each with their own drawbacks. I wanted to know if there is a way that has proved to have the best performance over most all cases of the problem?

What I think would be the most popular system is one that saves state changes, then when a user wishes to return to a previous state it walks the changes backwards until it reaches a specified time stamp reversing the changes along the way.

Or is this problem just application specific.


texts:
Given positive numbers $x_1,x_2,\ldots,x_n$, a positive integer $k$, and a positive real number $D$, determine whether we can divide the numbers (according to the ordering) into $k$ parts so that each part has sum at least $D$.

A simple greedy algorithm works here: Find the least $i_1$ such that $x_1+x_2+\ldots+x_{i_1}\geq D$, then the least $i_2$ such that $x_{i_1+1}+x_{i_1+2}+\dots+x_{i_2}\geq D$, and so on. If we can get at least $k$ parts, the answer is yes. Otherwise the answer is no.

Assuming that we're allowed to query the sum of any subset of the $x_i$'s, this algorithm takes $O(k\log n)$ queries. Is there an algorithm that takes fewer queries?


texts: How to prove the following: Every set is Turing reducible to itself

texts:
Question:
Prove the following:  Every set is Turing reducible to itself.

If anyone can provide a solution that would be great, I've just been introduced to computation theory so be as descriptive as you like for my sake if not strictly for the answer. Thanks!


texts: Why Church-encoded types aren't sufficient to express inductive proofs?

texts: I've heard some claims that the calculus of constructions without inductive types isn't powerful enough to express proofs by induction. Is that correct? If so, why isn't the Church-encoding sufficient for that?


texts: How to compute quotient subgroup efficiently?

texts:
Let $G$ be a finite group given by the table representation and a normal subgroup $H$ of $G$ is given. I want to compute $G/H$ that is quotient group.

Model of computation is RAM

For all pair of $a$ and $b$ in $G$ just check $a.b - b.a = 0$ , but it is going to take much time $O(n^2)$. Is there a faster algorithm to solve this problem?


texts:
I am wondering is anyone has something like a cheatsheet with all the operations between $O(n)$, $\Theta(n)$, $\Omega(n)$, $o(n)$, $\omega(n)$. For example, this is something I don't know how to solve:
$$\frac{\Theta(n)}{o(n)} =?$$
There are not many combinations and I was wondering if anyone could help me.


texts: Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$

texts:
So far we have learned Recursion Tree, Substitution Method, and Master's Theorem.
I'm not sure how we can find lower AND upper bounds.
I know that using Master's Theorem, we get $T(n) = \Theta(n^4)$, but how can I find both upper and loewr?


texts:
I've been playing around with an alternative to the standard object-oriented paradigm for modeling data, and I would like to know if there is any research or already existing systems along the same lines. Let me briefly explain my ideas.

What I call the object-oriented paradigm goes something like this. Objects are representations of physical entities or concepts. An object can consist of components (other objects), and have various attributes and methods (member functions). For example, a car can be represented by an object having four wheels, a gas pedal, a steering wheel, and various methods for driving around. Moreover, each object is part of a type (or class), defined as a set of objects having the same kinds of attributes and methods (like the class of all cars). Importantly, these attributes and methods are in some sense an integral part of the object; the object is composed of its parts. So the car objects represents the whole physical thing, including all its parts and its behavior. (I'm sure this stuff is very familiar to you.)

Now, for various reasons I'm considering a fundamentally different view, which we might call the network-oriented paradigm. In this view, objects do not exist. Instead, each physical entity or concept is represented by one indivisible atom, which by itself carries no information. Instead, all the information about the entity --- its attributes and methods --- are encoded as links to other atoms. For example, a car atom would have links to four wheel-atoms, one gas pedal atom, one steering wheel atom, and to various methods for driving cars around. The key difference is that, in this network view, these atoms that are connected to the car atom are not part of the car. There is no sharp "boundary" defining what is "part of" or "inside" an entity, only links connecting atoms to provide them with attributes and behavior. Moreover, atoms are not typed, at least not in the usual object-as-instance-of-class sense. Any atom can connect to many other atoms, resulting in a kind of network (hence the name). I think this view is more flexible in various ways; for example, one can easily create a version of a car with three wheels by simply removing one of the links, without having to redesign an entire class hierarchy. And I also like it better for philosophical reasons :)

Question: does anyone know of an existing system or language, or theoretical papers where something like this has been explored?

I haven't found anything similar in the literature when googling, but I'm not a theoretical computer scientist (I work in computational biology) so I just might not know where to look. I'm experimenting with a network-oriented system like this on my spare time, mostly for fun, but I also think data modeling along these lines would be more useful in my field than the object-oriented tools we have now.


texts:
What is the complexity of the following algorithm in Big O:
for(int i = 2; i < n; i = i^i)
{
    ...do somthing
}

I'm not sure if there is a valid operator to this type of complexity.
My initial thought was as follows:
After $k$ iterations we want: (using tetration?)
${^{k}i} = n \implies k=\log\log\log..._k\log{n}\implies\mathcal{O(\log\log\log..._k\log{n})}$ (where we have k times the log function) but i'm not sure if this is evan a valid way of writing this.
Anyway, we have a complexity that that includes $k$, which does not seems right to me.


texts: Reduce the total internal border of a set of touching rectangles (using graphs)

texts:
I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas

I will go over the algorithm, however the final structure still consisting of rectlinear rectangles has a more complex representation as shown below. I think it will still work.

Possible steps

Example of a Real World problem


texts: algorithm for predicting procces's memory/cpu usage based on other other prior/still running jobs

texts:
In a 'pool' with a lot of  cpus ,jobs(processes) are running(lots of them) .

Given I have  time/resource usage 'samples' from many prior/still running jobs - how would you go about trying to predict the process resource usage ?

Very abstractly , what I think should be done is as follows :

1) New job is submitted and start running and I wait for some time to gather resource usage information/samples

2) find a subset of jobs that their  'behave' (up until that point in running time) 'similarly' - how would u do that ? maybe those who are always in a specific margin and also there average distance is closest ?

3) choose one job from the subset I found at stage 2, and give prediction of resource usage based upon that job..

Are there known/standard way for my objective ? Would love to hear your ideas,direction etc ..


texts: Raft algorithm: What's the data format of `term`?

texts:
Time is divided into terms, and each term begins with an election. After a successful election, a single leader manages the cluster until the end of the term. Some elections fail, in which case the term ends without choosing a leader. The transitions between terms may be observed at different times on different servers.

In Raft algorithm, term is a limited period of time, and widely used in leader election, log replication.

What's the data format of term?
Is it composed of Unix timestamp and length ?
How does every node guarantee their timestamp are synchronous? (Google Spanner use Atomic clock to guarantee true time).


texts: Cost of computational representation in PAC-learning definition

texts:
I'm currently reading Foundations of Machine Learning by M. Mohri, A. Rostamizadeh, A. Talwalkar and according to their definition a concept class $C$ is said to be PAC-learnable if

$$Pr_{S \sim D^m}[R(h_s)\leq\varepsilon] \geq 1-\delta$$

holds for any sample size $m \geq poly(1/\varepsilon,1/\delta,n,\mathrm{size}(c))$.

I have problems understanding the definition of the parameters $n$ and $\mathrm{size}(c)$. The book defines them as follows:

  We denote by $\mathcal{O}(n)$ an upper bound on the cost of the computational representation of any element $x \in \mathcal{X}$ (the input space) and by $\mathrm{size}(c)$ the maximal cost of the computational representation of $c \in C$.

A general answer would be greatly appreciated but I also have two examples I would like to understand in detail:

Axis-aligned rectangles: Each rectangle can be represented by its corners which are points in $\mathbb{R}^2$, so the computational cost is constant. Therefore, $poly$ is actually a polynomial in $1/\varepsilon$ and $1/\delta$, correct?
Universal concept class: Consider $\mathcal{X} = \{0,1\}^n$ and let $U_n$ be the concept class formed by all subsets of $\mathcal{X}$. Here the computational cost for an element $x \in \mathcal{X}$ is $n$, so $poly$ is a polynomial in $1/\varepsilon, 1/\delta$ and $n$ … ?

Especially the second example illustrates my problem very well: Taking $n$ as an additional parameter only makes sense (imho) if one considers all concept classes $U_n$ at once, because for a fixed class $U_n$ the cost of the computational representation is again constant.

I think my problem is that I don't understand the part

  … denote by $\mathcal{O}(n)$ an upper bound on the cost …

I assume that this is big O notation, but how can we say that $\mathcal{O}(n)$ is an upper bound on the cost?
And why can we not say that it is constant in the second example?


texts: Does the following modified Two-Phase Locking protocol ensure serializability and freedom from deadlock?

texts:
Consider the following variant of the two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects ${O_1,...,O_k}$.

The modified algorithm works as :

Step 1. $T$ acquires exclusive locks to $O_1, . . . , O_k$
in increasing order of their ids.

Step 2. The required operations are performed.

Step 3. All locks are released.

Does this protocol ensure serializability and freedom from deadlock?

Since the locks are being obtained in an increasing order of their ids, the circular wait condition cannot prevail and a deadlock can thus be avoided. But does it ensure serializability? How to argue with respect to the serialization aspect?


texts: Proving that $ (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$?

texts:
How would I prove that these two regexes are equal to one another? $$ (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$$

I'm permitted to use the following regular expression identities.


texts: Byzantine Generals Problem - Regular Set of Neighbors

texts:
Going through Lamport's paper, I'm a little confused by the second part of the regular set of neighbors definition.

  A set of nodes $\{i_1, \ldots, i_p\}$ is said to be a regular set of neighbors of a node if :

  each $i_j$ is a neighbor of $i$, and
  for any general $k$ different from $i$, there exist paths $y_j,_k$ from $i_j$ to $k$ not passing
  through $i$ such that any two different paths $y_i,_k$ have no node in common
  other than $k$.

  The graph $G$ is said to be $p$-regular if every node has a regular set of
  neighbors consisting of $p$ distinct nodes.

I'm assuming $i_j$ is a node in the set. Is it right to assume $k$ is any other node not $i$ or any node not $i$ and not in the set? Also, is it saying that every $y_j,_k$ path will not have a common node or that there must be some $y_j,_k$ paths that don't share a common node?

I put the example graph from Lamport's paper with some labels on the nodes (that was edited with a track pad. Sorry!) just in case it'll help give an explaination. Any and all help is much appreciated!


texts: Is it undecidable if the language of a given Turing Machine is the set of composite numbers?

texts:
I am aware that the following problems are undecidable and tried to reduce the given problem to one of the following but with no success:

Halting problem
Blank Tape Halting problem
State-Entry problem
If a TM accepts nothing
If a TM accepts everything

I am looking for hints :)

Do I have to make multiple reductions?

Do I have to make a contradictory argument like we do for the Halting Problem?


texts: Is it necessary for a Push down Automaton (PDA) to have a stack?

texts:
I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA:

Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed?


texts:
It's been a long time since I've studied time complexity in school, but I've been tasked with finding the time complexity of an algorithm.  Here is the algorithm in a pseudo-pseudocode (yes, two pseudos because I'm not good at creating pseudocode.  Haha!).

main()
{
  list = methodImportFromCSV(...)   // Don't care about this line's complexity

  tree = createRootNode()    // O(1)

  DO
    count = tree.createChildren(list)
  WHILE count > 0
}

createChildren(list) : returns integer
{
  nodesCreated = 0

  foreach (node in this.children)
  {
    nodesCreated += node.createChildren(list)
  }

  groups = separateIntoGroups(list) // O(n)

  foreach (group in groups)
  {
    if (someMethodThatReturnsTrueOrFalse(group) = true) // Some method is O(n) of the group
    {
      this.children.Add(new child())
      nodesCreated += 1
    }
  }

  return nodesCreated
}

You can see that the method is recursive and just creates a tree structure.  I remember a few things just as linear iteration is [O(n)], but I've never had to deal with recursion before.  Is it permissible to state that the algorithm is running at O(n * t)?  Perhaps I am wrong?  I thank you, all, for your assistance.


texts: Reconstruct directed graph from list of ancestors for each node

texts:
I have a problem that I encountered that boils down to the following:

Considered this directed graph I found on Google:

I have the following information available to me

Node: Ancestors

1 : 3
2 : 1 3 5 7
3 : Null
4 : 3 5
5 : 3
6 : 1 2 3 4 5 7
7 : 1 3
8 : 1 2 3 4 5 6 7

How can I re-construct the original graph in a reasonably efficient manner? I basically have large sets of data that I would like to have visualized as branches and merges(similar to a code repository, but not quite).

Note: While I believe my data shouldn't be disjoint, I'm somewhat certain my data is incomplete and will produce disjoint graphs, or at the very least have many separate "roots". There is no ordering to the data, everything must be considered random, the lists can also be thought of as sets.


texts: Time complexity of $L=\{a^nb^n | n \ge 1\}$

texts:
Consider the following language:
$$L=\{a^nb^n | n \ge 1\}$$
I constructed the following Turing Machine:
\begin{eqnarray}
T &=& (Q, \Sigma, \Gamma, \delta, q_0, B, F) \nonumber \\
Q &=& \{q_0, q_1, q_2, q_3, q_4\} \nonumber \\
\Sigma &=& \{a, b\} \nonumber \\
\Gamma &=& \{a, b, X, Y, B\} \nonumber \\
F &=& \{q_4\} \nonumber
\end{eqnarray}

When the input comes as $aabb$, the Turing Machine works like this:

How can you know the time complexity of this Turing Machine?


texts: Find number of triples that sum up to zero in query-intervals

texts:
My problem is that we have an array of $N$ integers $(N <=5000)$ on the interval $[-10^6,10^6]$. We also have $Q$ queries $(Q <= 10^5)$ giving us some range in the array.

For each query, we want to find the number of triplets of indices in the range such that the sum of those array values equal to zero. More formally we want to find the number of ways we can choose unordered distinct triples $i, j$ and $k$(within the given query range) such that $a[i]+a[j]+a[k] = 0$.

I'm thinking of doing an $O(N^2)$ pre-computation and $O(\log N)$ time for each query but I am unable to come up with a concrete working idea. Any help would be appreciated.

Edit: queries can be processed offline, as the array does not need to be updated.


texts: regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$

texts:
$r_1=\Lambda+(a+b)^*b$
$r_2=(b+aa^*b)^*$
$r_3=b+\$+aa^*b+(b+\$+aa^*b)(b+aa^*b)^*(b+\$+aa^*b)$

For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, then i used FSM2Regex which gave me $r_3$ which i simplified into $r_2$ using regex simplifier.
now $r_2$ seems better than $r_1$. Should I go with it? If so, what is lacking in $r_1$? I can't see the difference between $(a+b)^*b$ from $r_1$ and $(aa^*b)^*$ from $r_2$. Is one the subset of other? Are they overlapping or disjoint?

Inputting any of the three RE's back into FSM2Regex gives RIDICULOUSLY complex TG's especialy because for some reason that is beyond me, it also draws $\$$ (null string) transitions. Even $r_3$ doesn't give back the FA I used to generate it. So my question is : are $r_1$ and $r_2$ different? How? what should I go with?


texts: Worst case running time to search for an element in a balanced BST with $n2^n$ elements

texts:
What is the worst case running time to search for an element in a balanced binary search tree with $n 2^n$ elements?

The answer is $\Theta(n)$.

My answer:

To search an element in BST is $\log (n)$ so
$$
\begin{align*}
\log(n 2^n ) &=  \log(n) + \log(2^n) \\
            &=  \log(n) + n\log 2 & \text{(base is 2)} \\
            &=  \log(n) + n
\end{align*}
$$

  Why have they used $\Theta$ in the answer?
  And why only $n$?


texts: Algorithm to find most nodes in distinct cycles

texts:
I am trying to design a program where people trade objects within a fixed set of objects.   They offer a single product, and designate a set of products they are willing to accept for that product.  The job of the program is to involve as many people in a trade as possible.

To do this, I create a directed graph, where each edge points from a person who will give a product to a person who wants that product.

I want to find the distinct cycles (they don't share a node) that cover the largest subset.

How would I do that?


texts: If DFA has two states, which of the conditions hold?

texts:
Let $L$ be a regular language ,and $M = (Q, Σ, δ, q_0, A)$ is a DFA such that $L(M) = L$.
 Prove that if $|Q| = 2$ then one of the following holds :
a) $L=∅$ b) $ε∈L$ c) $∃a∈Σ$ and $a∈L$

The problem is, I think all of these are FALSE. If there is 2 states, none of them are accepting states, then L will have no elements. This disproves b) and c). However if one of the states is accepting, then a) is false !
I dont see how one of these statements is always true.


texts:
I am reading Sipsers. The book introduces halting problem and proves that is a turing recognisable language but not a turing decidable language. Thus giving a Turing machine which does not halt on some inputs. The language to be precise is
$L=\{\langle M,w \rangle| \ M \text{is a turing machine and } w \text{ is a string M accepts} \}$. Let $D$ be the turing machine that recognises $L$. Inability of $D$ to halt on some inputs is due to the fact that there exist Turing Machine $M$ which do not halt on some input. Thus the reason for not halting is kind of recursive ( if I consider only this example ).
I am still not able to understand in crux why a turing machine won't halt. But can't come up with language over $\{0,1\}$ which is turing recognisable but not decidable. What are all the reasons a Turing machine won't halt ?


texts: Number of conflict serializable schedules

texts:
Two transactions $T_1$ and $T_2$ are given as:
$$T_1: r_1(X)w_1(X)r_1(Y)w_1(Y)$$
$$T_2: r_2(Y)w_2(Y)r_2(Z)w_2(Z)$$
where $r_i(V)$ denotes a read operation by transaction $T_i$ on a variable $V$ and $w_i(V)$ denotes a write operation by transaction $T_i$ on a variable $V$. The total number of conflict serializable schedules that can be formed by $T_1$ and  $T_2$ is _______________

I have tried finding the total number of schedules – nonconflict serializable schedules, but I think there is a higher possibility in committing mistakes in the exam for that method. Please suggest a better way to solve this.


texts:
I have a question about predication and branch prediction.

I've emailed my professor regarding this and he replied me that predication has a less instructions than branch prediction.

So I tried making an example of my on but I'm not sure if this is right..

I've assumed for predication it has 'if' and 'else' each having 100 instructions.
Then either right or wrong, it will waste 100 instructions.

For prediction(since this has more instructions), I've assumed it has 'if' and 'else' each having 300 instructions doing exactly the same thing as the predication above.

My questions is..

Is it even possible to make 300 instructions to 100??
In above case, if predication has to win over the benefit of branch prediction, accuracy of prediction should be below 66.6%.
(300*0.3333=100) Is this correct?
If so, when deciding which would be better off than which, does it has to be based on accuracy of a prediction or the size? Reason why I am mentioning size is because during the lecture, I remember my professor saying "use predication in small size loops..."

Thanks in advance..


texts: Are all language over $\Sigma= \{0\}$ decidable?

texts: I have problem in determine whether it is decidable or not, can somebody help me please


texts: is it possible to create an avl tree given any set of numbers?

texts:
I am studying balanced trees, especially AVL trees. My question is whether is it possible to create an avl tree given any set of numbers. is it possible to prove the following statement?

Let $A$ be the set of integers. Given any set $A$, it's possible to create an avl tree corresponding to the given set of numbers.

Is there any way to prove or work out the above statement? I appreciate your answers.


texts: Algorithm for Estimating Number of Unique Monthly Visitors

texts:
Is there a way to estimate the number of unique monthly visitors to a site based on a limited sample of one week of data? I have information about when a given user visited the site. This isn't as simple as just multiplying the number of unique visitors the first week by 4, due to the hotel problem. If 10 people visit your site the first week and the same people are the only visitors to your site the second, third, and fourth week, the total number of monthly unique visitors to your site is only 10.
I know you can use HLL to estimate the number of unique visitors to a site in O(1) space. I'm wondering if there's a similar approach to estimate how many unique visitors there will be after a month, preferably that also works in O(1) space.


texts: Approximating Deep Neural Networks (DNNs) with Binarized Neural Networks (BNNs)

texts:
I am working currently as a research intern on Binarized Neural Networks where the weights and the activations of the network are binary. The architecture of this type of networks makes them memory efficient and computationally efficient, which makes them ideal for resource constrained environments, like embedded devices and mobile phones.

The interesting part about BNNs is that we can encode a binarized network as a CNF formula (Boolean Formula). Using this formula, we can verify some properties of the network like Robustness against adversarial examples (carefully crafted samples looking similar to usual inputs but designed to mislead a pre-trained model). We can also extract explanations that support neural network decisions, hence make the neural network explainable.

Currently, I am trying to make a DNN explainable by verifying its decisions using BNNs. The first direction of research is to reduce a DNN to a BNN. Of course the two networks should be equivalent. I am researching ways to make this reduction but I haven't found any works in the subject.
Is it possible to carry out this transformation ? Is there any techniques that can "binarize" a DNN ?

Thanks :)


texts: How are image processing and computer vision related to artificial intelligence.?

texts:
We have often heard both terms image processing and computer vision in AI sessions

But i am confused, how they both are related to artificial intelligence?


texts: What are the units for time complexity graphs?

texts:
I often see big-O notation for time complexity algorithms and I see an equation that looks like $O(n) = n\log n$, which naturally generates a graph like the bottom one:

I know the x-axis represents some amount of information, and the y-axis represents some amount of time. However, what is the amount of actual time or data represented, does it depend on different types of computers or is it a standard (e.g.) bytes to seconds or KB to minutes?


texts: Dependent type system with different computation model

texts:
There exist various Turing-equivalent models of computation, such as lambda calculus, Turing machines, or register machines.

It seems that dependent type systems (like Coq, Agda, Idris, homotopy type theory) all have a lambda-calculus-based model of computation at their core. That's because they use term substitution ($\beta$-reduction) to relate the typing model to the computation model.

Can we swap out the lambda calculus at the core of dependent type systems for other computation models?

Or more generally, can we formulate a type system that lets us plug in our own computation model and its inference rules, subject to some set of consistency rules?


texts: What is the loop invariant of the following function?

texts:
x = n; y = 0

while x >= b:

   x = x DIV b

   y = y + 1

return y

This function takes in $n,b\in\mathbb{N}, n > 0, b > 1$, and returns $k\in\mathbb{N}$ such that $b^k\leq n \lt b^{k+1}$

So far I think it is:

$b^y \leq n$

$x \leq n$

but now I'm stuck


texts: Maximum-weight set of cliques of size 3 with no common vertices in undirected graph

texts:
I'm looking for an algorithm/insight into a problem that's an extension of the Maximum Weight Matching problem. The maximum weight matching problem looks for the max-weight set of edges that contain 0 common vertices. The problem can be thought of as grouping the vertices into sets of 2 such that no vertex belongs to more than 1 group.
I'm looking to extend the problem such that the vertices can be split into groups of 3. For an undirected graph, this translates into looking for cliques/cycles of size 3 that do not contain common vertices. Any guidance on how to approach this problem either deterministically or with an approximation/heuristic algorithm?
Note: the graphs I'm working with are typically dense


texts: Resource Allocation problem using Deep Reinforcement Learning

texts:
I am working on a resource allocation problem, and I need some help.
I have a few Jobs (J) and few Machines (M) to complete them.
Each job has a size (s_j), resource demand (c_j), and a delay bound (d_j).
Now the size of the job (and therefore its resource demand) can be partitioned into smaller units (say into L levels, with k = s_j/L resolutions, k being the smallest divisible unit) and can be allocated to the Machines. I need to allocate the resources to the tasks in such a way that the delay is minimized. (violation of the delay bound will come as penalty).
This is an online scheme, and at each time steps, such jobs arise. I am thinking of Reinforcement Learning to solve it. (Any other solution approach is also welcome)
Essentially my actions at each time steps are three matrix - B, F, X.
B = How the jobs are partitioned. Here, b_nm = job j is partitioned into the task size of b_nm (a multiple of smallest unit k) and allocated to Machine M. (sum of b_nm over m = s_j)
X = Association matrix consists of (0 or 1) values. If x_nm = 1 that means task n is allocated to machine m.
F = Resource allocation matrix. f_nm (0 to 1) is the fraction of the total resource (assume this is a discrete set, i.e., discrete action space) that is allocated to task n in machine m.
Is Deep Q learning a good approach to solve it? Given the action space set is quite large. Or should I try policy gradient methods?
More importantly, what should be the NN architecture? Given the structure of the problem, can CNN provide better performance here than FNN?
Any suggestions/comments are welcome.


texts: Relation and difference between information retrieval and information extraction?

texts:
From Wikipedia

  Information retrieval is the activity of obtaining information resources relevant to an information need from a collection of information resources. Searches can be based on metadata or on full-text indexing.

From Wikipedia

  Information extraction (IE) is the task of automatically extracting structured information from unstructured and/or semi-structured machine-readable documents. In most of the cases this activity concerns processing human language texts by means of natural language processing (NLP). Recent activities in multimedia document processing like automatic annotation and content extraction out of images/audio/video could be seen as information extraction.

What are the relations and differences between information retrieval and information extraction?

Thanks!


texts: Decide whether there exists a walk of weight exactly k

texts:
Consider the following problem:

Input: a directed graph $G = (V,E,\omega)$ where $\omega : E \longrightarrow \mathbb{Z}$, two vertices $v_1, v_2 \in V$, and a weight $k \in \mathbb{Z}$

Question: Does there exist a walk from $v_1$ to $v_2$ with weight exactly $k$?

The weight of a walk is simply the sum of all edges in the path. Note that the walk can contain cycles.

Is this problem decidable?  Is there any algorithm to solve this problem, if I don't care about the running time?  My problem is that since we can have edges weighted with either positive or negative integers, it is hard to determine when to stop or turn back when it gets too low or too high.

For example, given the graph $G$ where $V = \{ v_1,v_2 \}$ and $E = \{e_1:(v_1,v-1), e_2:(v_1,v_2)\}$ and $\omega(e_1)=-2$ and $\omega(e_2)=1$, the question could be is there a walk from $v_1$ to $v_2$ with weight $-99$. The algorithm should say yes, as there is a walk starting from $v_1$ and self looping 50 times over edge $e_1$ before taking edge $e_2$ and terminating.

I previously asked about the complexity of a similar problem here, but there I was focused on the complexity of the problem.  Others have shown that this problem is NP-hard.  Also, the previously question asked about a path, whereas here I am asking about a walk (a vertex might be visited multiple times); the version with paths is in NP and thus decidable, but here I am asking about walks rather than paths.

Notice that this problem is not trivial, largely because we are talking about walks rather than simple paths.  There is no a priori upper bound on the length of a walk from $v_1$ to $v_2$, so just enumerating all possible walks might never terminate.  Also, the graph could contain exponentially many cycles, and the walk might visit some of them any number of times.  And, there is no obvious upper bound on the number of times that we traverse any given cycle.  In particular, it is not obvious whether this problem is in NP or not.  A straightforward reduction to integer linear programming (an integer variable for each edge, counting how many times the walk traverses that edge) runs into the difficulty that it is not clear how to ensure that you have a walk and not a flow.


texts: The Taylor series and time complexity analysis

texts:
I was just wondering, if an algorithm $A$ has a time complexity O$(2^n)$, since $2^n$ can be represented using a Taylor series, which is a polynomial, does this mean that $A$ has polynomial time complexity? Generalising even further, does this mean that any algorithm which has a time complexity O($f(n)$) where $f(n)$ has a corresponding Taylor series representation is also a polynomial time algorithm?

Thanks very much in advance.


texts:
I’m an amateur in the study of algorithms. For a while I’ve had a burning question, why  do we study complexity theory in computer science? The reason I ask is because algorithms with better asymptotic complexity are not always faster for practical purposes, in fact they can be absurdly slower. Why not instead develop a theory that better suits the practical needs of scientific research and industry?
As an example, it is known that developing an algorithm to determine a perfect chess game can be done in $O(1)$, as the number of legal chess games on an 8×8 grid is bounded from above. However, I have heard this algorithm would take longer than the age of the universe to terminate. This begs the question, why complexity theory? It seems to me the field is fundamentally flawed, and computer scientists should be using a better approach for the study of algorithms.
(Note: My sincere apologies to researchers in the field. ☻)


texts: If I have some source sending codewords and I take a large sample of codewords in order to construct an empirical distribution of the codewords sent. Using this empirical distribution, what methods can I use to demonstrate/prove (statistically) that the source is not a Markov source?


texts: How do real numbers like Pi, golden ratio, etc fit into type theory

texts:
In type theory, all computable functions must terminate, however, numbers like Pi are non-terminating real numbers, hence a non-terminating function is required to compute this number, even though one would never compute the full sequence.
How does type theory view/deal with such non-terminating numbers/object?


texts: Compute sums of all subsets of some words

texts:
We have $16$ words of given length, let's say $W_1,...,W_{16}$ and  and i want to make an one dimensional matrice that will contain all the possible sums of $W_i$'s, for example:

$W_1,W_2,...,W_{16}$

$W_1+W_2,W_1+W_3,...,W_1+W_{16}$

$W_2+W_3,...,W_2+W_{16}$

and so on, all the by two sums...

then all the three sums

$W_1+W_2+W_3,...,W_1+W_2+W_{16}$

then all the four sums

until the sums which is all by sixteen

$W_1+W_2+...+W_{16}$.

Is there a faster way for example, than using a triple $for$ to make all the possible by three sums and in general n fors to make all the by n sums?


texts: All string matches for regular expression

texts:
Given a regular expression, the ask is to find all matches in a string, str.
Most implementations give longest match only. For example, [\d]* in str "123456", the regex libraries in C++ or python only provide the longest match, i.e. { "123456", "" } at position 0 and 6 respectively, and that too after iterating over the string matches.
,
How can one obtain all matches like { "" , "1", "12", "123", "1234", "12345", "23456","2","23","234", "2345","23456", ... and so } with C++ regex libraries.


texts: What is the compressibility of this simple "book"?

texts:
Compressibility is defined as

$$C=\frac{2^{HN}}{2^{H_{max}N}}$$

The book is made up of a simple alphabet of only {a,b,c,d} which occur with probabilities $$P(a)=0.2, P(b)=0.4, P(c)=0.1, P(d)=0.3$$

In class we were given the example of calculating the entropy of a simple string of coin tosses, where $N$ is the number of coin tosses.

So, for example, we could say that $P(heads)=0.1$ and $P(tails)=0.9$. The entropy of each coin toss is therefore $H(p=0.9)=0.469$ If we toss the coin 4 times then we end up with a compressibility of:
$$C=\frac{2^{HN}}{2^{H_{max}N}}=\frac{2^{0.469\cdot4}}{2^{1\cdot 4}}=22.3\%$$
How do we extend this to the book case?

The entropy of the letter occurance is $$H(p=0.2,p=0.4,p=0.1,p=0.3)=1.85$$

and the maximum entropy is just 2 bits (i.e. we require 2 bits to descibe four characters)

Since this is all the information given in the question, I presume that we just set $N=4$ and plug in the values for $H$ and $H_{max}$ to get the entropy. However, I am struggeling to see why. Why is $N$ not the number of letters that make up this book?


texts:
In Sipser's text, when proving that there exists an oracle $A$ such that $P^A \ne NP^A$, he writes:

  Let $M_1, M_2, \ldots$ be a list of all polynomial time oracle TMs.

I understand that there are countably many Turing machines, but aren't there uncountably many oracles?


texts: Relation between interactive proof systems (IP), NP, coNP, PSPACE

texts:
I would like to ask you some clarification on the following question:
know that ${\sf NP}$ is a subset of ${\sf IP}$
and also ${\sf coNP}$ it is a subset of ${\sf IP}$.
So ${\sf IP}$ is a biggest class, but how much it is big?

May i say that ${\sf PSPACE}$ is a subset of ${\sf IP}$? or that they may intersect?

Can you give me a easy clarification about it?


texts: Why is my own implementation of Bubble Sort so much slower than another one I found online?

texts:
I wrote my implementation of Bubble Sort according to my understanding of the general principle of how the algorithm works, and then compared it against another implementation I found online.

def my_bubble_sort(n):
    switched = True
    while switched:
        switched = False
        for i in range(1, len(n)):
            if n[i] < n[i - 1]:
                switched = True
                n[i - 1], n[i] = n[i], n[i - 1]
    return n

def some_other_bubble_sort(n):
    for i in range(len(n) - 1):
        for j in range(len(n) - 1 - i):
            if n[j] > n[j + 1]:
                n[j], n[j + 1] = n[j + 1], n[j]
    return n

While my_bubble_sort() is much faster on processing lists that are already sorted, some_other_bubble_sort() is almost three times faster (= takes 35% of the time) compared to my_bubble_sort() on actually random, unsorted lists.

I'm not sure why that is. Can anyone help me understand?

It can't be the additional checks against switched that make my implementation that much slower, can it?

Pastebin link

I also found that my version seems to be fairly close to the one taught at this MIT lecture.

Which one is generally preferable? Are they both valid implementations of bubble sort? Or is either of the two technically another sorting algorithm?

And which one would be preferable, generally speaking?


texts: Quantum computers, parallel computing and exponential time

texts:
I've read that quantum computers can solve 'certain problems' exponentially better than classical computers.  As I think I understand it, it's NOT the same to say that quantum computers take any problems that are EXPTIME-complete, 2-EXPTIME,... and convert them to linear time or constant-time.

I would like to know something more about this matter:

Why can/can't a quantum computer solve exponential problems in sub-exponential time?
Is it at least theoretically possible to imagine a computer (quantum or otherwise) able to solve EXPTIME-complete problems in constant time? Or does this lead to a contradiction?

EDIT  a third related item:

Can quantum computers do parallel computing?

Now that the subject came up from comments, the idea about parallel computing, that's the usual/pop vision about quantum computers, like if quantum computers were able to compute "all posibilities at once" of any given problem (I think if that were the case, wouldn't be necesary to call great Peter Shor to invent a factoring algorithm!). Then "why" question about quantum computers can/cannot do parallel computing is half a computer science and a physics question.

Here a source of confusion: http://physics.about.com/od/physicsqtot/g/quantumparallel.htm


texts:
Definition : Kolmogorov complexity is a static complexity measure that captures the difficulty of describing a string.
For example, the string consisting of three million zeroes can be described with fewer than three million symbols (as in this sentence)
From wikipedia

In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as descriptive complexity, Kolmogorov–Chaitin complexity, algorithmic entropy, or program-size complexity

I am not able to understand few things like " static complexity " and why we need it


texts: Data structure for a queue of weighted elements

texts:
Consider a queue of elements with weights $w_0, w_1 \ldots, w_{n-1}$.  The queue supports two operations:

Inserting one element at the back of the queue
Reducing the weight of one element in the queue
Given a value $W$, remove from the front of the queue the smallest prefix $w_0, \ldots w_{k-1}$ with total weight $\sum_{i=0}^{k-1} w_i \geq W$.

Operations on the queue must be at most $\mathcal{O}(\log n)$ in the worst-case scenario (no randomized algorithm).
One approach that works is to represent the queue as a self-balancing binary tree such as an AVL, using the insertion order as the key and maintaining the total weight to the left of every node and to the right of every node. While this works, it seems a little bit overkill as we never really make use of the general insertion capability of the AVL... here, we only need insertions at the back.
Another possible structure would be a forest of $v$ complete binary trees where $v$ is the number of 1's in the binary expansion of $n$. The forest would basically match the binary representation of $n$. Adding to the back sometimes creates new trees, and sometimes leads to the merging of trees by "carrying the 1". However, some of that structure is lost when prefixes are being extracted, though perhaps it is salvageable.
Are there other structures I should be thinking about which solve this issue?


texts: Value of constants in Big Theta notation

texts:
In Big Theta notation used for defining the running time of an algorithm, are the constants $c_1$ and $c_2$ different for every value of $n$?

Definition:

$\qquad \displaystyle \Theta (g(n)) = \{ f(n): \exists\, c_1,c_2,n_0>0. \forall n \geq n_0.\ \ c_1g(n) \leq f(n) \leq c_2g(n) \}.$


texts: Decidability of Narcissistic Language Using Turing Machines

texts:
I've been working on decidability practice problems and I came across this one in a practice problem set from the textbook An Introduction to Computational Techniques. I know the steps for how to prove a language is undecidable by constructing a Turing Machine which shows that the language is not recursive. However, I'm not sure how to prove that this language is decidable. Does anyone know how to solve this?
The question is:

Prove that the following language is decidable:
$$ \{⟨M ⟩ \mid L(M ) = \{⟨N ⟩ : ⟨N ⟩ = ⟨M ⟩\text{ or }L(N ) = \{⟨M ⟩\}\}$$


texts: What time complexity is more significant?

texts:
A certain algorithm executes $n$ operations of three types: insert, delete, and find.
We know that $n/10$ of the operations are inserts, and the rest are deletes and finds.

You are given two implementations of the algorithm. The first one implements insert in worst case $\Theta(n)$, and the amortized cost of every operation (including insert) is $\Theta(1)$. The second implementation implements insert in worst case $\Theta(\log n)$, and the amortized cost of every operation (including insert) is $\Theta(\log n)$.

Which implementation would you recommend, and why?


texts: Approximating the runtime of a practice problem

texts:
I'm studying for an algorithms exam and came upon the problem :

    for (i = 0; i < n * n; i++) {
        i++;
        for (j = 0; j < (log(n) * log(n) * log(n)); j++) {
            j++;
        }
    }

I figure that line 1 costs $ c_1(n^2) $, line 2 costs $ c_2(n^2 - 1) $, line 3 costs $ \sum_{j=0}^{n^2} \log(j)^3 $, and line 4 costs $\sum_{j=0}^{n^2} \log(j)^3 - 1 $. Am I on the right track? If so, what do the summations get simplified to?


texts:
Are all languages in $\mathbf{P}$?

Note: The definitions of all the symbols and functions here follow the document [1].

The following is my attempt to answer the question. Assume that we design a special Turing machine $M_1$, no matter what the input is, $M_1$ will jump to the state $q_{\rm accept}$ (the accepting state). Because no matter what the input $w$ is, $M_1$ only needs one step to finish the calculation, $T_{M_1}(n) = 1\ \forall n \in \mathbb{N}$. Let $k=1$, then $T_{M_1}(n) \leq n^1 + 1 = n + 1$. Therefore, $M_1$ runs in polynomial time. Then, all languages $L$ are in $\mathbf{P}$.

Reference

[1] S. Cook, The P versus NP problem, [Online] http://www.claymath.org/sites/default/files/pvsnp.pdf.


texts:
Given a graph G, and positive integers k, q, pack the edges of G in (pairwise edge disjoint) connected sub-graphs, each of size (number of edges) at most k, and such that, no vertex is part of more than q of these connected sub-graphs.

What is the closet related problem already studied? What can be said in case we restrict to k=3, q=2, and graphs of maximum degree 3?


texts: Nine-input sorting network of optimal depth with minimum number of comparators

texts:
In the research on sorting networks, two parameters are typically of interest: The number of comparators required and the depth required.
They have practical implications for throughput and latency. Results in latter category are usually easier to achieve than  corresponding results in the former. Already in 1989, Parberry demonstrated that the optimal depth for nine-input and ten-input sorting networks is seven:

Ian Parberry. "A computer assisted optimal depth lower bound for sorting networks with nine inputs." In Proceedings of the 1989 ACM/IEEE Conference on Supercomputing, November 1989, pp.152-161

Not until 2014 was it shown by Codish et. al. that the optimal number of comparators for nine-input sorting networks is 25, while the optimal number of comparators for ten-input sorting networks is 29:

Michael Codish, Luís Cruz-Filipe, Michael Frank, and Peter Schneider-Kamp. "Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten)." In Proceedings 26th IEEE International Conference on Tools with Artificial Intelligence, November 2014, pp. 186-193

In general, sorting networks of optimal depth cannot necessarily be achieved by using the optimal number of comparators. Knuth (TAOCP, Vol. 3, 2nd ed.) states that often "one or two extra comparator modules" are required, and shows (Fig. 51) a  ten-input sorting network of optimal depth seven that requires 31 comparators, that is, two more than optimal.

In a multi-hour search of the literature and the internet at large, I have been unable to find a worked-out example of a nine-input sorting network of depth seven, nor have I been able to find information on the minimum number of comparators needed to construct such network. I am currently unable to construct any nine-input sorting networks of optimal depth with my home-grown software.

What nine-input sorting networks of depth seven are known? Following Knuth, they should require no more than 26 or 27 comparators.