texts:
I'm getting a bit confused about the three terms and their differences: Depth-First-Search (DFS), Backtracking, and Branch-and-Bound.

What confuses me:

Stack Overflow: Difference between 'backtracking' and 'branch and bound', Abhishek Dey: "Backtracking is [always] used to find all possible solutions" and "[Branch and Bound] traverse[s] the tree in any manner, DFS or BFS".
zhaoyan.website: Branch-and-Bound uses DFS or BFS, but usually BFS. At the same time, they say that B&B uses a queue which would mean that BFS is done. So this source seems to be inconsistent with itself.
Constrained optimization: "Constraint optimization can be solved by branch and bound algorithms. These are backtracking algorithms [...]"
*

Here is what I think they are. As it is a question about terminology where I already have an idea what the answer could be, I expect sources.

Concrete and a bit smaller questions:

If we use other tree traversals than DFS (e.g. BFS), can it still be Backtracking?
If we use other tree traversals than BFS (e.g. DFS), can it still be B&B?
If we have a constraint satisfaction problem (CSP) and not a constraint optimization problem (COP), can it still be B&B?
If we have a COP and not a CSP, can it still be Backtracking?
Is B&B a special Backtracking algorithm (or vice versa)?

Depth-First Search

Depth-First-Search (DFS) is a way to traverse a graph:

def dfs(node):
    yield node
    for child in node.children:
        yield from dfs(child)

Example:

The following graph would be traversed in the order A, B, D, H, E, C, F, I, G

    A
   / \
  B   C
 / \  /\
D  E F  G
|    |
H    I

Breadth-First Search

BFS is another way to traverse a graph. For the example graph, the BFS traversal is [A, B, C, D, E, F, G, H, I]

Backtracking

Backtracking is a general concept to solve discrete constraint satisfaction problems (CSPs). It uses DFS. Once it's at a point where it's clear that the solution cannot be constructed, it goes back to the last point where there was a choice. This way it iterates all potential solutions, maybe aborting sometimes a bit earlier.

Branch-and-Bound

Branch-and-Bound (B&B) is a concept to solve discrete constrained optimization problems (COPs). They are similar to CSPs, but besides having the constraints they have an optimization criterion. In contrast to backtracking, B&B uses Breadth-First Search.

One part of the name, the bound, refers to the way B&B prunes the space of possible solutions: It gets a heuristic which gets an upper bound. If this cannot be improved, a sup-tree can be discarded.

Besides that, I don't see a difference to Backtracking.


texts: Given two arrays of length n and n - 1, order the first array such that no partial sum is in the second array

texts:
Two arrays of natural numbers are given of length $n$ and $n - 1$:

e.g.

$A: [a_0, a_1,..., a_{n-1}, a_n]$

$B: [b_0, b_1, ..., b_{n-2}, b_{n-1}]$

All elements of $A$ are unique (can be in $B$), all elements of $B$ are unique (can be in $A$) and
every element of $B$ is smaller than the sum of all elements of $A$.

Find a solution $S$ which is a reordering of $A$ (so f.e. for $n=2, S: [a_1,a_0,a_2]$) such that $S_0$ (0th element) is not in $B$, $S_0 + S_1$ is not in $B$, $S_0 + S_1 + S_2$ is not in $B$, etc.

for example:

$A: [1, 2, 3]$

$B: [1, 2]$

Possible solutions:
$S: [3, 2, 1] \lor [3,1,2]$

Furthermore, there is always at least one solution (seems logical as $B$ contains one less element and all it's elements are smaller than the sum of $S$, but don't see how to prove this fact).

The algorithm I have right now is simply going through the permutations and backtracking if the solution doesn't work out. This takes too long but I'm having trouble finding an alternative. Is there some mathematical property I'm missing?


texts: Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints

texts:
I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'⊂V$ such that $R⊂V'$, $N[V']=V$, $∀v'∈V '[∃r∈R ($path($r', v'$)$)]$ that minimizes the sum of vertex weights in $V'$. Note the path must contain only vertices in $V'$.
In other words, all roots must be in $V'$, the closed neighborhood of $V'$ must include all vertices in the original graph and every vertex in $V'$ needs to have a path to a root.
I have constructed a naive algorithm that takes the powerset of $V$ and checks for each subset if it satisfies the 3 constraints. The first constraint is trivial, the second requires the algorithm to compare the union of $V'$ with $V$, and the third one is done by using DFS (only adding vertices to discovered if they are in $V'$.
I was thinking I could convert the vertex-weighted undirected graph to a edge-weighted directed graph and then run Chu-liu/Edmonds' algorithm to find a minimal spanning arborescence. I tried converting the graph by adding $v'$ for each $v$ in $V$, with an edge $(v,v')$ with the vertex weight. All outgoing vertices from $v$ will now be outgoing from $v'$. The problem is that these auxiliary vertices don't need to be included in the MSA, but Chu-liu/Edmonds' algorithm will include them.
Actual question: Is there a better way to convert the graph, so that I can use this approach, or should I go for another (maybe even easier) approach?


texts: Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o

texts:
New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning.
If you have a given an array such as A[1...n] of numeric values (can be positive, zero, and negative) how may you determine the subarray A[i...j] (1≤ i ≤ j ≤ n) where the sum of elements is maximum overall (subvectors). Regarding the brute force algorithm below, how do you go about analyzing its best case, worst case, and average-case time complexity in terms of a polynomial of n and the asymptotic notation of ɵ. How would you even show steps? Without building out the algorithm?
Thanks in advance.
// PSEUDOCODE
// BRUTE-FORCE-FIND-MAXIMUM-SUBARRAY(A)
n = A.length
max-sum = -∞
for l = 1 to n
    sum = 0
    for h = l to n
        sum = sum + A[h]
        if sum > max-sum
            max-sum = sum
            low = l
            high = h
return (low, high) # No, return of MAX-HIGH

Note: New to the forum, not sure if this is the correct exchange. But I am referring to and referencing problems from https://walkccc.me/CLRS/Chap04/4.1/.


texts:
Given a graph $G = (V,E)$ and an integer $k$, the 1-BDD problem asks if there exists a subset $D$ of at
most $k$ vertices such that the degree of any vertex in $G[V \setminus D]$ is at most one.
Is there any FPT algorithm for the above problem running in time $O^*(2^k)$?


texts:
I've just began a course on logic and learned the following :

De Morgan's laws

Normal forms

How to represent a logical formula (using or, and, not operators) using binary trees

How to get the conjunctive normal form  of a formula

It's obviously not much, but the subject interested me a lot and it was enough to study the 2-SAT and the 3-SAT problems. These two problems were very interesting to study.
I am wondering if there are other classical/interesting algorithms problem in logic (just as 2-SAT, 3-SAT) that can be studied with the little I know about logic?


texts: Determining whether a line between two points in a monotone polygon is a valid diagonal

texts:
Given a monotone polygon, with it's vertices given in counter-clockwise orientation, is there any fast process to determine whether the line between two vertices of that polygon A and B is a valid diagonal of that polygon? A valid diagonal is a line between those two vertices that lies inside the polygon and doesn't intersect or touch any edge of the polygon.

Note : I need to be able to do this checking in constant time for triangulating the monotone polygon in linear time.


texts: Optimizing a join where each table has a selection

texts:
Consider the following query:

SELECT Customer.Name FROM Customer
INNER JOIN Order on Order.CustomerId = Customer.Id
WHERE Customer.Preferred = True AND
      Order.Complete = False

Let's suppose all of the relevant attributes (Customer.Preferred, Order.Complete, Order.CustomerId and Customer.Id) are indexed. How can I evaluate this as quickly as possible?

Standard optimization advice would say that I should do the select on each table first, then the join using sort-merge or whatever the cardinality would imply. But this involves two passes through the data - I'm wondering if there's a better way.

EDIT: I think asking if there was a "better way" was too ill-defined. Suppose we are trying to find $\sigma_a(A)\bowtie_j\sigma_b(B)$. Observe that we can find this in $O(\alpha)$ (where $\alpha$ is the cardinality of $\sigma_a(A)$) with the following pseudocode:

for each a in A:
   find foreign tuple in B  // constant-time, if using hash table
   check if foreign tuple meets foreign constraint  // again, constant time

As mentioned by some answerers, there are various minor permutations (do the for loop over B instead, etc.). But they all seem to be $O(\alpha)$ or $O(\beta)$. Is there a better way?

Note that if it the query were a self join, we could just do the merge part of a sort-merge join, (since our indexes would already be sorted) which would run in time proportional to the number of results. So I ask if a similar thing can be done here.

I am more than happy to accept a proof that there is no better method as an answer. I believe that there is no faster algorithm, but I'm unable to prove it.


texts: Intuition on O(number of leaves) for master theorem

texts:
I am trying to develop the intuition of the master theorem for the case where $a > b^{d}$ [Case 3] in this video. In the video, they say that since most of the work is done at the leaves, we should expect $O(\text{number of leaves})$ but I don't see how that is similar to  $O(n^{\log_b a}$), which one would get from the proof.
I just need the connection to the intuition as in how to see  $O(n^{\log_b a}$) from $O(\text{number of leaves})$ even in the least rigorous way.  I don't need the actual proof. The presenter gets on to the proof where $n$ is a power of $b$ later on, which is easier to follow but I would like to know so that I don't have to look up the material every time I need to check my work. Given the order of the presentation, I suspect that the intuition can be obtained without the proof for now but I could also be wrong and would appreciate being corrected if that's the case.


texts: Importance of Needham–Schroeder Protocol

texts:
I'm working on a paper about model checking on cryptographic protocols and many of the papers I have read, base their approaches in the Needham-Schroeder protocol. I undestand this was one of the earliest security protocols for authentication and that Lowe's findings makes it an interesting protocol to talk about, I get that it is also one of the easiest protocols to explain and that's why it is used on textbooks, I have also read about how it led to the creation of some modern protocols like SSL. However it felts somewhat strange for me that even modern research keeps on using it for their work instead of the fixed version or some other similar protocols.

Does this protocol has a set of features that makes it kinda "perfect" for research about verification or something like that, what am I missing?


texts: Intersection of a language with a regular language imply context free

texts:
Lets say you have a language $L$ and you want to determine if it is context free.
Context free languages intersected with regular languages are context free. Is that enough to prove that $L$ is context free?

Meaning, given a regular language $P$, if
$$L \cap P = T$$
where $T$ is context free, is $L$ is context free?

Let $A  =\{x \in \{a,b\}^{\ast} \mid |x|_a < |x|_b < 2|x|_a\}$
how can I show this is context free? Is the only way to create a PDA or a CFG?


texts:
I came through Josephus problem a little while ago. Problem is stated as follows :

"People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.
The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution."

 Though I was able to figure out O(n) (n being no. of people & k being specified no of people skipped) solution to this problem using DP.I came to know that a better solution for larger value of n exists O(k*log(n)),but unable to figure it out.

Please help me with O(k*log(n)) solution.


texts: Convex quadratic approximation to binary linear programming

texts:
Munapo (2016, American Journal of Operations Research, http://dx.doi.org/10.4236/ajor.2016.61001) purports to have a proof that binary linear programming [1] is solvable in polynomial time, and hence that P=NP.

Unsurprisingly, it does not really show this.

Its results are based on a convex quadratic approximation to the problem with a penalty term whose weight $\mathcal{l}$ needs to be infinitely large for the approximation to recover the true problem.

My questions are the following:

Is this an approximation which already existed in the literature (I rather expect it did)?
Is this approximation useful in practice? For example, could one solve a mixed integer linear programming problem by homotopy continuation [2], gradually increasing the weight $\mathcal{l}$?

Note: After writing this question I discovered this related question: Time Complexity of Binary Linear Programming . The related question considers a specific binary linear programming problem, but mentions the paper above.

[1] Binary linear programming is linear programming subject to the constraint that certain variables can only take the values $0$ and $1$. Integer linear programming can be reduced to binary linear programming by introducing an additional variable for each element of the binary expansion of each variable.

[2] Homotopy continuation methods aim to track the solution of a problem as a parameter is allowed to smoothly vary. In practice, this usually means slightly increasing the parameter, and re-solving the problem, using the previous solution as initial condition. If there solution algorithm fails, then you reduce the step-size. If it passes, you can increase the step-size. There are also homotopy methods that map into differential equations, but those are less relevant here.


texts:
Background
Semiautomated file merging is a critical part of version control systems (all the ones I've used anyway!). This is usually accomplished on textual source code without the tool understanding the underlying language – although semantic merging also exists.
I'm interested in whether merging relational data has been researched, and what the findings have been.
Specifically, I'm imagining that a single relational database is "forked" in to two (or more) independent copies. That independent changes are made to these copies, and that we then want to recombine these databases in to one again, which reflects the changes in each.
What this question isn't
I'm not asking a question about specific technologies here, although that would be interesting. I'm definitely not asking about SQL based technology sepecificaly. I'm also specifically interested in relational data, and not tree data like XML, JSON, or ASTs, etc.
I'm also not asking about integrating heterogeneous databases or information stores, which seems to be the subject of Data integration. For the purposes of this question, it can be assumed that the databases will have the same schema and this doesn't change.
Some ideas about how this might work
Relational data is, basically, sets. Sets, in principle, have (several) sensible merge semantics, even when the common base isn't known, such as for a commutative replicated datatype set.
There are obviously some basic issues, such as generating identities. If identities are simple incrementing numbers, then these become extremely hard to merge. This problem seems to be solved by using globally unique identifiers.
Incrementing identifiers seems to be a specific case of a more general problem. It is an example of inserting a new fact in to the database that has been derived from the current state of the database.
In general, I suspect that any fact added to the database that is derived from the existing facts in the database, rather than simply new information collected from the outside world, is a potential source of difficulty during a merge. I wonder if this is a huge problem, or one that can be avoided for the most part by something like normalisation?
For example: if we adjust a balance by looking up the current balance and adding or decrementing, then this is hard or impossible to merge. However, if we store individual increments and decrements, this information is trivial to merge. When we need the balance, we should compute it from the data we've got.
Problems also arise for integrity constraints. Following naive set merging, a primary key may no longer be a primary key. However, it seems like it might be possible to automatically determine where this could happen from the database schema, and then have the user choose a resolution scheme, or default to some sensible one if such a schema exists. Note: it is possible to keep an audit, show conflicts as they arise, and have a user revert a decision later, as is done with version control systems.


texts: Why would a function be tabulated in advance and then retrieved?

texts:
Given some function and assuming no concern for the time to compute the co-domain for its domain, when might it be preferable to compute and tabulate in advance the co-domain results of the function, and then retrieve it from the table rather than compute it?

For example, if the domain for $f(x)=x^2$ were sufficiently small, why, if ever, would one wish to compute the co-domain and then, for a given x, retrieve the stored value of $f(x)$?


texts: Non-deterministic algorithm to check if a list has some given value

texts:
I know that I can build a non-deterministic algorithm with a CHOICE function that verifies if a value x is in an array in O(1) time complexity.

The usual algorithm to do that is

find (A, x)
    j = CHOICE(1, .. , A.length)
    if A[j] == x
        return VALID
    return FAIL

But, it works because we are able to access the position j directly, in constant time.

So, if I change the problem: instead of an array A, use a linked-list L, then, how can I construct my non-deterministic algorithm using the CHOICE function to check if a value x is in L or not ?

Will it still have O(1) time complexity ?


texts: Moving a set of points in the plane subject to constraints

texts:
I'm new to geometric algorithms and computational geometry, so please forgive me if this is an inappropriate question for this forum.

Let $X$ denote the disjoint union of $n$ one-point sets. Let $f:X\rightarrow \mathbb{R}^2$ be a function subject to some set of constraints $C=\{c_1,\cdots,c_m\}$, where $c_i=(x_{i_1},x_{i_2},l_i)$ is a triplet which represents the constraint that $d(f(x_{i_1}),f(x_{i_2}))=l_i$, where $d$ denotes the Euclidean metric on $\mathbb{R}^2$. Suppose $C$ is fixed. I would like to design an algorithm which takes as input an additional constraint, $c'$. The algorithm should efficiently search some representative subset of the space of functions which satisfy the constraints in $C$ to look for one which also satisfies the constraint $c'$. I would be happy with an approximate configuration (i.e. all constraints satisfied within some $\epsilon$).

Has anyone heard of a similar algorithm they can refer me to? I've been browsing the CGAL libraries for something that may be of use to me, but I haven't found anything yet.


texts: Is this time complexity quasi-polynomial?

texts:
I have been working in the time analysis for an algorithm and finally I got a curve that fits:

$O(2^{(\log_2(N)^{2.01})})$

N is the number of elements.

I'm right to say the above time complexity is quasi-polynomial?


texts: Least Significant Bit (LSB) vs Little Endian - Are they equivalent in anyway!

texts:
For a multiple choice question: What do we call the LSB?
(i)Little Endian    (ii)Upper bit   (iii)Big Endian (iv)Lower Bit

I feel ideally none of them is a true correct choice, but my best bet was (iv) Lower Bit.

However, our professor claims that the correct choice should be (i)Little Endian. He even said "LSB stands for Least Significant Bit which is right most bit of a binary equivalent and it is Little endian format."

I don't agree with the last part i.e. "..it is Little endian format."

My understanding (primarily from the book  “Computer Organization and Design” by Patterson and Hennessy,) is that LSB (and MSB) concepts were introduced to clearly identify bits at both extremes while avoiding any confusion arising due to writing styles like vertically or horizontally which can be confusing when read/written from different directions. Further it (LSB) has nothing to do with byte ordering such as Little endianness. For example any number will have both LSB and MSB, and can be stored in a little endian hardware as much as it can be stored in a big-endian hardware.

Pls let me know if I'm misunderstanding the professor's statement in any way.


texts:
I am trying to understand how camera matching (or match moving) works. I need to build a program that can move the camera in a way to match a 3D object to its projection on an image. For eg. if I had an image of a cube at some angle, the virtual camera must be moved in such a way that the points/vertices of the 3D cube match up with those in the image.

The inputs would be the image and the points on the image that correspond to each vertex of the the object (cube in the above example).

What is the approach I must take? Is there any algorithm that can help?

EDIT:

This is what I have figured out so far.

So this equation gives the relation between the world coordinates and the image coordinates of a point.

This can be expressed as
Xc = R * Xs + T
where R represents the rotation of the camera and T represents the translation.

Assuming the user points out which points belong where on the image, I need to compute the R and T matrices now.

I came across the Tsai Calibration Algorithm Which does solve this algorithm at some point. But as you can guess by the name, the algorithm is not designed for camera matching. Also, I don't have a very strong background in math so I need to figure out how to solve this equation. To make things harder the transition from world coordinates to image coordinates must also be figured out.

I need help with somehow modifying this algorithm for camera matching and in solving the mentioned equation.

Please mention any other methods you know of. I do not need to stick to this particular method.

EDIT 2:
For anyone who needs more information on camera matching:
http://en.wikipedia.org/wiki/Match_moving

But basically the idea is to try and find the location and orientation of the camera from which the actual image must have been taken. Let say I have an image of a Rubik's cube which shows the red and green sides. I also have a 3d model of the Rubik's cube. Now I need to find the location and orientation of the camera such that if I take a picture of the 3d model now then it would look exactly like the image with the red and green sides visible.


texts: What is the complexity class of this variant of Subset sum?

texts:
Let's represent Subset Sum problem with binary arrays instead of numbers.
Example: given two-dimensional array

[1, 0, 0] (4)
[1, 0, 1] (5)
[0, 0, 1] (1)

is there set of one-dimensional arrays, sum of which is equal to

[1, 0, 0, 1] (9)

In this problem sum of bits in each position can have carry-over. If carry-overs are forbidden (bit positions are independent) and we ask instead: are there arrays which sums to

[2, 0, 1]

then what complexity class such problems belong to? In what papers it was studied?


texts: Developing a Context Free Grammar whilst knowing the number of terminals

texts:
I am trying to develop a CFG for the language $L$ defined by:

$L = \{a^{n+2}bba^{n-2} | n > 1\}$

The problem I am having is that I cannot develop the CFG for this language no matter what I try. The closest I can get is:

$S \rightarrow aaaaXbbX$ (Production 1)
$X \rightarrow aX | \Lambda $ (Production 2)

This would be right if we were somehow forced to substitute the same value of the non-terminal $X$ in both its appearances in production 1. However, we can substitute $X \rightarrow aX$ in its first apperance in production 1 and $X \rightarrow \Lambda$ in its second appearance in production 1, thus throwing the balance of $a's$ off as defined in the language $L$.
The first question is, is there even a CFG for this?
Well, I would say according to theory, yes there is because:

I am asked to draw a Determinate Push Down Automata for this language; and
According to theory, every language accepted by a PDA is context-free

Am I correct that there is a CFG to this and what is it?


texts: Since programs are swapped from backing store to main memory why don't they get lost when the computer is suddenly turned off?

texts: So when I play a video, that means the video is moved from backing store to main memory. Then if I remove my laptop's battery all of sudden, that means the video should get lost as main memory is volatile. Why doesn't this happen though?


texts: Recursive definition of a language $ L $ over $ \{a,b\} $

texts:
How would I start the recursive definition of the following language:

L over {a, b} such that L consists of strings in which each
occurrence of b is immediately preceded and followed by an a

The 'and' part is causing me problems with this problem and I don't see a clean way to gurantee the occurence being preceeded and followed recursively.
The recursive definition structure is as follows:
Basis: The base we have to start with for the recursion
Recursive step: How we generat ethe language from the basis
Closure: Trivial to state
My thought process on this:
We can have lambda, because no b's or no a's doesn't apply to the condition.
My attempt so far:

Basis: $ \lambda \in L $
Recursive Step: If $ w\in L $ then $ aw, wa, babw, waba \in L $.

What i don't see is how th break the recursive step to account for being able to place b's anywhere in $ w\in L$ such that the condition is satisfied.


texts:
What's the relation between Abstract Types, Abstract Data Types, Abstract variables and Concrete types?
Is there any sort of connection?
Can someone point to resource other than wikipedia pages for learning more about these topics?


texts:
Let me explain what I want to achieve. I'm working on the coloring book project. On the input, I'm getting transparent images with black borders (Like this). Currently, I've created the 2D Matrix with colors in points. And basing on this Matrix I want to form an array of regions.
Region:
class Region {
    var set = Set<Point>()

    func contains(_ point: Point) -> Bool {
        return set.contains(point)
    }
}

The region represents points that form bordered parts(e.g. gun barrel, button, hat).
My future logic will be this:

Users taps.
Get point.
Find the region that contains that point.
Color all the points in that region.

The problem is that I don't know how to form those regions :). Can you please help me solve this problem? Maybe it's some famous algorithm but I just don't know how to google it properly.
P.S. I hope this is the correct place to ask this kind of question.


texts: Place 4 notorious problems into 2 diagrams (one assuming P=NP, and the other one assuming P!=NP)

texts:
This diagram is on Wikipedia:

On left side we see NP-hard intersecting NP class (assuming P!=NP), on right side we see NP-hard including NP (assuming P=NP)

Where should I place the following problems (assume decisional part)?

Traveling salesman
Subset sum problem
Sorting a list (any problem known to be solvable and verifiable in Polinomial time)
Hanoi Towers

I'm a bit confused because I've seen many versions of those diagrams (I'm not even sure those are correct right now).


texts: Bakery algorithm: How does it work with single-writer safe registers?

texts:
I'm trying to understand the bakery algorithm and read that the Bakery algorithm uses single-writer safe registers. But I am not able to understand the correctness of bakery algorithm with safe registers. Since safe register may return any value that the register may hold If a read does overlap any writes.

 choosing[i] = true;
 number[i] = max(number[0], number[1], …, number [n – 1])+1;
 choosing[i] = false;
 for (j = 0; j < n; j++) {
     while (choosing[j]);
     while ((number[j]!= 0) && (number[j],j)<(number[i],i)));
 }
 critical section
 number[i] = 0;
 remainder section

It is possible to execute (number[j],j)<(number[i],i) while thread j trying to update to number[j]. If the number[j] is a safe register and it returns a value less than number[i] (safe register may return any value that the register may hold If a read does overlap any writes) then we will wrongly wait on the while check.

Is my observation correct or could you please help me to understand why safe register does not matter?


texts: Find a CFG for palindromes with at most three c's

texts:
I'm trying to figure this one out, as I've found the CFG for the palindrome language.
I can't work on a solution that also covers #c(w) <= 3.

Find a CFG for the language
      {w∈{a,b,c} | Reverse(w)=w, #c(w)<=3}?

Would appreciate your help


texts: Regular expression for a string not containing a set of substrings

texts: I'm trying to figure out how to build a regular expression for a language that doesn't contain strings that contain $101$ or $001$. The alphabet is defined as $\{0, 1\}$. I'm stuck on trying to figure out the DFA. Any help would be appreciated.


texts: Run time analysis of a program with nested for loops

texts:
Problem

Let's say we are given a program and we want to find an algorithm  that analyses its asymptotic complexity. This program can only have two types of statements: do_something and the for loop. The for loop is defined as followed.

for <variable> = <from> .. <to>
    <body>

The for loop makes the <variable> iterate from <from> to <to> (except when <from> is greater than <to>, then <body> won't be executed at all)

<body> must be a statement again (so either for or do_something).

<variable> is a lowercase letter a..z except for n, which is defined prior to the program.

<from>, <to> can be any variables defined in the outer loop. Addtionally, <from> can have the value 1 and <to> can be n.

Example:

for i = 1 .. n
    for j = 1 .. i
        for k = j .. n
            do_something

Let $f(n)$ be the number of times do_something is executed as a function of $n$. We want to know the asymptotic complexity of $f(n)$. For a non-negative integer $k$ and a positive rational $C$, we say that $C \cdot n^k$ is the asymptotic complexity of $f(n)$ if:

$\lim_{n \rightarrow \infty} \frac{f(n)}{C \cdot n^k} = 1$

In the above's example, the asymptotic complexity would be $\frac{1}{3}n^3$.

Solution (?)

I could not come up with an efficient algorithm to solve this problem so I looked it up (which was in a foreign language). However, I only understand a portion of it:

  Every for loop will give us inequalities: for i = j .. k means
  that $j \leq i$ and $i \leq k$. First create a directed graph where
  each variable corresponds to one node and for every inequality $i \leq j$
  we create a directed edge from node $i$ to node $j$. If we consider
  the strongly connected components (SCC) then we can notice that if two
  variables $i, j$ are in the same SCC, they must be equal. Now let's
  consider the condensed graph G' (meaning that we consider every SCC as
  one node) and let the number of nodes be $m$. The time complexity
  would be $C \cdot n^m$, where $C = \frac{\text{number of topological sorting in G'}}{m!}$

So I understand that $f(n)$ is a polynomial of degree $m$, but can not explain how the the coefficient of $n^m$ should have the $C$ as described above. Can anyone help me understand this solution?


texts: What is the ideal complexity of a task with (n-1)!/2^(n-1) possible threes?

texts:
I have n elements to connect. Each element has a given length. My objective is to connect all the elements, so that I get one large, with length sum of all elements. The elements must be connected the way the same way they are inputed, but I can choose in what order to connect them. If I connect two elements, they will continue to stay connected. The price of connecting two elements is (the combined length of them (modulo) some value). The objective is to connect all elements together, at the lowest cost.

The lowest complexity I could find is:
O((n-1)!/2^(n-1)), but this can't be the solution, since it is very time-complex.


texts:
In a Turing machine I read that it can go only right or to left. But in my book [elements of theory of computation, Book by Christos Papadimitriou and Harry R. Lewis ] it says that Turing machine operates in two discrete steps
1) put the control unit in new state.
2)Either: replace the symbol already there by the symbol currently scanned. Or
Move read/write head one tape square left or right

In many online tutorials they say you must move read/write head right/left but you may not change state

Can someone please clear the doubt


texts: Any ideas on implementation of a certain image process?

texts: I recently found this music video. While the music is mislabeled, the video part caught my eye. It seems to be transitioning between two images based on shape? I think its a fade-in/fade-out with the images being streched and transformed, but it seems to be specific on the shape in the image. This may be manual, but anybody have ideas on how one might go about something like this automatically? I was thinking it could be possible if you find the "flow" of an image by assigning pixels vectors based on their color compared to their neighbor's colors.


texts:
The DNG specification (page 87) describes a simple algorithm for converting a "fish-eye" photo into a regular photo (just several lines of basic geometry).

The transformation is configured using six numbers: $k_0, k_1, k_2, k_3, c_x,c_y$. Does it allow to represent identity (i.e. not changing the photo at all)? In order to get identity, the $f$ should be always one, so the bracket $(k_0\theta + k_1\theta^3+ k_2\theta^5+ k_3\theta^7)$ should be alwqys $r$.

In other words:

$w(r) = k_0\theta + k_1\theta^3+ k_2\theta^5+ k_3\theta^7$, where $\theta=arctan(r)$

What should be $k$s, so that $w$ is the identity for $r\in[0,1]$?


texts:
Okay so we've been given an algorithm and asked to give an upper bound to its best and worst case
weirdSort(A,r,p)

if r < p

q = (r+p)/2
BubbleSort(A,r,q)
wierdSort(A,q+1,p)
Merge(A,r,q,p)

I'm not quiet sure how to do that.. this is my first time analysing time complexity and I'm quiet lost
I know that an upper bound for BubbleSort is $O(n^{2})$ for worst and $O(n)$ for best, and for Merge is $O(n)$ for both (Merge being the function that merges the arrays in MergeSort)
So for the worst case I have
$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n^{2}\right)+O\left(n\right)\ ➜\ T\left(n\right)\ =\ T\left(\frac{n}{2}\right)+c_{1}n^{2}+c_{2}n$
and for the best case
$T\left(n\right)=T\left(\frac{n}{2}\right)+2O\left(n\right)\ ➜\ T\left(n\right)\ =\ T\left(\frac{n}{2}\right)+c_{1}n$
But now what? how do I handle $T\left(\frac{n}{2}\right)$? What are the steps I need to take in these types of questions? I feel like they've just thrown us in the water without really explaining how to solve stuff..


texts: Is there a non-brute force algorithm for Eulerization of graphs?

texts:
Given some undirected, unweighted, connected, and potentially parallel-edged graph $G$, an Euler circuit may be constructed iff every vertex in $G$ has an even degree.

In graphs with two or more vertices of odd degree (there may only be multiples of two), one must "Eulerize" the graph, connecting the odd vertices with additional edges through other vertices if necessary.

The optimal case for Eulerization is with the construction of only $n/2$ edges, where $n$ is the number of odd degree vertices, but this can only be the case if each odd vertex has an adjacent partner, thus allowing us to connect both vertices with one edge and making them both even.

That being said, most graphs will require more than $n/2$ edges. As humans, we tend to Eulerize graphs by always choosing each pair of odd vertices that are adjacent to one another, and then using trial and error for the rest. However, this does not always work.

For instance, in the following graph, choosing to add an edge between the pair of adjacent odd vertices, $1\leftrightarrow 2$ and using $5$ edges to connect $3\leftrightarrow 4$ results in an Eulerization that costs $6$ edges. However, choosing to instead connect $1\leftrightarrow 4$ and $2\leftrightarrow 3$ yields an Eulerization that costs $5$ edges, even though it did not use the adjacent odd vertices to its advantage.

I know for sure that this problem is solvable, at least by brute force, because the number of pairs of odd vertices which should be connected with some number of edges is finite; specifically, there are $2^{n/2} \Gamma(\frac{n+1}{2})/\sqrt{\pi}$ (Mathematica said so) possible sets of pairs of odd vertices to connect. It's possible to go through each one, linking up each vertex to its partner (finding the shortest path between the two vertices in an undirected graph is probably a challenge within itself, which Wikipedia fails to give a time complexity for).

In the end, the whole deal probably runs in polynomial times exponential times factorial time, which is pretty nasty. I've done some basic research into whether there are algorithms which Eulerize paths, but can't seem to find any.

Mathematica code for graphic:

GraphPlot[
  {1 -> 2, 2 -> 5, 5 -> 3, 3 -> 6, 6 -> 3, 6 -> 7, 7 -> 6, 2 -> 7, 7 -> 8, 8 -> 9, 9 -> 10, 10 -> 4, 4 -> 11, 11 -> 4, 11 -> 12, 12 -> 1, 1 -> 12},
  VertexRenderingFunction ->
    (If[#2 < 5,
        Text[Style[#2, Large], #1, Background -> Yellow], Null] &)]


texts: Is there an algorithm to achieve optimal compression in a "streamed" manner, assuming equal probability of each possibility?

texts:
(Sorry for the question title; edits are welcome.)

Let's say that you have a set of data made of repeating units, consisting of a value with $2$ possibilities, a value with $3$ possibilities, $5$ possibilities, $4$ possibilities, repeat. The total number of possibilities per unit is $2\times3\times5\times4=120\text{ possibilities}$. Assuming that these are all equally probable, that's $\log_2120\approx6.9\text{ bits}$. This means that the minimum space required to represent $1$ unit is $1\text{ Byte}$, but the minimum space required to represent $1000$ units is $864\text{B}$.

The naïve way of producing this compression would be to put them all into a base-120 number, then convert this to binary. However, this requires having access to all of the data at once in order to decompress it. There must[citation needed] be some algorithm that can take in a stream of compressed data, output a stream of decompressed data, and only use finite memory, but I can't find one.

Please describe and explain such an algorithm, if one exists.


texts: Solve the worst case of this recurrence equation

texts:
I am trying to find the worst case $Θ$ bound for the following recurrence equation:
$$
T(n)=\sum_{i=1}^kT(a_i)+n+\lg k\sum_{i=1}^ka_i\quad
where\quad n=1+\sum_{i=0}^ka_i\quad and\quad
a_0\ge a_1, a_2, \dots,a_k\ge 1
$$
By master theorem, with $k=a_0=a_1=n/3$ and $a_2=a_3=\dots =a_k=1$, $T(n)=Θ(n\lg n)$. Now my freind and I guessed that the worst case of $T(n)$ is also $Θ(n\lg n)$, but we are not able to prove it.

My question is, what is the worst case bound of $T(n)$ and how to prove it?

Edit: By worst case I mean that $T(n)$ to be the maximum of the expression I wrote over all $k\ge1$ and $a_0\ge a_1,a_2,\dots,a_k\ge1$ such that $n=1+a_0+\dots+a_k$.


texts: Determining Cumulative Benefit of Orders with Various Items

texts:
I'm working on a project to change the location of items in a warehouse to allow me to ship items together which were bought in the purchase order (currently impossible due to conveyor logistics). The problem is, I don't have enough space to relocate them all and don't know which items to prioritize.

I have a list of orders, each of which has a given benefit associated with it if I can put the items next to each other. One or more distinct items is associated with each of these orders. The goal is to maximize the value of a given number of relocations.

Here's the situation that I believe makes this problem difficult:

Let's say I take the item that appears most frequently as a single item in these orders (call it item A) for my first relocation priority. I then repeat that process for item B, so we will have captured opportunity for single item A orders, single item B orders, and item AB orders.

When I try to repeat this process for item C, I will get benefit from A, B, C, AB, AC, and BC orders. However, if AC orders represent an enormous amount of the opportunity, I would have been better served taking item C as my second priority item, so I would need to change the ranking.

This will only get more complex as items and pairs are added to the list. Does anybody know the best way to prioritize my items?


texts: Pattern recognition and compressing a data

texts: I am given a matrices each with 4 columns such that each element's value is between 1 to 4. Their is recurring pattern between first two digits while other two are random digits of a row. I need to find a pattern and then reduce it's number of elements. I am new to this topic . I don't need a complete solution just a little hint that how should I begin with the problem ? Which lossless algorithm will be good to begin with the problem or I am going completely in wrong direction?


texts: position to insert element in inserionsort (equality of probablity)

texts:
prove that in algorithm insertionsort, for successively considered element a[i] there is equal probablity that element will be inserted in one of i positions:

a[1] <= a[2] <= ... <= a[i-1]

To my eye it is obvious and I can't prove it. What is your opinion ?


texts: How interpret the notation $f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\}$, $N$ is a number of the form $2^n$?

texts:
I need help how to interpret the following notation for $f$:

  Zeroes and ones form a binary number which can be converted to
  decimal notation. Thus, we may think of the computer as calculating a function
  $$
f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\},
$$
  where $N$ is a number of the form $2^n$, and $n$ is the number of bits in the computer memory. In this description, $f$ must be a function because the computer cannot generate two or more different outputs from the same input. We assume without loss of generality that the domain and codomain of $f$ are of the same size. In other words, we assume that both the input and the output of the computer have the same number of bits.

Update:

I understand the function notation
\begin{align}
f&:\mathbb R \rightarrow \mathbb R_+ \\
x& \mapsto f(x)
\end{align}
so if $x\in \mathbb R$ we have $f(x)\in\mathbb R_+$.
So far so good.

However I don't follow the meaning (mapping) of $\{0, \dots, N-1\}$ in this case.

Attempt 1:

Say I have the decimal number $5$, so $N= 5$. I guess "of the form $2^n$" means a binary number, i.e. $5_{10}=(0101)_2$ and thus $n=4$. So I have the function
$$
f: \{0, 1, 2, 3, 4\} \rightarrow \{0, 1, 2, 3, 4\}
$$

Is this correct?

Attempt 2:

Is the domain and codomain of $f$ a binary number?  I.e. no commas in the sets
$$
f: \{0101\} \rightarrow \{0101\}
$$

Thanks in advance!


texts: Is the set-partition problem polynomial time reducible to the subset-sum problem?

texts:
There are many solutions on the web showing that the subset-sum problem is polynomial time reducible to the set-partition problem. However, during my search, I came across the following powerpoint presentation (slide 12), where it says that the inverse is also true. i.e. the set-partition problem is polynomial time reducible to the subset-sum problem.
So far, I have been unable to find any proofs to show the same.

So, my question: How is the set-partition problem polynomial time reducible to the subset-sum problem, or was there an error on the presentation above?


texts: How to deal with cost variation in a dynamic graph when applying Dijkstra

texts: What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I selected (I made the selection using an estimate). How do I deal with this variation?


texts: How are Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets related?

texts:
I am having an AI exam in two weeks, and I am still figuring out certain concepts and ideas, related to Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets (yes it is all going to be tested and yes we have a text (AI - A Modern Approach), but no, we did not cover everything in class).

I "know" a few things about the mathematical descriptions of all of those, but I know pretty much nothing about their usage or practical applications.

Here are my questions (and I apologize for my naivety):

What kind of machine learning algorithm classes do they belong to? Since they all need training, does it mean that they are all supervised learning algorithms?
They all have an underlying structure that allows a graph to represent them, where directed edges denote dependencies between states. The probability of being in a state is computed as a conditional probability from ancestors of the state. Does that sound about right?
In what kind of situation do you want to use which of the algorithms? Is it possible to some it up, or does it require subtle differentiation and expert-level knowledge?
Why do Neural Nets get special treatment? I heard of many classes teaching Neural Nets, but I have heard of no such thing for the other guys.


texts:
Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree?

What if the tree is infinite? What would then be a better way to prove that a given CFG generates a given language?


texts: What's the difference between a "dead" and "empty" state?

texts: In computational theory, I came across both deterministic and non-deterministic finite state machines but I heard someone said there are no dead states in deterministic machines. I thought dead and empty states were the same. What I noticed is that empty states are represented by a special symbol called an empty set ∅. What's exactly the difference?


texts: Constrainted Optimization Problem in Matrix Entropy

texts:
I have a constrainted optimization problem in the (Shannon) matrix entropy $\mathtt{(sum(entr(eig(A))))}$. The matrix $A$ can be written as the sum of rank 1 matrices of the form $[v_i\,v_i^T]$ where $v_i$ is a given normalized vector. The coefficients of the rank one matrices are the unknowns in which we optimize and they have to be larger than zero and sum up to 1.

In a CVX-like syntax the problem goes as follows:
given variable $\mathtt{c(n)}$

$$\text{minimize} \qquad \mathtt{sum(entr(eig(A)))}$$

$$\begin{align} \text{subject to} \qquad A &= \sum c_i v_i v_i^T\\
\sum c_i &= 1\\ c_i &\ge 0\end{align}$$.

Does any have an idea how to solve this efficiently? I already know it probably can't be cast as a semi-definite programming (SDP) problem.


texts:
My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." (For some reason, my table is not formatting here.)

What's the runtime of this code?

int f(int n) {
  if (n <= 1) {
    return 1;
  }
  return f(n -1) + f(n -1);
}

The tree will have depth N. Each node (i.e., function call) has two children. Therefore, each level will have twice as many calls as the one above it. The number of nodes on each level is:

Level
#Nodes
Also expressed as…
Or…

0
1

20

1
2
2 * previous level = 2
2^1

2
4
2 * previous level = 2 * 2^1 = 2^2
2^2

3
8
2 * previous level = 2 * 2^2 = 2^3
2^3

4
16
2 * previous level = 2 * 2^3 = 2^4
2^4

Therefore, there are 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^N (which is 2^n+1 - 1) nodes. (see "Sum of powers of 2 on page 630.)

Try to remember this pattern. When you have a recursive function that makes multiple calls, the runtime will often (but not always) look like O(branches^depth), where branches is the number of times each recursive call branches. In this case 2, so O(2^n).

As you may recall, the base of a log doesn't matter for big O since logs of different bases are only different by a constant factor. Howerver, this does not apply to exponents. The base of an exponent does matter. Compare 2^n and 8^n. If you expant 8^n, you get (2^3)^n, which equals 2^3n, which equals 2^3n * 2^n. As you can see, 8^n and 2^n are different by a factor of 2^2n. That is very much not a constant factor.

I do not understand the last paragraph. What base of a log? What is that and why do they say this here? What do they mean?


texts:
I am currently learning about caches in Systems class, and I had a few doubts about what exactly happens when a Computer reads a PDF. This is the sequence that happens in my mind:

The CPU checks if the pages of the PDF I want to read are there in cache.
It is not, so we keep going down the Cache hierarchy until we get to the Hard Drive, from where the PDF is located and read into main memory.
From main memory, it goes all the way back to L1 cache, and the CPU reads it.

Is there anything wrong with the simplification I have given above?

I know that Cache entries use the effective memory address of its data to determine where the data will be placed in the structure.  Here, in this example, what exactly will be the memory address of the PDF?


texts: After third form normalization, extra tables shall be created. And the functional determinant are used as primary key in the new table, as foreign key in the modified old table. My question is that following this strategy, the referential integrity enforces that when attributes have to be added to the new table before attributes can be added to the "old" table. one can't add attributes to the "Old" table first. However, in my application, it is more intuitive to add attributes in the old table first. It appears to me the normalization rule is not very applicable in such situation.


texts: Is the "data path cycle" the same thing of the "fetch-decode-execute cycle"?

texts:
I am reading the book Structured Computer Organization (5th edition) by Tanenbaum and at a certain point, in the second chapter, he talks about data path cycle and fetch-decode-execute cycle, and I am not understanding if they are really the same thing.

The data path cycle should be the number of small and minimal steps that a CPU goes through each cycle. On the other hand, the fetch-decode-execute cycle is the number of small steps that could be generalised like this:

Fetch the instruction from the memory and put it into a register
Change programming counter to point to the next instruction
Determine the type of the instruction fetched
If the instruction uses a word, determine where it is
Fetch the word, if needed, into a CPU register
Execute instruction
Go to step 1.

The fetch-decode-execute cycle is common to all computers, so each data path cycle should be a fetch-decode-execute cycle, right?


texts: Is the class NP closed under complement?

texts: Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.


texts: Prove grade-school multiplication algorithm applied to binary numbers

texts:
I want to prove that the basic multiplication algorithm is correct when applied to binary numbers.
I try to follow the steps described here and here but didn't succeed.

The basic implementation algorithm is the multiply function defined below, the other functions are given by completeness (this is F# but it reads as pseudo code):

let toBitsArray (x : int) =
    let bitArray = System.Collections.BitArray(System.BitConverter.GetBytes(x))
    let bits = Array.zeroCreate<bool> bitArray.Count
    bitArray.CopyTo(bits, 0)
    bits

(* Gives an array of bits (bool: 1 or 0) in little endian representation
   for example 5 = 00000000000000000000000000000101 (32 bits)
   the function will give this array:
   [|true; false; true; false; false; false; false; false; false; false;
     false; false; false; false; false; false; false; false; false;
     false; false; false; false; false; false; false; false; false;
     false; false; false; false|]
   which represents 10100000000000000000000000000000 (32 bits) *)
let toLittleEndianBitsArray (x : int) =
    let bits = toBitsArray x
    if System.BitConverter.IsLittleEndian
    then bits
    else Array.rev bits

let multiply (x : int) (y : int) =
    let by = toLittleEndianBitsArray y
    let rec loop (x : int64) (y : bool list) =
        if List.isEmpty y
        then 0L
        else
            let h = List.head y
            let t = List.tail y
            if h
            then x + (loop (x <<< 1) t)
            else loop (x <<< 1) t

    loop (int64 x) (List.ofArray by)


texts: Fastest way to determine constrained sum of an array

texts:
I have two $N$-vectors of positive integers, called cost and gain, and I have another integer called budget. You can think of every pairwise correspondence between cost and gain as a stock, and every possible subset of stocks as a portfolio.
I need to determine the portfolio (subset of pairwise correspondences) whose sum of gains is maximised, given that the corresponding sum of costs is smaller than budget. Every stock can appear only once in the portfolio.
Example:
budget = 5, cost = [1,2,17,4], gain = [5,9,100,2]

The third element must be discarded because it doesn't fit in the budget, while the best subset is given by first plus second, because the cumulative gain would be 14 for an expense of 3, while the other subset first plus fourth would respect the budget but gain less.
I approached the problem thinking to extract all the subsets contained in the power set of integers from 1 to N with at least one element, that is, all the ordered sequences of indices from 1 to N with length varying from 1 to N. This would correspond to all the possible portfolios, let's say. However, it turned to be too slow, because of nested loops.
I feel like this must be some classical problem in Algorithms, but I never studied this subject and I have just the sensation that there must be some kind of Dynamical Programming like solution. What is the fastest solution to this problem?


texts:
$$ L=\{<M>|M\ is\ a\ TM\ ;\ ∃x,|x|<5 ;\ M\ rejects\ x\} $$

How can i prove that $L \notin R$?
I can't see how Rice's theorem be used here since the conditions are not met (The constrain $M\ rejects\ x$ is about the machine architecture and cannot be expreseed by a non-trivial language)


texts: complexity of a Constraint Satisfaction Promise Problem

texts:
Due to curiosity regarding possible extensions of Schaefer's dichotomy theorem,
I wound up considering the "promise constraint" with 3 boolean inputs that's given by

$C(x,y,z)   = \hspace{.1 in}\begin{cases} \hspace{.19 in}\text{ True} & \text{ if exactly one of } \hspace{.02 in}x,\hspace{-0.03 in}y,\hspace{-0.03 in}z\hspace{.02 in} \text{ is true} \\ \hspace{.19 in}\text{ False} & \text{ if } \hspace{.07 in}x=y=z \\ \text{promise fails} & \text{ otherwise.}\end{cases}$

What is the complexity of the following promise problem?

Input:  a 3-CNF formula with no negations

must output YES if:  the input has a 1-in-3 satisfying assignment

must output  NO if:  the input has no NAE satisfying assignment

In the following, define $m$ to be the number of
promise-constraints in the 3-CNF formula provided as input.

I have neither managed to show that that problem is in
promisecoQMATIME$\hspace{-0.02 in}\big(\hspace{-0.04 in}$2o(m)$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}$q2o(m)  for infinitely many $m$,
nor show that there does not exist a positive integer $k$ such that for every must-output-NO instance U of that problem, some $k$-constraint sub-instance of U is not 1-in-3 satisfiable.

(If there does exist such a k, then the promise problem is solvable in coNLOGTIME.)

$m = 10$  is enough to refute  $k < 7$,  but I haven't yet found any refutation for $k = 7$.
The rest of that sentence will apply even when each variable occurs exactly twice,
if "infinitely many $m$" is replaced with "infinitely many even $m$" (since 3 is odd).

Motivation:
I was looking for non-trivial promise-constraints, to try to get an idea of whether or not Schaefer's theorem should extend to them.  To try to find one, I restricted attention to 3-variable boolean promise-constraints which only depend on how many of their inputs are true.  To be non-trivial, such constraints must be false when all of their inputs are equal, and must also have a way to
be true.  Furthermore, to avoid being resolved by Schaefer, they must have non-trivial promise.
The previous two sentences only leave 2 possibilities: the one I'm asking about, and the one which is instead true if and only if exactly two of the inputs are true.  However, the latter is equivalent
to what I'm asking about, since it just reverses the roles of [$\hspace{.02 in}$True,False] values for the variables.

What I've Tried:
I do realize that it would be enough to be able to find a NAE-satisfying assignment when
given a 1-in-3-satisfiable monotone 3-SAT formula, but my only idea for perhaps finding
such assignments faster than brute force is looking for autarkies (bottom of page 15).
(Additionally, I don't see any search-to-decision reduction for the promise problem,
since the oracle could output YES to lead the solver to instances which fail the promise,
and then output NO regardless of how the solver tries to simplify from there.)
I have also tried to find a small gadget.  It is possible that some more complicated representation would help, but so I could run a search for such things, I only looked for 3-input-variable
gadgets in which each each input variable is represented by only one output variable.
My Python program's brute-force search for such gadgets with [at most 3 constraints]
or [4 constraints and at most 3 non-input variables] did not find anything at all useful.


texts: Is my algorithm a $O(nm \lg m)$ solution for sorting a row and columnwise sorted $2D$ array?

texts:
The problem (from MIT 6.006 course) is the following:

  In this problem, you are given a $2D$ array of integers $A$ that has $n$ rows and $m$ columns. (Assume $m$ is much (e.g., exponentially) smaller than $n$.) Array $A$ has one special property: the integers in every row of $A$ and every column of $A$ are non-decreasing. More formally, $A[i, j] ≤ A[i, j + 1]$ for every $i = 1, 2, \ldots , n$ and $j = 1, 2, \ldots , m−1$, and $A[i, j] \leq A[i+1, j]$ for every $i = 1, 2, \ldots , n−1$ and $j = 1,2, \ldots ,m$.

  Describe and analyze an algorithm with running time $O(nm \lg m)$ that produces a sorted $1$~$D$ array of length nm that has exactly the same elements as $A$. For example, for the $2D$ array given above, the algorithm should return $[1, 2, 3, 4, 4, 5, 5, 6, 8, 10, 19, 30]$.

The solution to this problem is to use the merge routine from merge-sort, along with a min-heap or an AVL tree.

This works by maintaining m pointers, one for each column of the $2D$ input array.
The pointers start at the top of each column and we put each value of where the pointers point to into a min-heap (thus, the min-heap will at any given time contain at most m elements). We then use the merge routine from merge-sort to combine all the columns into a $1D$ array. The min-heap tells the merge routine which item to put next into the resulting array. When extracting an element from the heap, the pointer of the column of that element is advanced one element "down" and the corresponding value is inserted into the min-heap. This process is being performed until all the elements are processed.

I came up with a slightly different solution and was wondering if the time complexity still turns out to be $O(nm \lg m)$.

My solution works as follows (essentially a modified version of merge-sort):

Start with the entire array
Split the array in $2$ halfes by performing a column split (each of size $n \times m/2$)
Recursively split the subproblems into halfes until we reach the base case
Base case: the problem has size $n \times 1$ (a single column of the input array) and we simply return it (a $1D$ array that is already sorted)
For every other step than the base case, merge the two $1D$ arrays into a $1D$ array that contains all the elements of the two columns but now sorted

Concerning the time complexity, my thoughts are:

We split each subproblem into half the number of columns, thus resulting into $O(\log n)$ splits.
At each level of the recursion we perform $O(nm)$ work (for merging).

Combining the two parts, this gives: $O(nm \lg m)$. Is this correct or am I missing something here?

My attempt:

$T(m,n) = 2T(\frac{m}{2}, n) + O(nm)$.
If I guess $O(nm \lg m)$ as a solution to this recurrence $\forall k$, $k < m$, this is what I get by induction:

\begin{align}
T(m, n) &= 2T(\frac{m}{2}, n) + O(nm) \\
&= 2T(\frac{m}{2}, n) + c \cdot nm \\
&= 2(c \cdot n\frac{m}{2} \lg\frac{m}{2}) + c \cdot nm \\
&= c \cdot nm (\lg m - \lg 2) + c \cdot nm \\
&= c \cdot nm \lg m - c \cdot nm + c \cdot nm \\
&= c \cdot nm \lg m
\end{align}

As far as I can see, this is the desired complexity but I still feel like I am missing something here.


texts: TSP decision problem vs TSP optimization problem

texts:
Let's check together whether the TSP-decision problem is NP-complete. Maybe it will help me to understand things better.

Question for TSP-decision problem: Given n cities and a tour from length $k$. The traveller starts at an arbitrary city, visits every other city just once and returns to the starting point. Does a tour from length $\leq{} k$ exist?

Let's first check whether the TSP is in NP:

A proof is given. Proof in this case is a tour. For it to be in NP, we must be able to verify this proof with a deterministic algorithm in polynomial time.
So first we have to check, whether every city is only visited once. This can be done at most in $O(n^2)$. Next we need to calculate the distances and sum them up. This can be done as well at most in $O(n^2)$. The last step is to check whether the calculated length is $\leq{} k$. The hole process would require a polynomial time $\rightarrow 2 n^2 = O(n^2)$.

So the TSP-decision problem is in NP. What about the NP-hardness? We don't need to prove that, because Richard M. Karp proved that the Hamiltonian Circuit is NP-complete. The TSP is a special case of the Hamiltonian Circuit, therefore we know TSP must be NP-complete as well. NP-complete means = NP-hard and NP.

Is this possible with TSP-optimization problem?

Question for TSP-optimization: Given n cities and a tour from length $k$. A traveller starts at an arbitrary city and visits every other city just once and returns to the starting point. Is tour from length k the shortest tour?
We can check in polynomial time, that every city is visited once.
However we can't check whether $k$ is really the shortest tour, because we would have to check every other possible tour as well. That would mean $(n-1)!$ possible tours. And this would make the hole process above exponential.

So TSP-optimization problem is not in NP? Therefore it is not NP-complete, but NP-hard?

Anything wrong about my thoughts?


texts: Algorithm for a list of best solutions to the Assignment problem

texts:
I am trying to brute force a classical substitution cipher. The problem is that there are $26!$ possible keys. So, I'd like to do frequency analysis to try likely keys first. Then, on the first $n$ tries I will use a dictionary to see if there are actual words in the decryption. That way, I don't need to try all possible keys.

So, as suggested here, I will use chi-squared testing. I was thinking of making a matrix, best illustrated with an example. Suppose in an alphabet {A,B,C} the letter frequencies are 50%, 30% and 20% respectively, and that in a ciphertext the frequencies are 10%, 50% and 40% respectively. Then the A-B cell in the matrix is $(0.1-0.3)^2=0.04$, which is the error rate when a B in plain is encrypted as an A.

   |  A   |  B   |  C                 | Use in plaintext | in ciphertext
---+------+------+------           ---+------------------+---------------
 A | 0.16 | 0.04 | 0.01             A |        0.5       |       0.1
 B | 0.00 | 0.04 | 0.09             B |        0.3       |       0.5
 C | 0.01 | 0.01 | 0.04             C |        0.2       |       0.4

The Hungarian algorithm then gives me a frequency-analysis-wise optimal key: $A \mapsto C, B \mapsto A, C \mapsto B$. This is because the sum of the errors (0.01+0.00+0.01=0.02) is minimal. This is useful, but what I need is the $n$ best keys.

The only thing I can come up with is to run the Hungarian algorithm, and then set one of the cells in the matrix above corresponding to the key found to a high value, so that if you run the algorithm again the  key you find doesn't contain the mapping. So, in the example above, you could set A-C to 1 so that when you run the Hungarian algorithm again you find a different key that doesn't contain $A\mapsto C$.

However, this isn't guaranteed to find good keys in order. What would be a better way to extend the Hungarian algorithm to find the best $n$ keys?

Epilogue: after implementing this using D.W.'s approach below, it turned out that this method doesn't perform well enough to crack small-length (at least up to 1000 letters) cipher texts, because frequency analysis alone isn't enough. Performance may be improved by taking frequent digrams or trigrams into account, but I doubt this method can be as powerful as simple hill climbing.


texts: Algorithm. Input: pointers to k unsorted arrays of different lengths. Needed output: k sorted arrays

texts:
$k = \Theta(n)$

The arrays consist only natural numbers $1$ to $n$

The sum of the length of all arrays = $\Theta(n)$

It should return the $k$ original arrays, each sorted on its own.

The running time should be at worst $\Theta(n)$.
How is it even possible? There's something I must be missing because I have no idea how to approach this.
The data I gave you is all the given data. Any ideas?

Using counting sort on each array won't work, for it will be $\Theta(n^2)$, but maybe a different approach using this method?


texts:
Why is the complexity class IP important?
What additional insights does this class give us that we could not get from NP or RP?


texts: How to "properly" handle incorrect values in a random walk?

texts: I'm performing a simple one dimensional walk to create sample interest rates. Whilst I know there are lots of options for encouraging values to oscillate around a mean etc. I'm yet to find a simple "proper" way to handle truly random processes going out of bounds. Whilst you could simply turn it in the other direction, is there some sort of commonly accepted way of making asymptotically less and less likely to get closer to the boundary the closer you get to it?


texts: Why Is My Proof Of Asymptomatic Time Complexity Of A Dynamic Array Using The Accounting Method Getting A Wrong Answer?

texts:
I had trouble formatting the summation symbols, so if anyone knows how to do it correctly feel free to edit.

I just read the asymptomatic analysis chapter from CLRS. While the aggregation and potential method are clear to me, I thought I should do some extra practice with the accounting method. My goal was to prove that if you have an array size 1, and when it fills up, you double the size, results in a time complexity of O(1) per operation. Using aggregate analysis, here is the proof I came up with:

If you call append n times, then the time complexity would be this:

$\sum_{i=1}^{\log n} \frac{1}{2^i}$

which is less than

$\sum_{i=1}^{+\infty} \frac{1}{2^i}$

which is equal to $2n$. So, the time complexity for all N operations will be O(N), so the time complexity for a single operation is O(1).

However, if the size starts at 1, then adds by 1 instead of multiplying by 2 (meaning, size starts 1, then becomes 2, then becomes 3, etc...) then the time complexity should be O(N), which I get using aggregate analysis.
$\sum_{i=1}^{n} (i+1)$

the extra 1 comes from actually placing the next element. This is equal to around (n(n + 2)) / 2, or O(N ^ 2) for all N operations, and O(N) for a single operation, which is correct. However, using the accounting method I get another answer. The actual cost of placing an element is 1, and the asymptomatic cost I set is 2. So the first time costs 2, and the second call the copying doesn't take any extra time because I prepaid it before, and the extra cost of placing that element is 2. So, it becomes:

$\sum_{i=1}^{n} 2$

which is equal to O(N) for all total operations, and O(1) for a single operation. This isn't the correct output. Where did I go wrong, and how can I fix it?


texts: Algorithm and proof for combining a list of node connections into groups of nodes efficiently

texts:
My goal is to algorithmically take a list of relations between nodes (in other words, a list of undirected edges between nodes of a graph) and label each group of nodes such that all nodes that have a path between them have the same label (I believe the term for this is a "connected component") and nodes that do not have a path between them have different labels. Put another way, each connected component has a unique label.

NOTE: I haven't done all that much in the way of discrete math proofs since college, so hopefully you can bear with me and correct my terminology/methods if necessary.

To clarify, the data is in the form of a list of pairs of connected nodes.

For example:

n_1, n_3
n_3, n_5
n_5, n_7
n_5, n_9
n_2, n_4
n_4, n_6

In this <contrived> example, the odd-numbered nodes all belong to the same group, and the even-numbered nodes belong to another group.

I believe the way to do this is to process each item in the list according to the following rules:

Maintain an ordered list (call it "encounteredNodes") of all encountered nodes and the group label they have been assigned to
Maintain an integer variable (call it "nextLabel") that is incremented and returned each time a new unique label is needed
For each item in the list, determine if either node has been encountered yet.

If neither node has been encountered, get a new unique label from nextLabel and add both the nodes to encounteredNodes with this new uniqueLabel
If one node has been encountered but not the other, assign the label of the previously-encountered node to that of the unencountered node.
If both nodes have been previously encountered, take the lesser label of the two and use it to replace the label of all nodes in encounteredLabels that have the greater label of the two.

After one pass of this "for loop" through all the nodes, the algorithm is complete and the nodes have been grouped according to the goal. I believe the proof can be shown in this way:

Lemma 1: None of the operations can result in 2 previously encountered nodes that already have the same label being assigned to different labels. Because of this, already encountered nodes never "split off" from their group of nodes with the same labels, and once two nodes have the same label, they will never have differing labels (though they may change together to the same new label) for the remainder of the algorithm.

Assume there are two nodes that have a path between them via the list of edges, yet after the algorithm finishes, they have different labels (call them $L_1$ and $L_2$. If that's the case, then either...

They each contain a node (and these two nodes are directly connected), or...
there is a "chain" formed of groups of nodes where each group has the same label and the chain can be traversed to get from $L_1$ to $L_2$.

However neither of these scenarios can occur based on the algorithm. In the case of 1, there would have to have been a pair of connected nodes in the list where one node belongs to $L_1$ and one node belongs to $L_2$. However, after the algorithm processed this connection, both nodes would have the same label, and because of Lemma 1, they would have the same label until the end of the algorithm. In the case of 2, the neighbouring links in the chain could not exist because of the first case. Thus. This is a proof by contradiction.

Is this all sound? Also, I was never that great at algorithm runtime calculations, but I think it would be $O(n \log{n})$ because iterating the list of connections is linear time, but each iteration requires a search of ordered lists. Is this correct?


texts: Is there a way to show $\{a^nb^nc^n:n\geq0\}$ is not regular without pumping lemma?


texts: Algorithm for finding all the heaviest edges in a graph

texts:
We have a non directed, not necessarily connected graph $G=(V,E)$, that is represented by a adjacency list, and a weight function $w:E \to R$. All edges have distinct weight. An edge is "heavy" if there exists a simple cycle in $G$ that contains it, and it has the maximal weight in that cycle. The question is to give an algorithm which finds all of the heaviest edges in $G$.

My proposed algorithm:

Create an array $A$ of size $|V|$ where every cell represents a node $v_i$ in G. Mark all nodes as 'unexplored'.
Select the node $v_1$ in $G$ and run Prim's MST algorithm from it. Modify Prim's algorithm so that when a node is reached by the MST tree it is marked as 'explored' in $A$.
Scan the array $A$ linearly from the last node encountered as 'unexplored'. Each time a node marked 'unexplored' is found, do step 2 for it.
When $A$ is traversed completely, mark the group of all the edges in all the MSTs found as $E'$.
Return $E/E'$ — this is the group of heaviest edges.

The algorithm's correctness follows from the cycle property for MSTs, and that every edge has a distinct weight.

This algorithm is as efficient as running Prim's MST algorithm on a connected non directed graph — that is $O(E + V \lg V)$ with Fibonnaci heaps.

My questions is, is this is the optimal running time for this problem? I have a feeling this can somehow be done in linear time using DFS.


texts:
I am trying to find the maximum palindrome sub-sequence and after going through some tutorials, I came up with a memoized version.But I am not sure about the runtime.I want to know if the following algorithm will work.Could also someone explain what the runtime will be?

Memoized-Palindrome(A,n)
initialize longest [i][j] =0 for all i and j
then return Memoized-Palindrome1(A,1,n,longest)

Memoized-Palindrome1(A,i,j,longest)
if longest[i][j]>0 return longest [i][j]
if (j-i) <=1 return j-i
if A[i]==A[j]
      then longest[i][j] = 2 + Memoized-Palindrome1(A,i+1,j-1,longest)
    else
      longest[i][j]= max(Memoized-Palindrome1(A,i+1,j,longest),Memoized-Palindrome1(A,i,j+1,longest)
return longest[i][j]


texts: Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? How?

texts: Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? If so then how?


texts: Bankers Algorithm-Is the system in safe state?

texts:
Could somebody please provide a step-through approach to solving the following problem using the Banker's Algorithm?

A system contains 10 units of resource class Ru. The resource requirements of three user processes P1, P2 and P3 are as follows

                      |   P1  |  P2  |   P3   |
Max Requirement       |   8   |  7   |   5    |
Current Allocation    |   3   |  1   |   3    |
Balance Requirement   |   5   |  6   |   2    |
New Request Made      |   1   |  0   |   0    |

Using Banker’s algorithm, determine if the projected allocation state is safe and whether the request of P1 will be granted or not.

My solution:

total recources :10
total allocation :7
available: 10 -7 = 3

Need
P1     5
P2     6
P3     2

3>2 so P3 can run now available is 6
6>5 so P1 can run now availabl 9
9>6 so P2 can run

System is safe state,Hence P1 will be granted.

But I'm not sure if my solution is true.


texts: Universal Turing Machine simulation with bounded time overhead

texts:
Is it possible to design a Universal Turing Machine in which the simulation time of a given Turing Machine $M$ is bounded by a factor of $\mathcal{O}(\log|\Gamma|+\log|Q|)$ of the original running-time of $M$, where $\Gamma$ and $Q$ are the tape alphabet and states of $M$ respectively?

If so, how can this be done?


texts: Lambda calculus :Will there be any x left after first substitution?

texts:
I found the following set of lemma in my lambda calculus textbook :

  Lemma 1.16 Let $x, y, v$ be distinct (the usual notation convention), and let no variable bound in $M$ be free in $vPQ$. Then

  (a) $[P/v][v/x]M \equiv [P/x]M$ if $v \notin \mathrm{FV}(M)$;

  (b) $[x/v][v/x]M \equiv M$ if $v \notin \mathrm{FV}(M)$;

  (c) $[P/x][Q/y]M \equiv [([P/x]Q)/y][P/x]M$ if $y \notin \mathrm{FV}(P)$;

  (d) $[P/x][Q/y]M \equiv [Q/y][P/x]M$ if $y \notin \mathrm{FV}(P), x \notin \mathrm{FV}(Q)$;

  (e) $[P/x][Q/x]M \equiv [([P/x]Q)/x]M$.

I am stuck at (e) .I wonder if there is any order to be followed while evaluating this kind of expressions or there isn't any .What I think is that in $[P/x][Q/x]M $ we would replace all the $ x $ in $ M $ by $ Q $ and as such we wouldn't be having any more $ x $ to be replaced by $ P $ . Then there is no point in the the exterior substitution expression ,i.e. $ [P/x] $ . How to explain this ?


texts: If $L = \{ a^{2^n} \mid n \ge 0 \} $ is not regular, then why there is a DFA thats accepts its language?

texts: Let $L = \{ a^{2^n} \mid n \ge 0 \}$, which is a non-regular language (no proof here). Let $M = (\Sigma,Q,\delta,z_0,F)$ be a DFA with $\Sigma = \{a\}$, $Q = \{z_0\}$, $\delta(z_0, a) = z_0$ and $F = \{z_0\}$. Then the DFA should accept $L$ and $L$ is therefore regular. Why is my approach wrong?


texts: Concept of M-augmenting path to find a larger matching than $M$

texts:
I'm reading section 16.1 of the book, Combinatorial optimization, Polyhedra and efficiency by Schrijver. Here, he starts with a matching $M$ and describes a path $P$ that is $M$-augmenting if:

The path has odd length (in terms of edges).
Its ends are not covered by $M$.
Its edges are alternately out of and in $M$.

Theorem 16.1 then states that we either have a matching of maximal size or an augmenting path exists.
I don't understand this statement. See the graph below for example. For now, we have the edge between vertices 2 and 5 in a matching $M$. I can't find any path that satisfies the three conditions above. Yet, this is obviously not a maximal matching since the edge between vertices 1 and 4 can be added to increase its size. What am I missing and why is my understanding so way off?
Further, if I'd used 1-4 as my initial matching, it would have been impossible to find a path that satisfies condition 2.

Conversely, I take the graph the the author himself provides as an example of an augmenting path. In the simple linear graph below (which is also a linked list), an augmenting path satisfying the three conditions above exists. However, where is the edge that can be added to this graph to increase the size of $M$?


texts: A question about proving Rice's Theorem by reducing it to the Halting Problem

texts:
I've read the definition for Rice's Theorem, here's the one from Wikipedia:

  In computability theory, Rice's theorem states that all non-trivial,
  semantic properties of programs are undecidable.

The classical proof for proving Rice's Theorem is on Wikipedia, which is similar to other sources.

However, I have a problem with this proof, made clear (hopefully) in the paragraphs following.

This proof goes like this:

  if we had an oracle for deciding these properties of program behavior, we would be able to use it to solve the Halting Problem, but the Halting Problem is undecidable, so an oracle for deciding these properties cannot exist either.

However, as far as I know, the impossibility of the Halting Program only occurs if the program checking whether something halts or not is trying to prove the hypothetical does_it_halt(a, i) wrong by using self-referencing tricks. But, in this proof, the oracle that is trying to decide the property is not trying to do that. So, it should be able to do its job without solving the Halting Problem.

I had some hope at the beginning that this proof may be wrong, but since it is apparently the "classical" proof for proving Rice's Theorem, I must be missing something. What is it that I am missing ?


texts: Missing assumptions in selection algorithm proof of correctness by contradiction?

texts:
Yes, this is homework.
I need help knowing how to begin this problem:

  Let A be an algorithm that finds the kth largest of n elements by a
  sequence of comparisons. Prove by contradiction that A collects enough
  information to determine which elements are greater than the kth
  largest and which elements are less than it. In other words, you can
  partition the set around the kth largest element without making more
  comparisons.

I'm not looking for an answer. I am confused about how to even begin this question, it's the last one on my homework and tried searching quite a bit for similar situations. My fellow students seem confused as well. I also asked the professor but he lived up to his reputation for being quite cryptic.
I actually found someone else's answer online searching, which I will provide here:

  Call the majority element x and say it appears i > b n/2 c times.
  Each time x is encountered, it is either pushed on the stack or an
  element (different from x) is popped off the stack. There are n − i <
  I elements different from x. Assume x is not on the stack at the end
  of the procedure. Then, each of the I elements of x must have either
  popped another element off the stack, or been popped off by another
  element. However, there are only n − i < I other elements, so this is
  a contradiction. Therefore, x must be on the stack at the end of the
  procedure

I don't remotely even know if that's correct, and I don't understand it.

How do I even approach this question? It seems like the initial question needs more information about the algorithm for me to be able to answer it. Or maybe there is an underlying implication to "sequence of comparisons" that I'm missing. I don't understand how to begin without a specific algorithm provided. None of his example problems he has done in class and none I've found in the book are like this. All the other problems have specific algorithms. I feel like maybe I am missing an important concept?


texts: How do I know which direction I should rotate a node in an AVL Tree?

texts:
I'm studying AVL Trees in my programming class and we got this exercise dealing with right, left, left-right and right-left rotations as a way to check if we understand the theoretical concept of AVL Trees. We're given the numbers $100,50,25,10,37,32,200$. Creating an AVL Tree until $37$ wasn't that difficult but then I got stuck at balancing out the tree when I insert $32$. The following is my method:

Now I know that there is a conflict at $52$ but since it has 3 nodes (LRL), I don't understand how I should rotate. I think, I should get $37$ as the root node $25$ as it's left child and $52$ as it's right child but I dunno.


texts: Counting sort on non-integers - why not possible?

texts:
What is it about the structure of counting sort that only makes it work on integers?

Surely strings can be counted?

''' allocate an array Count[0..k] ; initialize each array cell to zero ; THEN '''
for each input item x:
    Count[key(x)] = Count[key(x)] + 1
total = 0
for i = 0, 1, ... k:
    c = Count[i]
    Count[i] = total
    total = total + c

''' allocate an output array Output[0..n-1] ; THEN '''
for each input item x:
    store x in Output[Count[key(x)]]
    Count[key(x)] = Count[key(x)] + 1
return Output

Where above does the linear time break down if you try to use counting sort on strings instead (assuming you have strings of fixed length)?


texts: Are run time bounds in P decidable when the problem is promised that an input program must halt?

texts:
I'm solving Problem 11-10(b) in "what can be computed".

11.10 Consider the decision problem HALTSINSOMEPOLY (HISP), defined as
follows.
The input is a program P, and the solution is “yes” if and
only if there exists some polynomial q(n) such that, for every n, P
halts after at most q(n) steps on all inputs of length ≤ n.
(a) State, with proof, which of the following statements are true: (i) HISP is
undecidable, (ii) HISP ∈ Expo, (iii) HISP ∈ Poly.
(b) Would your answer to a change if we restrict the domain of HISP, so that the
input P is guaranteed to halt on all inputs? (Note: This is an example
of a promise problem, in which the input is promised to have a certain
property, which may itself be undecidable.)

The proof of 11-10(a) is basically same as "Are runtime bounds in P decidable?", which is that HISP reduces to halting problem.
If an input program is promised to halt, however, this reduction does not help us.
Is there any suggestion to solve this problem?


texts: Push Down Automatons "guess" - what does that mean?

texts:
I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted by a deterministic pushdown.

Still, I do not understand how exactly they "choose". For palindormes for example every source I found just says the automaton "guesses" the middle of the word. What does that mean?

I can think of several possible meanings:

It goes into one state randomly and therefore might not accept a
word, which actually is in the language
It somehow goes
"every possible way", so if the first one is wrong it tests if any
of the other might be right
There is some mechanism I am not
aware of, that chooses the middle of the word and is therefore not
random, but the automaton always finds the right middle.

This is just an example; what I want to know is how it works for any automaton that has several following states for one and the same state before it.


texts: How well is Moore's law (and it's cousins) holding up?

texts:
I came across a set of articles back from the 2000s that stated Intel was planning a 10Gz CPU by 2011. Obviously, this didn't pan out. But how well are Moore's law and it's cousins holding up in terms of:

Transistors per \$1000
Floating point operators per \$1000
The performance of the world's most powerful supercomputers?
The computing power available to the average consumer
Flops per watt of power

And which of these are likely to break down in the next few years?


texts: Deterministic context-free languages are closed under regular right-product

texts:
I am looking for a proof for the following problem:

  For languages $L$ and $R$, if $L$ is deterministic context-free
  and $R$ is regular, then $LR$ is a deterministic context-free
  language.

Note: $RL$ may not satisfy this condition, e.g. if $L=\{wcw^R\mid w\in (a|b)^*\}$, and $R=\{a\}^*$.


texts: Making a grammar ambiguous by applying a morphism

texts:
I have an encoding of an unambiguous grammar $G$. Can I apply a morphism $σ$ so that the grammar becomes ambiguous?

I have no clear concepts about this, only the idea: "grammar $G$ is ambiguous if there's a string $x \in L(G)$ having two different leftmost derivations in $G$". I would like a good explanation and if it's possible, an example.

Morphism:

I will consider two alphabets,  $Σ_1$ and $Σ_2$, where $\Sigma_1$ is the terminal alphabet of $G$.
A morphism is a function of the form $h\colon Σ_1^* \to Σ_2^*$
which satisfies: $h(xy)=h(x)h(y)$ for all $x,y \in \Sigma_1^*$.
When applying the morphism to a grammar on $\Sigma_1$, the result is a grammar on $\Sigma_2$ (that is, the morphism is only applied to the terminals in $G$).


texts: Why do min/max operations in van Emde Boas trees run in $\mathcal{O}(1)$?

texts:
I have read in the book

  "Introduction to Algorithms", 3ed by Cormen, Leiserson, Rivest, and
  Stein (Chapter 20)

that Emde Boas trees run min/max operations in $\mathcal{O}(1)$ time since the minimum and maximum element are stored as attributes in each tree. I don't understand this very well. Does this mean that the min and max values are already given in the input, because the minimum and maximum must be calculated somewhere?


texts: How to perform alphabetically ordered DFS?

texts:
I've been working on this graph and just completely botching it. I mean to say that my solution may be the worst possible other than if a monkey had thrown darts at the graph to decide the next path.  Anyhow, I'm lost and really trying to get a grasp of where my conclusion and the proper conclusion diverged dramatically.

I wanted to perform a DFS, show discovery/finish times, the DF forest, and edge classifications. I assumed that: 1) The vertices are listed in alphabetical order in each adjacency list. 2) The vertices are taken in the alphabetical order in the main loop of the DFS algorithm.

Should I be treating this as a directed acyclic graph?


texts: $f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive $\Leftrightarrow$ its graph is a recursively enumerable?

texts:
I have known that:

  A function $\Bbb N → \Bbb N$ is recursive if and only if its graph is a recursive subset of $\Bbb N^2$.

Now I am considering about the partial functions. Is it the fact that:

  A partial function $f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive if and only if its graph is a recursively enumerable subset of $\Bbb N^2$.

If it is true (or one direction is true), may I please ask for a proof? Or some reference would be also appreciate (I searched it but did not obtain any useful result).

Note: It is from a math course (and I have asked in the math site). And I have not learnt about the related things about computer science (for instance, I have not learnt about the Turing machine and I have no skill of coding). So sorry I cannot understand explanations which involves the usage of terms in computer science. May I please ask for a mathematical approch please?
Thanks!

I have done some search but I cannot find some helpful material. Any reference would be appreciate to. Thanks a lot.


texts: How to embed Pearson distance into Euclidean space

texts:
I have a lot of numerical vectors, each of dimension 1000. I would like to compare them according to their Pearson distance. This works fine but comparing all vectors to each other is quadratic time and too slow. Ideally I would like to be able to perform efficient approximate nearest neighbour searches instead.

If I could embed the vectors into Euclidean space then I could use standard tools to do this.

  Is there a way to embed vectors from a space using the Pearson distance into Euclidean space?


texts: Re-arrangement Algorithm Minimizing Total movement

texts:
I have $n$ items arranged on a straight line (like a number line, items can only move 2 directions).  The each item has a size, some distance around their center position, that can't overlap with other items.  They also cannot cross each other.
The problem:
We have a set $S$ of positions (of size $\leq n$).  We need to find a way to move the items, so that after the movement each position in $S$ has one item there.  (There might be other items at other positions as well.)  The goal is to minimize the total movement of all items.  Is there an efficient algorithm to find the way to move the objects that minimizes this?


texts: If I want a cuckoo filter to hold a dataset with N entries with a target false positive rate of ϵ, how do I select the sizes for the table, bucket, and fingerprint parameters?


texts:
I was fooling around with Google Blocky's Maze demo, and remembered the old rule that if you want to solve a maze, just keep your left hand to the wall. This works for any simple-connected maze and can be implemented by a finite transducer.

Let our robot be represented by a transducer with the following actions, and observables:

Actions: go forward ($\uparrow$), turn left ($\leftarrow$), turn right ($\rightarrow$)
Observables: wall ahead ($\bot$), no wall ahead ($\top$)

Then we can build the left-hand maze solver as (pardon my lazy drawing):

Where seeing an observable will make us follow the appropriate edge out of the state while executing the action associated with that edge. This automaton will solve all simply-connected mazes, although it might take its time following dead ends. We call another automaton $B$ better than $A$ if:

$B$ takes strictly more steps on only a finite number of mazes, and
$B$ takes strictly fewer steps (on average; for probabilistic variants) on an infinite number of mazes.

My two questions:

Is there a finite automaton better than the one drawn above? What if we allow probabilistic transducers?
Is there a finite automaton for solving mazes that are not necessarily simply-connected?


texts:
Here's the problem:

I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$.  Denote $c_i$ as the i-th $X$ in $c$.  Informally, I want to map all the sets in each collection to bins, where no two sets in a single collection can occupy the same bin, such that the sum of the sizes of the unions of all sets in each bin is minimized.  More formally:

Let $N = \max_{c \in C} |c|$, and let $P_N$ be the set of all permutations of all non-empty subsets of the set $\{1,2,...,N\}$.  I wish to define a mapping:

$$F : C \rightarrow P_{N},\ s.t.\ \forall c \in C\ (|F(c)| = |c|)$$

with bin sets
$$B(k) = \{X \subset U : \exists c \in C\ (\exists i \in \{1,2,...,|c|\}\ s.t.\ c_i = X \wedge (F(c))_i = k)\}$$

Such that the quantity

$$\sum_{k=1}^{N} { \Biggl|\bigcup_{X \in B(k)}\Biggr| } $$

is minimized.

Off the bat, I'd guess that this is an NP-hard problem - a reduction from Set Cover seems to be just within reach.

Even a greedy algorithm that iteratively processes each collection $c \in C$, producing minimal results each time, requires $O(2^N \cdot |C|)$ time using dynamic programming, where $|U|$ is assumed to be a constant factor.

I'm having trouble proving whether or not the Greedy algorithm is even optimal - or if a more efficient solution exists.  Anyone have any thoughts?

Alternatively, minimizing the quantity:

$$\max_{1 \leq k \leq N} {\Biggl| \bigcup_{X \in B(k)} \Biggr| }$$

Is also of interest.  It's definitely a different problem, as demonstrated by a simple case where $C$ has 2 collections, one of the form $\{\{1\}, \{3, 4\}\}$, and the other $\{\{2\}, \{3, 4\}\}$.  I am not sure this problem is any easier though


texts:
$\newcommand{\bs}{\mathrm{bs}}$What is the largest gap known between block sensitivity ($\bs(f)$) of a boolean function ($f$) and degree of a polynomial ($\deg(f)$) that represents/approximates it?

We know of lower bound $$\bs(f)\leq c\deg^2(f)$$ for some $c>0$. Is there a Boolean function that achieves this separation?


texts: Polynomial Complexity (Relative to the Size of the Input)

texts:
I came across the following statement:

"Since b is smaller than n, the complexity $O((n + mb)^3)$ is polynomial."

I suppose it has something to do with the notion of polynomiality in terms of the input. All three variables are given as input. I am still not sure why it wouldn't be polynomial if $b$ was as big as $n$.

We could say $O(n + mn)^3)$ then which would be dominated by $O((mn)^3)$ for $m \geq 0$.
It is even given, that $m \leq n$ which means that we can say $O(n^6)$ as worst case.

Now I would say this is certainly polynomial, because our solution is of the form $O(n^c)$ with $c \in \mathbb{R}$ which means that it is polynomial in the size of $n$.

What am I missing here?


texts: Doubt on declaring an array in pseudocode

texts:
So here's the code:-

DECLARE number as INTEGER

PRINT "Enter a number"

INPUT number

DECLARE randomarray [1:number] AS INTEGER

Is this possible? i.e whilst declaring arrays, can we use variables?

Note:The question is strictly limited to pseudocode or general programming language


texts: Solving a linear program with simplex algorithm, matrix not full rank

texts:
I need to solve the following LP

$$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & A x = b\end{array}$$

where

$$A = \begin{bmatrix} 1 & 3  &1&0&0 \\   -2&-2&0&1&0 \\ 2&4&0&0&1     \end{bmatrix}, \qquad b = \begin{bmatrix} 2 \\2\\ 4\end{bmatrix}, \qquad c = \begin{bmatrix} -1\\ -1\end{bmatrix}$$

Matrix $A$ is not full rank. Then the only way to solve that problem is to create an equivalent problem with a full rank matrix? Here for instance:

$$ \min \{ (c,-c) (x^+,x^-)^T : \begin{bmatrix}   A & -A \\   -I& 0 \\ 0& -I \end{bmatrix}   (x^+,x^-)^T \leq (b, 0,0)^T \} $$

but I don't know how to solve a problem with $x^+$ and $x^-$. Would you have an example ?

  So my question is how to solve such a problem, and if you'd recommand
  my method, how do you use it, especially concerning the $x^+$ part.


texts:
1   2   3   4   5
|---|---|---|-----|---|---|
|   | > | v |     |   | 5 |
| > | ^ | > | [>] | z | 4 |
| ^ |   |   |  ^  |   | 3 |
| ^ | > | > |  ^  |   | 2 |
| a | ^ |   |     |   | 1 |
|---|---|---|-----|---|---|

Let say we have a GRID like the one above.
I want to create score for paths, where every next step has a lower discounted value.
F.e. let start with score with range [1,0), step 1:start (1,1) is 0.9, step2:up (1,2) 0.81, step3:up (1,3) 0.73, ....
and store the update Score in every cell.
(Later I want to add +/- Rewards along the path)
The first problem is if the path is too many steps the latter steps will have very small values.
Second most important is if paths overlap, the next path will screw the score of the previous path.  F.e. cell(4,4)
One solution is for every path to have its own lookup table but this will take too much memory.
I want to reuse the grid for all the paths, something like Reinforcement Learning but in the opposite direction, from start to end.
Cant figure the exact formula, has to be something along the line :
V_0 = 1
V_t = decay(V_t-1,%)

sort of !! + reward somewhere
Whats your idea ?