texts: Sub-graph Selection Algorithm Problem (Dynamic Programming or NP)

texts:
We have an algorithm problem in hand, can you please write your ideas about this, thank you!
There are N many nodes with K different colors. Some of the nodes have direct connection between each other and some do not.
We want to select M nodes from these N total nodes, but these M nodes must be connected. Also, our selected group of M nodes must have minimum number of distinct colored neighbors. There might be more than one best combinations, finding any of them is the goal.
For example, we selected M nodes and in total, these M nodes have the following neighbors: 5 red, 3 blue, 1 green. In this case, we count the unique colors, so the number of distinct colored neighbors, in this case, is 3. We want to minimize this number by selecting the best possible combination of M nodes.
Example graph visualization :

In this example, let's assume M = 4, then the best possible combination of nodes would be {9, 10, 11, 12} since this group has only one neighbor which is yellow.
If we choose {0, 1, 3, 5}, the neighbors of this combination would be {2, 4, 6}, which consists of 2 red neighbors and 1 green neighbor; which results with score of 2 since we look for distinct number of colored neighbors.
Is this algorithm question NP-complete? How should we proceed? If this is not NP-complete, what is the best algorithm we can use to solve this problem?
Can we combine graph algorithms such as Prim’s, Kruskal's, Floyd Warshall or traversal algorithms?


texts: Generating topological sequence from DAG with additional "not appearing before" constraints

texts:
DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG?
Is there an algorithm for generating topological sequence from DAG with such constraint? Or maybe I can transform the DAG with this constraint?


texts: What is difference between architecture and microarchitecture?

texts: I am studying computer architecture.  I would like to know the difference between the terms "computer architecture" and "microarchitecture".


texts: Solving $T(n)=4T(n/2)-1$ without using the master theorem

texts:
How can I solve the following recurrence without using the master theorem?

$T(n)= 4T(n/2)-1$  for $n>4$ and $T(n)=5$  for $n\le 4$, $n$ is a power of $2$.


texts:
I'm facing the following problem:
Describe a distributed MST algorithm in time $O(n \log \log n)$

I've managed to think of the following,

Run GHS(Gallager, Humblet and Spira) algorithm, till there are $(n/(\log n))$ fragments.

This way I believe there's a small thing to do so the finding of roots to connect fragments, will take $\log \log n$.

Basically if there are $\log n$ fragments, searching for the root to connect to, is supposed to take $\log \log n$, because in usual case it takes $\log n$ for $n$ fragments. But I'm really not sure about this one


texts: Disjoint Set Connected Components With Weighted Graph

texts:
I have been trying to solve this HackerRank problem (link).

The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken to be the MAXIMUM cost of any edge in the path. I will be given a series of queries in the form of [L, R] and I have to output how many paths in that tree have a cost in the provided inclusive range.

This is the code I've written -

class DisjointSetRep():
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

class DisjointSetNode():
    def __init__(self, val):
        self.val = val
        self.next = None
        self.head = None

class DisjointSetLinkedList():
    def __init__(self):
        self.rep = DisjointSetRep()

    def add_node(self, node):
        if not self.rep.head:
            self.rep.head = node
        self.rep.count += 1
        self.rep.tail = node
        node.head = self.rep

def make_set(v):
    new_linked_list = DisjointSetLinkedList()
    new_head_obj = DisjointSetNode(v)
    new_linked_list.add_node(new_head_obj)
    return new_linked_list, new_head_obj

def find_set(v, node_map):
    return node_map[v].head

def union(u, v, node_map, sets_map):
    u_node, v_node = node_map[u], node_map[v]

    if u_node.head.count > v_node.head.count:
        small_rep = v_node.head
        large_rep = u_node.head
    else:
        small_rep = u_node.head
        large_rep = v_node.head

    # update all nodes to point to new rep
    temp = small_rep.head
    while temp:
        temp.head = large_rep
        temp = temp.next
    # update last node in first list to point to head of second list
    large_rep.tail.next = small_rep.head
    # update new tail
    large_rep.tail = small_rep.tail
    # update count
    large_rep.count += small_rep.count
    del sets_map[small_rep]
    return large_rep

def create_data(edges, node_map, sets_map):

    # sort the edges first, according to cost
    edges.sort(key=lambda x:x[2])
    cost_map = {} # key - cost, value - no of paths
    largest_cost = edges[-1][2]

    for edge in edges:
        if find_set(edge[0], node_map) != find_set(edge[1], node_map):
            unioned_set = union(edge[0], edge[1], node_map, sets_map)
            cost_map[edge[2]] = unioned_set.count - 1

    prefixed_cost_data = {0: 0}
    for i in xrange(1, largest_cost+1):
        val = cost_map.get(i, 0)
        prefixed_cost_data[i] = prefixed_cost_data[i-1] + val

    return prefixed_cost_data

if __name__ == '__main__':
    n, q = map(int, raw_input().split())
    sets_map = {}
    node_map = {}
    for i in xrange(1, n+1):
        new_set, new_node = make_set(i)
        sets_map[new_node.head] = new_set
        node_map[i] = new_node
    edges = []
    for _ in xrange(n-1):
        edges.append(map(int, raw_input().split()))
    prefixed_cost_data = create_data(edges, node_map, sets_map)
    for _ in xrange(q):
        l, r = map(int, raw_input().split())
        print prefixed_cost_data[r] - prefixed_cost_data[l-1]

Let me explain the logic above, which I have derived from this comment -

I sort the edges according to their cost. I then iterate over them and construct the tree edge-by-edge by unioning each vertex, which is initially a disjoint set containing itself (make_set). At any point, no_of_vertexes - 1 gives the no of paths in the tree that contain the maximum cost, which is what I use in unioned_set.count - 1.

This gives me a cost_map with keys as the costs and the values as the number of paths. I also generated a prefixed sum array so that to get the output for [L, R], instead of calculating the no of paths for each value in the range, I can just do prefixed_cost_data[r] - prefixed_cost_data[l-1].

The implementation of the disjoint set is taken straight from CLRS (Section 21.2).

I think the above logic is correct, but I guess it's too slow since most of the test cases timeout.

Can anyone help me in optimizing it? I guess the entire logic needs to be revamped.


texts: Show that language of distinct binary strings is irregular

texts:
Let $Σ =\{\textbf{[},\textbf{]},\textbf{,},\textbf{0},\textbf{1}\}$, and let $L⊂Σ^*$ be the language containing list representations of finite sets of binary strings: i.e., every string $x∈L$ is of the form $x= \textbf{[}x_0\textbf{,} x_1\textbf{,} \ldots\textbf{,} x_n\textbf{]}$, where:

for all $0\le i\le n$, $x_i$ is a string in $\{\textbf{0},\textbf{1}\}^*$, and
none of the $x_i$ repeat: if $i$ is not equal to $j$, then $x_i$ is not equal to $x_j$.

Show that $L$ is not regular.

$\
\\$

$\textbf{EDIT: Below is my attempt: }$

Suppose $L$ is regular.

Suppose the pumping length is n.

Consider the string $x$ = $[0^n, 0^{n-1}, ... , 0]$.

By the Pumping Lemma, $x=uvw$, where

$u$ = $[$
$v$ = $0^n$, $0^{n-1}$, $0$
$w$ = $]$

Then, $|v|>0$ and $|uv| \leq n$

So, $x \in L$ and $|x| \geq n$.

$\
$

Choose $k=2$.

Then, $uv^2w$ = $[0^n, 0^{n-1}, ... , 0  0^n, 0^{n-1}, ... , 0]$

Since each of the strings in x are repeated, this is a contradiction to the Pumping Lemma. Therefore, $L$ is not regular.


texts: Automaton without variables and guards for queueing system

texts:
Disclaimer: Assignment question.

I am trying to solve the below question, the condition is not to use guards and variables. Is it at all possible to do this?

My approach was to have 4 separate automatons, 1 for each of the three servers and 1 for the entire system(with states for 0, 1 and 2 customers in the system). But its not working for all the conditions.
Any help is appreciated.


texts: Example of reduction such that it is not many-one reduction while it is not turing reduction

texts: I am reviewing things I learned, and I can't suddenly come up with an example of reduction that is not many-one, but Turing reduction. Can anyone present such an example?


texts: In a LP problem Ax = b, how to solve for A instead of x?

texts:
I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A.
Constraints are:

Each column of A must add up to 1.

A will start with some values being 0, and those must remain 0. In other words, A is sparse.

I know of algorithms to solve MOLPs like simplex and Benson's, but I'm seeing differences between how the inputs to those algorithms are expressed and how my problem is framed. What I'm looking for is how to transform or reframe my problem so that it can be solved by these algorithms, or alternatively, how an algorithm can be changed to accommodate the extra constraints.
The main differences I see are:

In most MOLPs of the form Ax = b, A is known and x is the thing to be solved for. In my problem, it's the opposite. x is fixed, and A is what needs to be solved for.

In my problem, x can contain both positive and negative values, and the objective is to get each row of b as close to zero as possible. I feel like this can be dealt with with slack variables, though, so that's not as much of an issue.

How to incorporate my constraints of A's columns adding up to 1, and A's sparcity.


texts: What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?

texts:
On an imperative programming language, let us consider the following program:
for i in 0..N { // N is the length of the arrays A, B, C.
  A[i] = A[i] + B[i];
}
for i in 0..N {
  A[i] = A[i] + C[i];
}

This program just sums three arrays $A + B + C$ component-wisely and store it to $A$.
We can easily transform this program into the following equivalent one:
for i in 0..N {
  let tmp = A[i] + B[i];
  A[i] = tmp + C[i];
}

I think the latter code is more efficient than the former because we can decrease the number of memory accesses.
Now I have a question.
What is the name of this type of program transform or program optimization?
Can we also call this deforestation?


texts: I currently have an undirected weighted graph. I am trying to find a good algorithm for learning/finding a cluster of closely related nodes and/or loosely relationship within a cluster in a graph given a size of the cluster. For example, here the longer edges represent the farther relationship between 2 nodes. We identified 2 clusters where each cluster has a close relationship internally. I am new to computer science, could you please suggest an algorithm or a paper for this problem? Your help is really appreciated!


texts: Finding the minimum cut of an undirected graph

texts:
Here's a question from a past exam I'm trying to solve:

For an undirected graph  $G$ with positive weights $w(e) \geq 0$, I'm trying to find the minimum cut. I don't know other ways of doing that besides using the max-flow min-cut theorem. But the graph is undirected, so how should I direct it? I thought of directing edges on both ends, but then which vertex would be the source and which vertex would be the sink? Or is there another way to find the minimum cut?


texts:
I came across the Python library libgpuarray and was reading about it but could not really understand what a GPU array is and why do we need it? What is the difference between a normal array and GPU array?

Please excuse the noobness of the question.


texts:
In the proof of TQBF-complete, it says if the input size is i, then the TM for the input has at most 2^i numbers of configuration. Can someone explain why?
The proof is from: http://zoo.cs.yale.edu/classes/cs468/fall12/TQBF-complete.pdf


texts: What is the average time for a node to transmit on the shared medium for Ethernet? (IEEE 802.3)

texts:
Suppose a shared ethernet link L, in which for nodes T1-T4 and a router R are connected:

--------------------------- R
  |     |     |     |
  T1    T2    T3    T4

L has bit-rate C=100 Mbps, and propagation delay is PROP = 10 msec.
Every node transmits packet with probability Pb = 10%. The mean packet length is P(length)=100 KBytes

Note that ethernet uses CSMA/CA

What is the average time for a node to transmit on the shared medium?

What I've tried:

We know that on carrier sense WAIT_BEFORE_RETRANSMITTING = 5*PROP = 50 ms.

We also know transmission_delay = P(length) / C = 8 ms in our case

So, based on those results, I suppose that the average time for a node to transmit on the shared medium is 50 + 8 = 58 ms


texts: In determining whether any segments intersect, why there must be some sweep where segments $a$ and $b$ are consecutive?

texts:
In CLRS, Section 33.1, we are given the any-two-segments-intersect algorithm. It's a cool algorithm for sure but going through the correctness proof, I don't know how they arrived at the following conclusion:

"Given that we have two segments (call them $a$ and $b$) that intersect at some point $p$, then there must be some sweep line $x$ for which the intersecting segments $a$ and $b$ are consecutive in the total preorder."

Why must $a$ and $b$ be consecutive at some sweep line?

I do see why visually using the figure 33.4 (page 1023) but I don't know how to prove this statement. How can I prove it?

If anyone had read that section, please enlighten me.
Thank you


texts: How can one search in O(log n) time in a red-black tree?

texts: How does the search operation for a red-black tree work and how does it take $O(\log n)$ time, where $n$ is the number of items? I know a red-black tree takes $O(\log n)$ recolorings and $O(1)$ rotations, but I was specifically interested in a good description of its search operation.


texts: What are open problems in computer science?

texts:
I should prepare some paper for a colloquium (kinda student-task) and it should cover the following points:

(1) at least one notable discovery in theoretical informatics (or computer science)

(2) at least one open problems in theoretical informatics

(3) an example of short notable proof of some result in theoretical informatics

Can you draw some examples of it? Or some sources?

I would like that it was related with computational linguistics or natural language processing.

Thank you


texts:
I understand that adding the annotations (dependent typing) may cause the type checking of the programming language to become undecidable.

What about type inference ?

Whether type checking and type inference of Agda  is undecidable ?

I'm interested not only in type checking but type inference also.


texts: How can we design an efficient divide-and-conquer algorithm for constructing a round-robin tournament?

texts:
Background and main question

I am studying algorithm analysis and design, and have been going through "Algorithm Design and Applications" by Goodrich and Tamassia.

One of the applications problems (A-11.2) poses the following:

  Given a set, P, of n teams in some sport, a round-robin tournament is a collection of games in which each team plays each other team exactly once. Such round-robin tournaments are often used as the first round for establishing the order of teams (and their seedings) for later single- or double-elimination tournaments. Design an efficient algorithm for constructing a round-robin tournament for a set, P, of n teams assuming n is a power of 2.

The chapter is on the divide-and-conquer method, so I am assuming that they intend for us to use a recursive algorithm to solve the problem.

Approach

I assumed that every team would play in every round (i.e. there is no need for "bye weeks").

I tried to tackle this problem via two different approaches:

1) Place each team in a some sort of collection (or, assign each team an integer, and place those into a collection). Pop the head element from the collection, and make pairs with the elements remaining in the collection. Use these pairs to populate an n - 1 rounds * n - 2 matches grid, where n, as in the problem, is the number of teams. Repeat until one element is left in the collection.

This is not a "true" divide-and-conquer approach, and is O((n-1)!), I believe.

2) Use n - 1, n * n binary matrices to plot the matches for each round.

This approach is not divide-and-conquer at all. I know intuitively that it will work, but I'm not sure how I would implement it programmatically.

Conclusion

How can we solve this problem via the divide-and-conquer approach?

What kind of asymptotic behavior can we expect?


texts: Exhaustive list of ways to distribute n objects to k sets

texts:
I am working on a research paper and we are developing a brute force algorithm to examine another clustering technique.

In this brute force algorithm we test every possible clustering example and see what natural clusters occur.

The problem comes from the assignment of every possible clustering. If give each value a cluster sequentially the complexity is much higher than necessary and results in many overlaps.

Sequential Example: 5 objects into 3 clusters
 11111, 11112, 11113, 11114, 11115, 11121, etc. . .

But 11112 and 11113 are effectively the same. The complexity above is O(k^n) where k is the number of clusters and n is the number of objects. This makes for a terrible time afterwards because duplicates will not be fun to work with and parse. Looking at natural clusters becomes easier with more points as well, and in a simple example, assigning 20 to 5 results in 3,200,000 mostly duplicate clusterings.

If we look at this using combinatorics then we can assign n objects to k groups in (n + k - 1) C (k - 1) ways. This results in 20 objects to 5 clusters having only 10626 different combinations.

Is there any way already made to exhaustively produce these arrangements in this way to eliminate the duplicates?


texts: Analysis of Algorithms: Applying Concepts

texts:
I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application.

I understand that if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$ then $f(n) \in \Theta(g(n))$

Essentially, when Big-O and Big-Omega form the upper and lower bounds of algorithmic performance, Big-Theta represents the optimal solution. But how does one determine those bounds and thus optimal performance?

How does/should one determine Big-O, Big-Omega, Big-Theta for the following algorithm?

int summation(int[] values)
{
  int sum = 0;
  for(int i = 0; i < values.length; i++)
  {
    sum += values[i];
  }
}


texts: Storing a configuration of nondeterministec machines in log space

texts:
In Sipser's book page 351:

  Recall that Savitch's theorem shows that we can convert nondeterministic TMs to deterministic TMs and increase the space complexity $f(n)$ by only a squaring, provided that $f(n) \geq n .$ We can extend Savitch's theorem to hold for sublinear space bounds down to $f(n) \geq \log n .$ The proof is identical to the original one we gave on page $334,$ except that we use Turing machines with a read-only input tape; and instead of referring to configurations of $N,$ we refer to configurations of $N$ on $w .$ Storing a configuration of $N$ on $w$ uses $\log \left(n 2^{O(f(n))}\right)=\log n+$ $O(f(n))$ space. If $f(n) \geq \log n,$ the storage used is $O(f(n))$ and the remainder of the proof remains the same.

Later on he mentions:

  To show that the reduction operates in log space, we give a log space transducer that outputs $\langle G, s, t\rangle$ on input $w .$ We describe $G$ by listing its nodes and edges. Listing the nodes is easy because each node is a configuration of $M$ on $w$ and can be represented in $c \log n$ space for some constant $c$.

My question is how exactly does a configuration get stored on the output tape? and how is it represented by a logarithmic term (does it differ between different encodings of a configuration)?

Also a small question, when talking about a machine's configuration on input $w$, do we actually mean configuration graph all inputs of length $|w|$? is that why $w$ is not part of the configuration graph?


texts: Questions from Dijkstra's EWD 1300: "The notational conventions I adopted, and why"

texts:
A link to the transcript of the manuscript: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1300.html

My questions:

What does Dijkstra mean by:

  "Do not introduce priority [precedence] rules that destroy symmetry. I remember how
  much more pleasant the predicate calculus became to work with after we
  had decided to give con- and disjunction the same binding power and
  thus to consider p ∧ q ∨ r an ill-formed formula."?

Specifically: can you illustrate how a precedence rule where conjunction has higher precedence than disjunction would destroy symmetry?

Then, what does he mean by (please note that he uses the "." operator to denote function application):

  "As time went on, I learned to appreciate expressions built with
  operators as a way of avoiding functional notation. We can write the
  difference  a−b  as  dif.(a, b) or exc.(b, a), where min and exc are
  functions of an ordered pair. (I believe that the notion of “function
  of 2 arguments” is now obsolete.) But we can also write the “curried”
  versions (min. a). b and (sub. b). a in which, for instance, sub is a
  higher-order function such that sub. b decreases its argument by b (so
  that sub.(−1) would be the successor function). Functions dif, exc,
  min and sub are different functions and as soon as the operation of
  functional composition enters the game, the distinctions are
  essential. But as long as we don’t do functional composition, the
  choice between the four options is irrelevant and writing the
  expression a−b is a lovely way of avoiding being overspecific."?

Specifically: what is the function exc, and how is it that a-b can represent both exc and min? Am I correct in understanding that min is the minimum function?


texts: Is unification over regular expression equations doable?

texts:
By way of example, suppose I know that $X + a = b + Y$ where $X$ and $Y$ are variables standing for regular expressions, then $(X, Y) = (b, a)$ is a solution to this set of equations.

Generalizing over all such equations, is there a computable (decidable) procedure for calculating the regular expressions which the variables must stand for in order for the equation to be solvable? Is there some kind of uniqueness, e.g. of minimal solutions?

In case the alphabet size matters: you can represent $\{1, \ldots, n\}$ in unary using just two symbols, so I assume the answer for $k$- and $m$-symbol alphabets are the same when $k \geq 2 \land m \geq 2$, in which case I care primarily for alphabets of size $\geq 2$—the reason I stress the word "assume" is that I know some properties of regular languages don't hold for regular expression equations (when suitably translated).

The application I have in mind is miniKanren-style logic programming.

Since families of sets closed under union form a semilattice, and the family of regular languages is one such closed family, programming with regular languages seems straightforward. For example, let each logic variable $V$ represent some indeterminate language $L$. For each $V$ store a pair of bounds $(sub, disj)$ expressing the knowledge $sub \subseteq L \land (L \cap disj) = \emptyset$, i.e. store two sets of strings for which the membership-ness is known. Grow them in the variable unification part and fail when $sub \cap disj \not= \emptyset$.

It would be nice to add logic over regular expressions and not just regular languages.  No obvious approach occurs to me, and I suspect it's a whole other ballgame.


texts: Reducing Graph Reachability to SAT (CNF)

texts:
So I came across this problem in my textbook. I was wondering how to develop a reduction from the Graph Reachability problem to SAT (CNF) problem. (i.e. formula is satisfiable iff there exists a path in graph G from start to end node)

1) I can't wrap my head around how to go from something that can be solved in polynomial time (Graph Reachability) to something that is NP (SAT).

2) I can't seem to find a way to formulate these nodes/edges of Graph into actual clauses in CNF that correspond to reachability.

I tried to think about algorithms like Floyd-Warshall that determine if a path exists from start to end node but I can't seem to formulate that idea into actual CNF clauses. Help would be much appreciated!


texts: Compute height of AVL tree as efficiently as possible

texts:
Given an AVL tree, I want to compute its height as efficiently as possible. $\newcommand{\bf}{\text{bf}}\newcommand{\height}{\text{height}}$

Each node of an AVL tree stores its balance factor ($\bf$), defined as

$$\bf(v)=\height(v.\text{left}) - \height(v.\text{right}).$$

We can recursively compute the height of an AVL tree in $O(\log n)$ time, using the following recursive procedure:

Height($v$):
1. If $v$ is a leaf node, return 0.
2. If $\bf(v)=+1$, return Height($v.\text{left}$).
3. If $\bf(v)=-1$, return Height($v.\text{right}$).
4. If $\bf(v)=0$, return Height($v.\text{left}$). (returning Height($v.\text{right}$) would work too)

This recursive algorithm works, because the balance factor tells us which is taller, the left subtree or the right subtree, and the algorithm always recurses into the taller subtree.

My question is: Is there a faster algorithm?  Can we do better than $O(\log n)$ time?  Assume we can't augment the tree to store extra information in it; we are restricted to only the information that is already normally stored in an AVL tree.


texts:
I want to use Vertex Cover as a known $NP$-complete Problem for the reduction.
The claim is that if a have a vertex cover in graph $G$ with size $\le k$, I will have a clique cover in $G^\prime$  with total number of cliques $\le k$

I want to reduce vertex cover problem to clique cover problem in the following way:

For each edge in $G$, I will create a corresponding vertex in $G^\prime$. In the picture, each e$_i$ in G corresponds to v$_i$ in $G^\prime$ for $1\le i\le5$
Two vertices in $G^\prime$ will be connected by an edge if their corresponding two edges in G have one vertex in common. For example, there is an edge between v$_1$ to v$_2$ as their corresponding edges e$_1$ and e$_2$ have one vertex in common which is a.
Each clique in $G^\prime$ corresponds to a vertex in G and that vertex belongs to the vertex cover. For example, for the graph in picture I have vertex cover {a,c}. With vertex a, I get  a clique  {v$_1$, v$_2$, v$_5$} and with vertex c, I get clique {v$_3$, v$_4$} in $G\prime$.

Now I don't know how to prove No instance in opposite direction: If $G^\prime$ doesn't have a clique cover with $\le k$ cliques (i.e it needs at least $k+1$ cliques), $G$ doesn't have a vertex cover size which is $\le k$.

Can anybody shed some light on this issue?


texts: Lower complexity bounds without mutation

texts:
Lower complexity bounds tend to be a very hard problem in general. Despite this, I was wondering if there are any theoretical results that relate lower complexity bounds for some class of problems in the case where mutation is allowed and in the case it's not allowed? In particular, what type of problems would be inherently harder to solve in a purely functional language on a RAM machine?

The following problem is why I started thinking about this: https://stackoverflow.com/questions/24105301/number-of-occurrences-in-list-of-each-element


texts: Regex for the language over $\{a,b,c\}$ that contain at least two $a$'s but no two consecutive $b$'s

texts:
Like the title says, we have the alphabet $\Sigma = \{a,b,c\}$ and the question is asking for the regular expression of the language $L$ that has the property that all strings in $L$ have at least two consecutive $a$'s but no consecutive $b$'s.

By attempt at a solution was this, where $aaa^+$ stands for $aaa(aaa)^*$:

$$(a+c)^*aaa^+(a+c)^*b(a+c)^* + (a+c)^*b(a+c)^*aaa^+(a+c)^*$$

but I know this is wrong since we never get an instance of consecutive $b$'s. Can someone point me in the right direction?


texts: Understanding Binary Search for Kth Smallest element in an Array

texts:
The Answer here shows a way to solve the problem with O(1) space. The approach uses Binary Search. I am finding really hard to wrap my head around why it works. I get why we did low + (high-low)/2 cause we needed to adjust the mid value based on the start and end of our range. The thing I just can't seem to wrap my head around is why does it work? The numbers in the array are unsorted and not contiguous,duplicates may exist so why does reducing the search space in our range based on countless or countequal give us the correct answer?
Can someone give some intuition or simple explanation to why this works?


texts: The definition of weakest precondition for a non-deterministic language

texts:
In the classical IMP language, the definition of weakest precondition is:

definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t"

This is stating that from state s, after executing c we get to a state satisfying Q. My question comes when handling the IF FI construct in the language of guarded commands (see selection command in Wikipedia). My guess is that in this case one needs to define:

definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ (∀ t'. (c,s) ⇒ t' ⟶ Q t')"

I wonder if this is correct and whether it is the standard way of writing it in the literature.

Currently, I'm having problems proving the weakest precondition definition for the sequential composition of commands:

"wp (c1;;c2) Q s = wp c1 (wp c2 Q) s"

So, I'm beginning to think my definition is wrong. Quoting wikipedia:

  the result of this function, denoted wp(S,R), is the "weakest"
  precondition on the initial state ensuring that execution of S
  terminates in a final state satisfying R.

so termination is required in the definition, and this is not properly imposed so far. There could be non-terminating branches.


texts:
We are given a directed graph, the number of vertices and edges. We need to decide, whether there is a [starting] vertex where we can get started and visit all the vertices. You can revisit vertices, but can't "use" edges twice or more time. All this in linear time.

I was thinking about DFS - if the number of vertices in the result matches the total number of vertices, obviously there is a way to visit all the vertices. The only problem about this - I guess - is that how do I choose the vertex where I'm starting off. Or can I do DFS with all the vertices and still remain in linear time?

(I tried to look into Eulerian path and Hamilton path problems, but I think they have nothing to do with my problem)

Any feedback is appreciated.


texts: Question on crc32 -> 64 by multiplication

texts:
Having a hash quickly accessible in a large database is a good thing, most hashes these days are much too large for that.
Best performance on a database is 32 bit int followed not too far off by 64 bit int keys but accessing a MD5 key already comes with a noticeable performance hit and requires (more than) twice the memory which matters when you have billions of rows.

Using CRC32 for hashing has a too high collision risk in my task but 64bit would be fine, however there is no nice native 64 bit hashing function available.

I wondered if I can just calculate two CRC32 hashes.
For example one hash of the string and one hash of the reversed string or with a couple bytes offset.
Then I multiply both 32 bit hashes with each other, which gives me up to 64 bit results.

Would that be an acceptable method to gain a proper 64 bit-ish hash from the 32 bit CRC function ?


texts: Comparing dual of a canonical primal program - Directly and by dual of the standard program

texts:
I have it as a homework question to compare dual programs in the following way:

Take a canonical program and write its dual
Take the same canonical program, write it as a standard program, take the dual of the latter, then write it as a canonical program.

In the following image, option 1 is starting with the upper left square and going right, and option two is (starting with the same place and) going down and then right and then up.

I have tried to do this, both in general and both by example, but I'm getting something strange: First I add slack variables to move from inequalities to equality, and I add the constraint that all slack variables are positive.

Then I write the dual of that program, the inequality look like $[A|I]^Ty\leq [c|0]$

(here $[A|I]$ denotes a block matrix) which gives two sets of inequalities: one is $A^Ty\leq c$ and the other is $Iy\leq 0$. Which is almost like the CD form in the picture - but I got $y\leq 0$ instead of $y\geq 0$.

Why do I get a different result ? I guess I have some error and that I should actually get $y\geq 0$, but I checked multiple times and I don't see any errors.


texts:
I just read some pages in Sipser's book Introduction to Theory of Computation about Post Correspondence Problem, and I'm thinking that PCP is actually in NP. The certifier is: for an input configuration of pile
$$(t_1/b_1, t_2/b_2,...t_n/b_n)$$
concatenating $t_1, t_2,...,t_n$ as a string $t$ and concatenating $b_1, b_2, ..., b_n$ as a string $b$, then compare $t$ and $b$ to see if the two are equal and then conclude that the input is actually a solution to PCP.


texts:
Suppose you have to provide a derivation by natural deduction, e.g.

$((A \rightarrow B) \rightarrow A) \rightarrow A$

Is it a good advice to start from backwards on in general?
I mean doing the derivation from bottom to top. The required premises or hypothesis should arise by itself.


texts: Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration

texts:
I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations.

Clojure provides persistent Vector, but it's only for fast append. Scala's Vector has effectively constant-time append and prepend, but I can't get how it's implemented, since it's based on same data structure (bit-mapped vector trie) as Clojure vector, and, as I understand, bit-mapped vector trie can't have fast prepend without some tricks.

I'm interested not in ready to use implementation but in a description of how to implement such a data structure myself.


texts: Where/when did Stephen Kleene first define the Kleene closure/star?

texts:
I'm working on a paper and would like to review the origins of Kleene's closure. I am unable to find any article of Kleene's that has the original definition of the Kleene closure.

Is there a paper by Kleene in which he first defines the Kleene closure?


texts:
Suppose you have two large lists of integers of length $N$, and you want to find two pairs $(a_1, b_1)$, $(a_2, b_2)$ from the lists such that $a_1 + b_1 = a_2 + b_2$ (modulo the integer width). Say for example, that $N = 2^{32}+1$ and the integers are 64 bits.

Is there any efficient way to do this? I know that if you are given a particular value, you can easily find the pairs that sum to that value in linear time, so the hard part is finding the colliding sum value in the first place. The obvious approach is $O(N^2)$, but I can't think of anything better.

One other idea I had was to try FFT to do a convolution on the lists, but I don't think that helps because the lists of integers are sparse, while my understanding is that the fourier transform would involve computing $2^{64}$ elements.

This answer says that there is an $O(N^{4/3})$ algorithm if the integers are randomly distributed, but doesn't provide any details.


texts: Bounded treewidth implies bounded clique-width

texts:
We have a graph G of treewidth $\operatorname{tw}(G)\leq k$, for some $k\in\mathbb{N}$. I've seen a claim that that implies that the clique-width of the same graph is at most $k \cdot 2^k$. This implies that given a tree decomposition of the graph we can construct a proper expression tree using at most $k \cdot 2^k$ labels.

I'm guessing that the $k$ in the decomposition allows us to "construct" a node of the tree decomposition, i.e. regardless how the vertices in one bag are connected, we can easily connect them since we have $k+1$-ish labels at our disposal. However, I don't quite see how we can use that fact to construct the complete expression tree (and therefore the $k\cdot 2^k$-expression).

How can we construct the proper expression and therefore prove that graphs of bounded treewidth are a subclass of graphs of bounded clique-width


texts: Proving that a preorder traversal of a rooted tree can be performed in linear time

texts:
Definition:
Let $T(V, E)$ be a rooted tree with root $r$.
If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$.
If $\lvert V \rvert > 1$, let $T_1, T_2, \dots, T_k$ denote the subtrees of $T$ from left to right. The preorder traversal of $T$ first visits $r$ and then traverses the vertices of $T_1$ in preorder, then the vertices of $T_2$ in preorder, and so on until the vertices of $T_k$ are traversed in preorder.
Question:
How does one prove, using the above definition, that a preorder traversal of a rooted tree $T(V, E)$ can be computed in $O(\lvert V \rvert)$ time? Since $T$ is a tree, $\lvert E \rvert = \lvert V \rvert - 1$, and so showing that a preorder traversal algorithm simply visits the vertices and edges of $T$ a constant number of times and does constant work on each visit would do it. Obviously this is true, but how does one prove this formally?


texts: How many combination of “n” bits are there in terms of n?

texts: How many combination of "n" bits are there in terms of n? And if this is derived, Given 4 bits for representing negative and positive numbers, what is the largest positive number that can be represented?


texts: Depth perception - detect how far into a scene a user is looking

texts:
I would like to know about how we can detect how 'deep' into a scene a user is looking. If looking into a 3D environment, with an object close to the user and one further away, how can we detect when the user is looking at the object further away? Or, rather, how can we detect which object a user is looking at in a 3D environment?

I am asking here because I'm not sure what this technology is called, or even if it exists, and so am hoping for some pointers into what I should be reading/looking at.

If anyone has some resources for me (links, algorithm names, books, articles, etc.), it would help a lot, but if you are able to explain a little, I'd really appreciate that, too.

Many thanks.


texts: Why is Quicksort described as "in-place" if the sublists take up quite a bit of memory? Surely only something like bubble sort is in-place?

texts:
Quicksort is described as "in-place" but using an implementation such as:

def sort(array):
    less = []
    equal = []
    greater = []
    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
        return sort(less) + equal + sort(greater)
    else:
        return array

You have to create a copy of the list for each recursion. By the first return, in memory we have:

array
greater+equal+less

Then by the second recursion across all sub-lists we have:

array
greater, equal, less from first recursion
greater+equal+less from less1, greater+equal+less from greater1

etc...

Is this just badly written code or am I correct in thinking that for a big list, you actually have to have, proportionally, a fair amount of extra space to store thse?

When I think of something that is "in-place", I think of bubble sort, which simply swaps elements in the list like: http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif

BubbleSort only requires 1 extra variable to store a potentially swapped element.


texts: Algorithm to check if a family contains two disjoint sets

texts:
Let $\mathcal F_1$ and $\mathcal F_2$ be a families of subsets of $\{1,\dots, m\}$. Such that $|\mathcal F_1| = n_1$ and $|\mathcal F_2|  = n_2$.
I would like to check if there is $f_1\in \mathcal F_1$ and $f_2\in \mathcal F_2$ with $f_1\cap f_2 = \varnothing$
One approach is to go through all $n_1n_2$ possible pairs and calculate the intersection for each one in $m$ time (or it can be $min(|f_1|,|f_2|)$ time but this doesn't matter to me).
Is there a faster way? reading the input would take $(n_1+n_2)m$ time. If there was anything of time $(n_1+n_2)^{2-\epsilon} p(m)$ where $p$ is polynomial that would be great.


texts: What is the current state of the art in solving the halting problem?

texts:
Yes, I know it's uncomputable in the general case. What I want to know is what special cases have been solved, and if there is work ongoing on finding or developing more of them.

To be a little more explicit about the sort of thing I'm looking for, total functional language compilers have to approximate the halting problem, proving that your source code terminates or saying it can't thus prove it. Idris, as far as I can tell, just uses a "one argument must be structurally smaller on each recursive call" primitive-recursion checker*; Isabelle is more sophisticated, with

datatype rosetree = Rose "'a rosetree list"

primrec rosemap :: "('a => 'b) => 'a rosetree => 'b rosetree" where
  "rosemap f (Rose as) = Rose (map (rosemap f) as)"

compiling fine despite the intermediate map on the recursive calls. Isabelle's fun mechanism seems even more powerful in terms of proving termination (although I can't think of a short, simple example for that off the top of my head).

Basically: how do these work? Are there papers or textbooks about the algorithms involved somewhere? Is finding heuristics for the halting problem a current research subject?

*If I'm wrong about this, please do let me know about that, too.


texts: The task of recognizing game units in the screenshot

texts:
I'm new to computer vision and I want to solve the task of recognizing the game units of the game Clash Royale in the screenshot.
Briefly, there are about 70 different types of gaming units belonging to two teams (they differ a little in colors and some are visible in front, others with backs). I want to find game units on the screenshot and classify their type of unit (then health and the team).

What are the best tools for task like this? What libraries will I use to simply teach the model? How many teaching examples do I need to learn the model? It seems that the quality of the screenshots is quite good and the images are clear. To what size should I reduce the screenshoot to get a good model and its speed? Maybe someone had a similar experience?

I think about CNN or a lot of HAAR cascades for each of the types of units, but I would like to receive advice.


texts:
I wanted to understand the Myhill-Nerode Theorem so I made up a small example to do so.

  L = (a $+$ b )

Clearly, this language is regular. So, I should be able to establish a finite number of equivalence classes by using this method.

I start with a suffix of length 0, which is only $\lambda$:

a$\lambda$ = a $\in$ L
b$\lambda$ = b $\in$ L

For all suffix strings of length $\nu \gt 0$, both are not elements of L.
Therefore, there are no distinguishable strings. I suspect this means there are 0 equivalence classes, and since 0 is a finite number, the language is regular. What might be missing from this analysis?

Note: I made sure to do some online research already and feel comfortable with the ideas of distinguishable strings. The equivalence class bit is what I probably need some clarification on.


texts: Is there any proof that quantum computers are more efficient than classical computers?

texts:
Shor's algorithm is often used as the argument. It can solve the factorization problem faster than any known algorithm for classical computers. Yet, we have no proof classical computers can't also factor integers efficiently.

Is there any actual proof quantum computers can solve some problems faster than classical computers?


texts:
I have a set $S = \{0,1,2,3,4,5,6,7,8,9\}$. $S_i \subset S$ for $i = {1,2,3,4,5}$. Any three $S_i$ has the same union, that is $S_1
\cup S_2\cup S_3 = S_1\cup S_2\cup S_4 = ...=S_3\cup S_4\cup S_5 = A$ and no $S_i\cup S_j = A$. What is lexicoraphical least of such $S_i$s?
I have to write a Python code for this and I would appreciate any help that could direct me to find a solution. What should I know to be able to solve this problem in the shortest possible period? Also, if there's a better way to formulate this problem please do leave me comments with your suggestions. If the information is not sufficient I can clarify further.


texts: Can the complement of a non-recursive language be RE

texts:
I've got a problem where I need to check the validity (i.e to say whether it's true or false) of the following statement:

  Complement of a non-recursive language can NEVER be recognized by any turing machine.

How I've thought of this is that, if a language $\mathcal{L}$ is non-recursive, there is no turing machine that accepts the language. That is, there's no TM that halts for every string in $\mathcal{L}$. But there could be a TM $M_1$ that halts for some of the strings in $\mathcal{L}$.

Now suppose, the proposition is $\ false$. So there could be a TM ${M_2}$ that recognizes the complement of $\mathcal{L}$. So ${M_2}$ halts and accepts every string that is NOT in $\mathcal{L}$ and may or may not halt for strings in $\mathcal{L}$.

Intuitively, It appears that ${M_1}$ and ${M_2}$ could be same, which makes my assumption $\ true$. That is the the proposition is $\ false$.

But I'm not certain about the arguments I've made (as the equivalence of $M_1$ and $M_2$ is based on intuition). Can someone verify whether I'm correct or correct me otherwise.


texts: Minimum time to assemble multipart object

texts:
I've been asked to do this task in an online assessment. I've passed, so my solution is supposedly correct, but I am unable to prove it. The task is:

Given a set of parts (array of integer part sizes), worker must put them all together. Parts are assembled in pairs. To put together two parts of sizes A and B worker needs A+B minutes. The resulting part's size is also A+B. Write a program to determine the minimum time required to put together given set of parts.

My solution was:

MinHeap h
for p in parts:
  h.push(p)
time = 0
while h.size() > 1:
  v1 = h.pop()
  v2 = h.pop()
  time += v1 + v2   ### assembly time
  h.push(v1 + v2)   ### adding new part
return time

This solution passed all tests.

Question:

Does this solution produce correct min time, and if yes, how to prove it?


texts: What's a real life usage for detecting communities in complex systems?

texts:
I am reading through the Girvan-Newman description, having come from the topic of "detecting communities in a complex system".

What exactly is a community in this context and why is it useful for a network to know about it? In simpler terms, what's a real-life usage of this algorithm?


texts:
Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$.

I have been doing a few exercises on Big O and this is the first time I have encountered the variable in the exponent.  I was wondering how to disprove this function.  Any help would be appreciated


texts: What's the difference between the concatenation and union of symbols within a language

texts:
I feel like I'm confusing myself perhaps but I'm having a bit of trouble figuring out how exactly this language works. I'm given the following regular expression

(a + b)* (abba* + (ab)*ba)

Can someone clarify to what union is compared to concatenation? Looking at

(a + b)*

Is it { $\epsilon$, a, b, ab, ba, aa, aab, bbb...)? I just want to make sure, for union, that I can have any combination of a and b in whichever order.
Can I also have an example of what a word from this language may be? From what I gathered

aaababbaabbaababba
abbaba
bba
ba

would all be valid words in the given language, correct?


texts: Data structure for selection of K elements and taking sum

texts:
The problem:

We are given an array $A$, an integer $Z$ and a value $Q$. The goal is to maximize the sum of $A$, by performing following operation any number of times:
We can select exactly $Z$ elements from the given array and perform XOR on each of them with $Q$.

Is there any data structure I can use which can perform this efficiently or any algorithm I am not aware of?

I tried finding each element's maximum possible value (using XOR/ignoring it), sorting the array and then making the selection but it did not work, which leads me to believe that the greedy approach won't work here.

I am primarily looking for an algorithm that can help or a data structure, not necessarily the code.

For example, given the array $[1, 2, 3, 4, 5], Z = 2$ and $Q = 4$, the answer is 23 as I can take XOR of 1 and 2 with 4 and of 3 and 4 with 4 as well.

Edit: The sum 23 is obtained as follows: We need to select Z (2) values at a time. So we select 1 and 2 and obtain their XOR with Q(4), which makes it 5 and 6. We then select 3 and 4 and obtain their XOR with Q, which makes them 7 and 0. Thus the final array becomes $[5,6,7,0,5] which is equal to 23 and is maximum possible sum.


texts: How can I reduce the time of this program

texts:
I solved a problem similar to the knapsack problem.

There are two packages with a capacity of $P$ on a production line. We want to put $N$ items in them with the weights $w_1,...w_n$ in a pre-defined order (the best order). We can put an item in the package 1 or the package 2 or close one package and replace it with a new package and put the item in it. What is the minimum number of packages?

Let $m(n,p1,p2)$ be the minimum number of packages for $n$ items where the capacity of package 1 is $p1$ and the capacity of the package 2 is $p2$.

I must keep track of the free capacity of each package which is not always $P$ (empty state)

let $w_n$ be the weight of the $n_{th}$ item.

It's my solution using dynamic programming:

def packaging(N, P1, P2, w):
    M = np.zeros((N+1, P1+1, P2+1))
    for n in range(N+1):
        for p1 in range(P1+1):
            for p2 in range(P2+1):
                wn = 0 if n == 0 else w[n-1]
                if n == 0:
                    M[n][p1][p2] = 0
                elif wn > p1 and wn > p2:
                    M[n][p1][p2] = M[n-1][p1][p2] + 1
                elif wn > p1:
                    M[n][p1][p2] = M[n-1][p1][p2-wn]
                elif wn > p2:
                    M[n][p1][p2] = M[n-1][p1-wn][p2]
                else:
                    M[n][p1][p2] = min(M[n-1][p1-wn][p2], M[n - 1][p1][p2 - wn])
    return M[N][P1][P2]

Its order is $O(NP^2)$. There is an $O(NP)$ solution for it. How can I enhance my solution to reach it?

Further updates might come to reformat the solution in a mathematical notation.

Source: Tehran University, Fall 2018, Advanced algorithms practice


texts: will this be decidable or partially decidable?

texts:
$A=\{\langle M \rangle \mid M \text{ is a turing machine and }|L(M)|\geq3\}$

Since Recursive enumerable languages are turing enumerable, so listing of all strings of the language in finite time is possible. Then deciding whether cardinality is greater than 3 should be decidable. But the material that i have been studying says it is partially decidable. Which one is right?


texts: Can we use Operator precedence parsing with this grammar?

texts:
This Grammar:

A-->Bbab|aa

B-->b

I think we can't because basically there is no relation between terminals? like no relation between a and b! or am i missing something? and the language of this grammar has only 2 members !

can we using Operator precedence parsing with this grammar?


texts: What can we say about decision problems having a polynomial time algorithm, ie, in $P$? Do they always have polynomial sized circuits (but not circuits of polynomial depth)?


texts: How to resolve a recurrence relation in the form of $T(n) = T(f(n))*T(g(n)) + h(n)$

texts:
I am basically trying to solve the following question:

Given a set $P = \{\{1\},\{2\},\dots,\{n\}\}$ of $n$ sets of elements, our aim is to merge these elements into one set.

At each step, sets can be only merged pairwise.

How many different ways can this merge happen?

For instance, given $P = \{\{a\},\{b\},\{c\},\{d\}\}$:

After the first step we can end up with three different combinations:
\begin{array}{c}
P_{11} = \{\{a,b\}, \{c,d\}\}\\
P_{12} = \{\{a,c\}, \{b,d\}\}\\
P_{13} = \{\{a,d\}, \{b,c\}\}\\
\end{array}

And all the sets will be merged after the second step:
\begin{array}{c}
P_{2} = \{\{a,b,c,d\}\}\\
\end{array}
All the examples I could find about recurrences is summation of two recurring functions such as

$T(n) = T(n) + T(n/2) + \Theta(n)$

However, I want to solve a recurrence relation where recurring function is multiplied by itself:

$T(n) = T(n^2-n)*T(n/2)$

I am not sure that I write the recursion correct but this is what I want:

\begin{array}{l}
n\\
\dfrac{n(n-1)}{2}*\dfrac{n}{2}\\
\dfrac{n(n-1)}{2}*\dfrac{n}{2}*\dfrac{\frac{n}{2}\left(\frac{n}{2}-1\right)}{2}*\dfrac{n}{4}\\
\end{array}

At first sight, the number of nodes in the recursion tree grows like $O(n) \rightarrow O(n^3) \rightarrow O(n^6) \dots$ at each level, which can be formulated as $n^{2k}$.

Since the size of the problem is reduced by a factor of 2, we have $\log n$ depth in the recursion tree. Therefore, $n^{2k} = \log n$ and $2k = \log_{n}\log n$ which does not seem a reasonable size.

Where am I mistaken?


texts: Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?

texts:
At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure have computed shortest paths with $k$ length. However, the part that I don't quite understand is why not only relaxing the edges that are directly connected to the source on the first iteration and then the neighbors' edges of those on the second iteration, and then the neighbouring eges of those and so forth?

The idea, is a similar algorithm to BFS I guess. We start from the frontier of edges relaxed and we make sure that we are connected to a node that we have computed its shortest path and since we are always relaxing edges that are connected like that, then we compute the shortest path in 1 pass rather than $O(EV)$ passes. I am sure I am wrong but I don't understand why. Of course it works in a straight line graph, but what type of worst-case input does it make that we need about at least $\Omega(EV)$?

I am mostly interested to understand, is the EV runtime in the worst case. I also do not care about improvements in practice or constant factors. Only asymptotics.


texts: A little confusion with the Knapsack problem (a worked example)

texts:
I'm going through a worked example on the Knapsack problem:

My problem is that I don't understand quite follow the last bulletpoint. Where does the $x_4 = 4/5$ comes from? I know $x_4$ has to be a fraction of 1 (otherwise it breaks the inequality) but why specifically $4/5$? Any insight is highly appreciated.


texts:
I'm currently trying to learn how to infer most general types on lambda calculus, and due to the lack of information on the subject I could find on Google I'm forced to attempt what I think is logical and ask here if it's correct, it's most likely not, so please correct me!

Here's a couple exercises I've got, the idea is to reduce the redex and infer the most general type:

$(λf.λg.λx.g\space x(f\space x)) (λy.y)$
$λz.λx.((λy.λw.y w)x z)$

After I reduce them:

$λg.λx.(g x) x$
$λz.λx.x z$

And my attempt to infer the most general type:

Since $g \space x$ is applied to $x$ I assumed $g$ must be $g :: a\rightarrow (a \rightarrow b)$ while $x :: a$
Then $(λg.λx.(g\space x)\space x)$ must be of type $(a\rightarrow (a\rightarrow b))\rightarrow (a\rightarrow b)$
Since $x$ is applied to $z$, let's say $z :: a$ and $x :: a\rightarrow b$, therefor the function is $a\rightarrow (a\rightarrow b)\rightarrow b$


texts:
Q) Consider an ordinary binary max-heap data structure with n elements that supports insert and extract-max in $O(log(n))$ worst-case time. Give a potential function $\Phi$ such that the amortized cost of insert is $O(log(n))$ and the amortized cost of extract-max is $O(log(n))$, and show that it works.

solution

The formula of amortized cost is

$a_n = c_n + \Phi(D_n)  - \Phi(D_{n-1})$

Where the potential function: $\Phi (D_n) = n log(n)$.

for insert:

$= c_n + \Phi(D_n) - \Phi(D_{n-1}) \leq log(n) + n log(n) - (n-1)log(n-1) \leq 3 log(n+1) = O(log(n))$

So, the amortized cost of insert is $O(log(n))$

extract max:

$a_n = c_n + \Phi(D_n) - \Phi(D_{n-1}) \leq log(n) + n log(n) - (n+1)log(n+1) = log(n) + n(log(n)) - n log(n+1) - log(n+1) < 0$

So, the amortized cost of extract-max is $O(1)$

Assuming this is correct. Could someone explain how they got the potential function?


texts:
I'm trying to solve a graph problem ( it's not for homework, just to practise my skills ).

A dag $G(V,E)$ is given, where $V$ is the set of vertices and $E$ the edges. The graph is represented as an adjacency list, so $A_i$ is a set containing all the connections of $i$.

My task is to find which vertices are reachable from each vertex $v\in V$.

The solution I use has a complexity of  $O(V^3)$, with transitive closure, but i read that in a blog it can be faster, although it didn't reveal how. Could anyone tell me an other way ( with better complexity ) to solve the transitive closure problem in a dag? Thanks in advance.


texts: Does a path (as in path graph or linear graph) NFA-epsilon have a simpler or more efficient algorithm other than the subset construction to convert to a DFA?  The only simplifications I have come up with relate to the NFA-epsilon representation, the computation of the epsilon closure, and the DFA representation.  Each NFA node can be represented as a set of symbols transitioned on, if it has an epsilon transition, and a unique reference to the following node.  The DFA representation can use shared references as it is acyclic.


texts: Why superscalar processors use dynamic branch prediction

texts:
I'm studying for an exam on Advanced Computer Architecture and in an exam question the question above is asked.

I know that branch prediction is crucial in superscalar processors in order to exploit ILP as much as possible, but I was wondering what could be the precise reason why superscalar processors use dynamic branch prediction instead of static one.

Update:

Hi again, as the two comments below suggested, I tried to think about it and thought that in case of a misprediction a processor using branch predictor has to flush the pipeline from the incorrect instructions issued because of the prediction.

So, for a superscalar processor issuing multiple instructions at the same time, the penalty would be much higher, but I'm still not sure this is the real point...

Any other help?


texts: Subset sum algorithms, their time complexity

texts:
The algorithm is in Python. Seems correct to me, ideas how to prove it? And what would be its time complexity?

from bisect import bisect

# Implements the decision version of subset sum.
# The subset sum problem: given a set and a number find a subset of the set which sums to the given number.
# Inputs: an ordered list of integers xs, and an integer n which is the target sum.
def subset_sum(xs, n):
    if n < sum(filter(lambda x: x < 0, xs)):
        return False
    if n > sum(filter(lambda x: x >= 0, xs)):
        return False
    xs = xs[:]
    u = {}
    def rec(i, n):
        if not (i, n) in u:
            u[i, n] = False
            k = bisect(sums[:i], n)
            while k > 0:
                k -= 1
                u[i, n] = u[i, n] or sums[k] == n
                u[i, n] = u[i, n] or rec(k, n - sums[k])
        return u[i, n]
    sums = xs
    return rec(len(sums), n)

It has been answered below that the above algorithm is exponential time.

That being so, I have a follow up question: Is the algorithm still exponential time if the rec sub-routine above is changed into the following?

def rec(i, n):
    if not (i, n) in u:
        u[i, n] = False
        k = bisect(sums[:i], n)
        k -= 1
        if k >= 0 and n >= sums[0]::
            u[i, n] = sums[k] == n or rec(k, n - sums[k]) or rec(k, n)
    return u[i, n]

The recurrence $T(i, n) = T(i - 1, n - 1) + log_2(i)$ is what I came up with for worst case running time. Maybe that's far off.
But from that it seems it is $|S|log(|S|)$.

New information:
I have been able to solve a problem instance involving a set of 8192 integers equal to the range (1, 9, ... 65537) and the target n = 65525 in one and a half minute on my laptop. The resulting list consists of 125 integers. That makes the algorithm (with the above changes applied) sub-exponential, certainly not $2^{|S|}$ . The time taken is for the search version which applies the decision version discussed here $|S|$ times.

Here is a link to the full source code of my test set-up:

http://codepad.org/5s5lkHAm


texts: Optimizing estimator of composed functions when function is known

texts:
I have a problem which I'm looking to see if there is literature on:

Consider three types of actors, a Director, Aggregator, and Follower. The Director talks to multiple Aggregators, the Aggregator talks to multiple Followers. The director gives simple commands to the Aggregator, who then can portion out the commands to each Follower as she sees fit.

The question then is, how can the Director know whether or not an Aggregator can complete a given request at time step T? T+1? If T is now, then this is relatively easy as the Aggregator can simply sum up the capabilities of each of the Followers and return it, saying "this is what I can do in total." The problem then is, if the Director is doing her own optimization problem in deciding how to direct two different Aggregators, given each command she must be able to predict how the Aggregator will react. I.e., what are the Aggregator's capabilities in time step T+1 given a direction D in time step T?

Due to the complexity of the Aggregator, I think it's likely best to create an estimator across the current state of the Aggregator (or all of their followers). Further, the Aggregator can give whatever knowledge it wants to the Director, though ideally this would be of constant size no matter the size of the set of Followers. This is therefor an optimization problem on the Aggregator's side for creating an optimal estimator, which is well studied.

What I want to know: Is there any literature about creating an estimator when you know the exact function you are estimating? So if I am the aggregator, how can I tell the Director, in a constant space for the amount of information I give no matter the number of followers, the information require to best predict I would react to a given direction?

Put another way: How can I create an optimal estimator in which I have full knowledge of the shape and composition of the functions I am estimating?

I can think of a number of places where this might occur, potentially in networking, data compression, etc., though I think I don't have the necessary vocabulary. I've tried searching through aggregation, optimization, estimation, forecasting, prediction, which a number of different combinations of keywords relating to these. There is a ton of generalized work on making estimators and predictors, though none which target the assumption that they already have perfect knowledge of that which they're estimating.


texts:
As we all know, Gaussian Noise follows Gaussian or Normal distribution, and that distribution follows a $BELL$ $CURVE$.

As we can see that most of the values are centered around the mean.

Now consider this image

When I add Gaussian noise to this image I get something like this

As we can see that the noise appears to be $UNIFORMLY$ $DISTRIBUTED$ throughout the image. There is no region where we can say that the noises concentrated around the mean value

So how can these be called Gaussian Noise?

The Code that I have used in octave is given below

 pkg load image;

I=imread('C:\Users\Hirak\Desktop\apple.jpg');
I=rgb2gray(I);

J = imnoise(I,'gaussian',0.02);
K = medfilt2(J);
imshow(J);


texts: Finite list induction principle and the tail eliminator

texts:
In Dybjer's Inductive Families the author present a method to derive an eliminator/induction principle for every inductive family of types.

In particular for the type of finite lists, namely
$$List' \colon (A \colon set) (n \colon N) set$$
we get the eliminator
$$\begin{align*}
listrec' \colon &(A \colon set)\\
& (C \colon (a \colon N)(c \colon List'_A n)set) \\
& (e_1 \colon C(0,nil'_A)\\
& (e_2 \colon (b_1  \colon N)(b_2 \colon A)(u \colon List'_A(b_1))(v \colon C(b_1,u))C(s(b_1),cons'_A(b_1,b_2,u)))\\
& (a \colon N) \\
& (c \colon List'_A(a)) \\
& C(a,c)\ .
\end{align*}$$

From what I get from this eliminator we should be able to provide any possible operation using finite lists.

Now my question is

  how do we get the classical destructor $$tail \colon (A \colon set)(n \colon N)(List'_A(s(n))) List'_A n$$
  that from any finite list gets its tail?

I am totally lost on how to approach this problem since the eliminator seems to be able to provide just function defined on the whole family $List'_A(n)$ and not on the sub-family $List'_A(s(n))$.

Thanks in advance.


texts: A relational algebra extended to model the full DML ("CRUD") domain

texts:
There are multiple references about the relational algebra for modeling queries (SELECT) but I have found very very little on the expanded algebra that would include concepts in all of DML such as INSERT, UPDATE, DELETE and maybe even MERGE, DECLARE, SET (as defined by MS SQL Server, whenever I must choose).  I'm looking for information about such an expanded algebra to help me reason about DML operations.

I assume that MS SQL Server, for example, must have some meta-domain model and/or type system that helps it validate SQL Scripts.  Here are a few of SQL SERVER 2008's SYS.MESSAGES (issued for scripted DML operations) that suggest to me violations of a type or domain-rule nature, not syntactic:

286 - The logical tables INSERTED and DELETED cannot be updated.
417 - TOP is not allowed in an UPDATE or DELETE statement against a partitioned view.
10729 - A nested INSERT, UPDATE, DELETE, or MERGE statement is not allowed in a SELECT statement that is not the immediate source of rows for an INSERT statement.
354 - The target '%.*ls' of the INSERT statement cannot be a view or common table expression when the FROM clause contains a nested INSERT, UPDATE, DELETE, or MERGE statement.
4005 - Cannot update columns from more than one underlying table in a single update call.

The database engine is compiling and analyzing the scripted commands it is given and emitting these messages in response to violations against its domain.

An engine executing this following statement isn't merely tacking on something trivial to the join of Table1 and Table2.  Beyond what it needed to SELECT, for the UPDATE it has to track more information throughout the statement such as the actual tables that ColB and ColC in the resulting join came from so that 1) it knows that they are from the same table (Error #4005) and 2) so it can actually write the results to somewhere permanent (not just a local transformation of the join):

UPDATE Table2
SET
    ColB = Table2.ColB + Table1.ColB,
    ColC = 3
FROM Table2
INNER JOIN Table1 ON Table2.ColA = Table1.ColA
WHERE Table1.ColX < 100

I've never used jOOQ, but the documentation suggests to me an uncommon level of sophistication/understanding compared to software with similar goals.  It apparently includes a fluent-style API for DML, and assuming that some of the library's value is in its ability to detect certain errors at compile-time, this suggests to me a decent domain model of DML.  Are jOOQ developers breaking ground with new and proprietary ways of understanding DML operations or is there published research into DML/CRUD types that they're implementing?  I'm so far overwhelmed trying to reverse-engineer the domain models from an implementation but I cannot find such a pure reference.

What is the domain model that is behind DML engines like SQL Server's script execution engine or softwares like the jOOQ library enabling them to understand/analyze DML scripts? For sql statements, relational algebra gives mathematical concepts of views, selections, projections, various joins, aggreggations, windowing, grouping, pivoting and each concept has type calculus that it dictates.  (Perhaps that a selection over a view yields a view of the same type with equal or fewer elements, that join takes two views and a join condition and yields a view of tupled elements, etc).  There are several implementations including Linq-To-SQL, Entity Framework which support (to varying degrees of competency) an alternate encoding and code translation of queries.  I assume that those softwares are grounded in the domain model of relational algebra.  But what would be the same basis for a library that supports full DML reasoning?

Thanks!


texts: Word factorization in $O(n^2 \log n)$ time

texts:
Given two strings $S_1, S_2$, we write $S_1S_2$ for their concatenation. Given a string $S$ and integer $k\geq 1$, we write $(S)^k = SS\cdots S$ for the concatenation of $k$ copies of $S$. Now given a string, we can use this notation to 'compress' it, i.e. $AABAAB$ may be written as $((A)^2 B)^2$. Let's call the weight of a compression the number of characters appearing in it, so the weight of $((A)^2 B^2)$ is two, and the weight of $(AB)^2 A$ (a compression of $ABABA$) is three (separate $A$s are counted separately).

Now consider the problem of computing the 'lightest' compression of a given string $S$ with $|S|=n$. After some thinking there is an obvious dynamic programming approach which runs in $O(n^3 \log n)$ or $O(n^3)$ depending on the exact approach.

However, I have been told this problem can be solved in $O(n^2 \log n)$ time, though I cannot find any sources on how to do this. Specifically, this problem was given in a recent programming contest (problem K here, last two pages). During the analysis an $O(n^3 \log n)$ algorithm was presented, and at the end the pseudo quadratic bound was mentioned (here at the four minute mark). Sadly the presenter only referred to 'a complicated word combinatorics lemma', so now I have come here to ask for the solution :-)


texts:
I have a homework problem that is perplexing me because the math is beyond what I have done, although we were told that it was unnecessary to solve this mathematically.  Just provide a close upper bound and justify it.

  Let
  $$f(n) = |\{w ∈ \{a, b\}^n : aa \notin w \}|. $$
  Provide an asymptotic upper bound on $f$ as $n\to\infty$.

So far:
$$
\begin{array}{c|c|c}
n & \text{strings} & \text{compared to } 2^n \\\hline
1 & 2 & 2^n - 0 \\
2 & 3 & 2^n - 1 \\
3 & 5 & 2^n - 3 \\
4 & 8 & 2^n - 8 \\
5 & 13 & 2^n - 18 \\
6 & 21 & 2^n - 43 \\
\end{array}
$$

The math that will give me an exact bound is beyond me.  Obviously $O(2^n)$ is an upper bound, though it is not particularly tight.

Any suggestions on what I should try?


texts: Are there more partially recursive functions than and recursive functions?

texts: Is the cardinality of the set of partially recursive functions greater than the cardinality of the set of recursive functions ?


texts: 3D Reconstruction from multiview calibrated camera

texts:
I have a calibrated camera whose intrinsics were calculated prior.
Suppose I have multi images with the same camera. Using the first two views.I have the

1) initial reconstruction using 8 point algorithm to find the fundamental matrix and then I computed the essential matrix as E = transpose(K)FK

2) camera matrices P1 and P2 where the origin is set to that of camera P1.

My question is, how would I add more views?. How to calculate the projection matrix for all the views?

Thanks in advance!

Note: I think this is a similar question but I can't understand the answer


texts: Error detection code supporting arithmetic

texts:
I am looking for error detection codes, which support addition in the encoded domain and are separate (a tuple of ($N$, $R(N)$), where $N$ denotes the functional value and $R(N)$ its redundancy).

So far I know residue codes where $R(N)$ equals $N \text{ mod } p$ and $p$ is a chosen constant. This scheme is closed under addition. Addition is performed by adding the functional part and the redundancy part mod $p$.

Can someone point me to other resources that describe coding schemes that are separate and support addition?

Thank's for the comments. Let me clarify my question. I want to have addition modulo $n$ where $n = 2^q$ with $q > 1$, e.g. $q = 32$, to support 32-bit integer addition.

Linear codes support a bitwise addition modulo 2, which is not suitable for my case.


texts: VAR autoincrement with constant space consumption for super large tables

texts:
Assume there was a database system that had a data type called VARINT or some variant that allowed instead of fixed-length INTs regardless of value, a 1 would only take 1 BIT (1), 2 would take 2 BITs (10), etc.

In this perfect world, a VARINT could be used to autoincrement a PRIMARY column.  However, there's still the issue of the field growing in size, so the "older" parts of this TABLE would be very fast, but the "younger" parts would get slower and slower.

What counting system could be used to hold the space consumed constant and small or at least grow at a much slower rate?


texts:
$\mathsf{EXP}\not\subseteq \mathsf{DTIME}(2^{n})$ and $\mathrm{CIRCUITSAT}\in \mathsf{DTIME}({2^{n}})$ holds and so why does $\mathsf{NP}\neq \mathsf{EXP}$ not hold while we know $\mathsf{NP}\subseteq \mathsf{DTIME}({2^{n}})\implies \mathsf{NP}\neq \mathsf{EXP}$?

Does $\mathrm{CIRCUITSAT}$ in any of $\mathsf{DTIME}(\frac{2^{n}}{n^c})$, $\mathsf{DTIME}({2^{\sqrt n}})$ or $\mathsf{DTIME}({2^{(\log n)^2}})$ $\implies \mathsf{NP}\neq \mathsf{EXP}$?


texts: Traveling Salesman Problem: Big O Complexity of Algorithm

texts:
I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused.

  The Traveling Salesman problem (TSP) is famous.  Given a list of
  cities and the distances in between them, the task is to find the
  shortest possible tour that starts at a city, visits each city
  exactly once and returns to a starting city. A particular tour can be
  described as list of all cities [c1,c2, c3, ... ,cn] ordered by the
  position in which they are visited with the assumption that you return
  from the last city to the start.This is a hard problem, that is, there
  is no known efficient solution for this problem and we are not
  expecting one any time soon. Your task is to analyze the following
  brute force approach to solving the problem:

  Consider the following algorithm for solving the TSP:

n = number of cities
m = n x n matrix of distances between cities
min = (infinity)
for all possible tours do:
    find the length of the tour
    if length < min:
         min = length
         store tour

  State the worst-case (big-O) complexity of this algorithm in terms of
  (number of cities)?You may assume that matrix lookup is one step
  O(1). For deriving big-O here, you need not count the if-statement or
  the for-loop conditional (i.e., testing to see when the for-loop is
  done), or any of the initializations at the start of the algorithm.

So far I know that there are 2 statements that will be executed after the if statement and I think there n! permutations of tours. Am I correct so far. How would I figure out the amounts of steps for "find the length of tour"?


texts: What does "higher order address bits" and "lower order address bits" mean?

texts:
"Assume a system with 4 GB virtual memory and 1 GB physical memory with 32 bit addresses. if the page size is 4 KB, How many bits will be allocated as the Higher Order Address bits and Lower Order Address bits to identify page numbers and corresponding words respectively?"
My question is, What does "higher order address bits" and "lower order address bits" mean in the above question?


texts: Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$

texts:
I'm reading a book at the moment about logic gates and Boolean simplification. There is a part which I can't seem to follow.

I can easily work out that $A \vee (\neg A \wedge B) \equiv A \vee B$ using a truth table as it's easy to see.

However, I can't seem to turn $A \vee (\neg A \wedge B)$ into $A \vee B$ using steps such as distributive / absorption etc.

Can someone talk me through the steps that you would take to simplify this?


texts: NP-complete reduction for a k-dumbbell graph

texts:
A k-dumbbell is a graph that consists of 2 cliques each of size k with one and only one edge between them. How do I show that finding if a graph is a k-dumbbell is NP-complete?

Proof it is in NP: Given the cliques of size k, I can verify if it they are the cliques of size k.

Proof of NP-hardness: If there is only one edge between them, how can I be sure that this is the edge I need for the reduction?

I'm trying to reduce from the k-clique problem as it seems to be the easiest choice.

I'm new to this so, if I'm wrong somewhere, please help me out !


texts: SQL - Are there row and column operations in row storage SQL database

texts:
I have a very fundamental question.

When one says data is stored in a table, I understand what row-store is,  but are all values in a table stored in contiguous locations? If we are trying to join two tables, are the values in the two tables located in two separate contiguous locations and when we join them, they become one new contiguous location with the required values. Where are the outputs of a sub query held? Is that a separate location too? How is data 'parsed' in a row store?


texts: Bin-packing satisfiability rather than minimization

texts:
Here's a problem I need to solve that's clearly related to the standard bin-packing problem, but I'm not sure how to approach it.

Suppose you have some finite set of bins $B$, and each $b_i \in B$ has some integer capacity $\mathit{cap}(b_i)$. You also have some set of items $L$ where each item $l_j \in L$ has some integer volume $vol(l_j)$. The question is, is there some way of assigning each item in $L$ to some bin in $B$ where no bin is overful, i.e. to find any total mapping $M : L \rightarrow B$ such that $\forall b_i \in B$, the sum of all $vol(l_j)$ with $M(l_j) = b_i$ is less than $cap(b_i)$.

The notable differences from the classic bin-packing problem are: first, we have only a finite set of bins, not an infinite number of bins to draw from. Second, we have no notion of cost; we only want to find some total mapping or determine that no such mapping exists. Third, bins are not homogeneous; we might have one bin with capacity 5 and another with capacity 10.

I'm not sure how to approach this problem or whether standard bin-packing approaches can be adapted to work with it. What is a good algorithm for answering the question?

For extra credit, there are a few extra bells and whistles that I would like to add, though these are optional:

Add a constraint that some bins can only contain a maximum number of items as well as having a volume limit
Some bins may have a minimum per item volume as well as a maximum volume; i.e. you don't have to put an item in the bin, but if you that item must have at least a given volume


texts: Show that LOOP is reducible to Complement of Halting problem

texts:
LOOP = {<M,w1,w2,w3>: M is a Turing machine that doesn't halt on at least 2 of the wi}
HPC = {<M,w> : M is a Turing machine that doesn't halt on w}
Show that LOOP is polynomial time Turing reducible to HPC
I am not sure how to begin solving this kind of problem.
Also the question I am trying to solve brings up the definition of A is polynomial reducible
to B if there is a B-oracle poly time Turing M such that M(x) accepts x iff x is in A.
Any hints or pointers on this ?
My thoughts :
What I understand by reducibility here is that If I have a Turing machine for HPC
Then I can use this turing machine to determine if <M,w1,w2,w3> is in LOOP
And same the other way If I have a turing machine for LOOP then I can use it
as a determiner for HPC. Is this a correct way to think about it?
This way it becomes simple and probably easier to prove. But not sure if it
is same as the question that is being asked


texts: Why substituting the search part in INSERTION SORT doesnt yield a running time of $\Theta(nlgn)$

texts:
$$
\Theta - Tight \ asymptotic \ bound
$$

If we change lines $5-7$ in Insertion sort

With BINARY-SEARCH(A,p,r,v)

Why don't we get a running time of $\Theta(n\lg n)$ as we go through the array $\Theta(n)$ and then do a binary search $\Theta(\lg n)$?


texts: Showing that Hadamard is its own inverse

texts:
Im trying to work out that a Hadamard transform H (a unitary matrix) is its own inverse by applying it twice to an arbitrary state $|x⟩$:

$$H|x⟩ = \frac{1}{\sqrt{2^n}}\sum_{y \in \{0,1\}^n}(-1)^{x \cdot y}|y⟩\,.$$

Then
\begin{align*}
H\left(\frac{1}{\sqrt{2^n}}\sum_{y \in \{0,1\}^n}(-1)^{x \cdot y}|y⟩\right)
&= \frac{1}{2^n}\sum_{y \in \{0,1\}^n} (-1)^{x \cdot y}\sum_{z \in \{0,1\}^n}(-1)^{y \cdot z}|z⟩\\
&=\frac{1}{2^n}\sum_{y \in \{0,1\}^n}\sum_{z \in \{0,1\}^n} (-1)^{x \cdot y}(-1)^{y \cdot z}|z⟩\\
&= \frac{1}{2^n}\sum_{y \in \{0,1\}^n}\sum_{z \in \{0,1\}^n}(-1)^{y \cdot (x + z)}|z⟩\,.
\end{align*}

But I don't know how to get from here to $|x⟩$ again.

I know that $HH^* = I$, but I want to show it this way, to understand what is happening.


texts: Algorithms for elementary operations using other elementary operators

texts:
The question asks to provide an algorithm to compute

$(i)$ The product of $n$-bit numbers using
reciprocation operation and addition operation but not using multiplication
and squaring.

$(ii)$ The square of a polynomial of degree $n−1$ using only
reciprocation and addition operation but not using multiplication
and squaring.

$(iii)$ The product of two $n − 1$ degree
polynomials using only squaring and addition operations but not using multiplication and reciprocation operations

All the operations stated above are on $n$-bit integers.

My try: The question asks to express some operator in terms of other elementary operators , so for eg. for (i) I tried writing $(\frac{1}{A} + \frac{1}{B})^{-1} = \frac{AB}{A+B}$, but to get $AB$,  I still have to multiply LHS by $A + B$. I think I can do $(ii)$ if I do $(i)$ as a polynomial is similar to a n-bit integer if you consider the bits as $(a_ix^i)$. I don't have an idea for $(iii)$ yet.


texts: Sorting an array of length n with k distinct elements in O(kn)

texts:
I have an array of the size N with K distinct elements.We don't know what the K is. I would like to sort this array in O(kn).
I have found this answer and I would like to understand what does exactly @Aidan Connelly was talking about(I'm  unable to comment on this answer)
I'm getting the array lets say it's (-50, 234567, -50, 2, 2345670, -50)
after sorting it I wanna get (-50, -50, -50, 2, 234567, 2345670)
let's say I have the code for quicksort-and I want to get only the unique values.
what should I do?go over the array and count for each element how many times it appears?and then make a new array out of it and perform the sort on it?and then make a new array that will contain all the elements?sound like I would be just going over and over the array..it seams to me that it won't be O(kn) anymore.
Is there a better way to get only the unique values and count how many times they appear and make a sorted array with all the elements?
***In addition K does not have a fixed upper bound unlike the previous question


texts: Maximum node splits in B-tree in terms of insertions and branching order

texts: Is there any algorithm to calculate maximum number of node splits that can occur in given number of insertions and highest branching order? Lets say I want to insert 10 elements to an empty B-tree with highest branching order of 3. Is there way to calculate the maximum number of splits that will occur?


texts: What are some differences between regex (FSM) in computer science with regex in programming?

texts:
Computer science has automata theory with lessons on regular expressions and FSM. How are these different from regex engines used in programming such as C++, Perl, PHP etc.?

I would like to know some differences i.e. stuff that can only be done with regexps in programming but cannot be done in formal regexps in computer science.

I heard there are a lot are differences but what are some major ones? Let's take Perl Compatible Regular Expressions (PCRE) or Boost.Regex for comparsion.


texts: Is it possible to reduce functional equations to SAT?

texts:
The problem of finding a solution for functional equations can be defined as:

  Let A0, A1, A2... An, B0, B1, B2... Bn, X be terms of the lambda calculus, all terms known, except for X, unknown. Given a set of N equations in the form X An -> Bn (that is, X applied to An strongly normalizes to Bn), what is an algorithm that finds X for arbitrary A, B?

Since there is no published solution for this problem on literature (as far as I known), is there any way to reduce that problem to SAT?


texts: Why guess $\Theta(n^2)$ for the substitution method of worst-case partitioning

texts:
In the book

  Introduction to Algorithms (3th edition) chapter 7

the recurrence of the running time of quicksorts partitioning is given by $$T(n) = T(n-1) + \Theta(n)$$
as the worst-case happens when the partitioning has one subproblem with $n-1$ elements and one with $0$ elements.

Now, they they guess $T(n)=\Theta(n^2)$ for the substitution method. I don't  understand this, why choose $\Theta(n^2)$? I personally would have chosen $\Theta(n)$, which is wrong.


texts: Halting Problem without self-reference: why does this argument not suffice (or does it)?

texts:
I'm trying to find a way to explain the idea of the Halting Problem proof in as accessible a manner as possible (to undergrad CS students). The simplest argument I have found is this one; this is precisely the style of treatment I am aiming for. However, the self-reference (in particular, checking if a program halts on itself) is not the most didactic.

What I'm wondering, as a proof sketch, is why we could not simplify even further and say: if we assume a program H(P,I) for the Halting Problem that halts with true if P(I) halts, and halts with false otherwise, then we could create a program of the form:

def Q(J):
  if H(Q,J) then loop forever
  else halt

... which is a valid program if and only if the Halting Problem is a valid program.  We can then ask: what should H(Q,J) return on any arbitrary value for J? We see a contradiction in both possibilities, and we conclude that since the existence of H allows us to construct the contradictory program Q, thus a program of the form H cannot exist.

There is still some self-reference here in that the program Q checks whether or not it halts on the current input (and does the opposite), but for me, this seems much more intuitive than setting up a situation where we need a call of the form P(P) or H(P,P), etc. However, I have not seen this simpler argument used, and I think it would have been were it valid. Hence my questions are:

Is the above argument sufficient as a proof (sketch) of the Halting Problem?

If so, why do so many arguments go with a confusing step of the form P(P) or H(P,P)? (Is it just to remove the unimportant "input" from the equation?)
If not, what's missing?

There are a variety of related questions on this topic, such as:

Halting problem without self-reference
Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I also found mention of the proof based on Berry's paradox, which is quite appealing. Still, I have not yet managed to convince myself whether or not the specific argument above works (even if just for my own understanding; I feel I am perhaps missing something stupid and would like to know what it is).


texts: Normal Distribution pattern in Java Array of doubles

texts:
Given ordered array of float numbers, Check if array represents Normal Distribution.

I wrote algo to find triangular distribution as follows:

1. Find index "i" in array such that sum {A[0] + ...A[i-1]} almost equal to sum {A[i] + ... + A[n-1]}
2. Check if A[i....i-1] is almost increasing sequence
3. Check if A[i ... n -1] is almost decreasing sequence

I need to upgrade this to normal distribution ? Is there good Java lib that identifies Normal Distribution pattern Or is there well known algorithm to solve this problem


texts: findining the smallest sum of squared lengths of the intervals I_{k}

texts:
Given a set S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{i} \in Z$ . and a K and it is  $Z^{+}$ .  The goal is to ﬁnd k intervals
$I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one of the
intervals $I_{j}$ and so that the sum of the squared lengths of the
intervals $I_{k}$ is as small as possible. For instance, S = {1, 3, 6}
and K = 2, the best outcome is $I_{1}$ = [1, 3], $I_{2}$ = [6, 6], and
the sum of squares of the lengths is 4.
We can approach our algorithm as: First of all, we sort S and let S =
{ $x_{1}$, $x_{2}$, . . . , $x_{n}$} where  $x_{1}$<$x_{2}$<, . . . ,
<$x_{n}$. Then we can use dynamic programming. We let L[i, m] be the
shortest sum of squared lengths of m intervals that cover all of
$x_{1}$, . . . , $x_{i}$. Notice that L[1, m] = 0 for all 1 ≤ m ≤ k
and L[i, 1] = ($x_{i}$ − $x_{1})^2$ for 1 ≤ i ≤ n. If we have a cover
of $x_{1}$, . . . , $x_{i}$, suppose the interval that covers
$x_{i}$ also covers all points $x_{j}$ , $x_{j+1}$, . . . , $x_{i}$.
Then, the sum of the squared lengths is at least ($x_{i}$ − $x_{j}$
$)^2$ + L[i − 1, m − 1]. Therefore, the minimum such value is actually
obtainable.

How can we know for sure "that L[1, m] = 0 for all 1 ≤ m ≤ k and L[i, 1] = $(x_{i} − x_{1})^2$ for 1 ≤ i ≤ n" and ?
Seem like we need to have a 2D-array? How can I visualize this solution better?
Here is what draw:

How can we fill the 2D array with ($x_{i}$ − $x_{j}$ $)^2$ + L[i − 1, m − 1] ?


texts: What does instantiating existential variables with out of scope variable imply?

texts:
I have following unfinished proof of a lemma:

Goal forall (P : Type -> Prop) (Q : Prop),
  ((forall x, (P x)) -> Q) -> (exists x, P x -> Q).
Proof.
  intros.
  eapply ex_intro. intros. apply H. intros. eapply H0.

The problem is the last eapply failed, with the message

Error:
In environment
P : Type -> Prop
Q : Prop
H : (forall x : Type, P x) -> Q
H0 : P ?x
x : Type
Unable to unify "?x" with "x" (cannot instantiate "?x" because "x" is not in
its scope: available
arguments are "P" "Q" "H").

The proof steps themselves look very phishy already. The proof constructs an existential variables to sit in place of $x$ in the second half, and then tries to instantiate it using the $x$ obtained as premise after applying the hypothesis (forall x, (P x)) -> Q. The proof steps look cyclic proof to me.

What in general does this message imply? What types of logical mistake does this message indicate here?

There is a recent github issue from Coq actually indicates that instantiating evars outside of scope CAN prove falsehood, except that it's blocked by QED.

https://github.com/coq/coq/issues/8215


texts:
Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the complete set of push down automata, with nothing more powerful.

First question: Can a language exist that expresses up to the power of finite state machines but nothing higher?

Next. Working at the power of Turing machines we have the lambda calculus which with a little bit of sugar is a nice programming language. In addition there are weaker forms of the lambda calculus that are not Turing complete such as the simply typed lambda calculus.

Second question: What calculi exist that cannot express problems above finite state machines, but a programming language could be built on top of. Kind of like the lambda calculus.

Grammars can be restricted to only allow regular languages. This of course does not change the fact that context free grammars can represent regular languages.

Third question: Even though context free grammars allow the expression regular languages, do the methods used to check if a grammar is regular allow the expression of all regular languages? Such as those talked about in "https://en.wikipedia.org/wiki/Regular_grammar".

These questions are all directly related. Pardon how convoluted this is.


texts: Is finding cache size possible with information given?

texts:
An 8-way set-associative cache is used in a computer in which the real memory size is 222 bytes. The line size is 16 bytes, and there are 26 lines per set.
A) What is the size of the cache in bytes?

What I (think) I understand:
Cache line and cache block are synonymous.
The textbook says that an n-way set-associative cache has n blocks(lines) per set. That conflicts with the next sentence that says "there are 26 lines per set." Is this problem incorrect or are my assumptions wrong?


texts: Are there pseudorandom number generators (PRNG) with no finite period?

texts:
The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period?

For this question it is not necessary that it be practical or used in real-world implementations.


texts: Show that problem is PSPACE-complete - path in directed graph

texts:
I have a following problem:
Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch circuit on this input and get result $0$.

Problem:
Is there exists path from vertex $k$ to vertex $l$ ?

I can reduce arbitrary problem from $PSPACE$ to above problem. The only thing that I can't do is showing that problem given in exercies belongs to PSPACE.

Tell me please, if my reasoning is correct (it seems to be too simple):
We know that $PSPACE = NPSPACE$. So we can give non-determinitic algorithm. Algorithm can guess sequentially verticles and check (using circuit) if there exists path).
I can say more, let algorithm guess ansewr (0 or 1).

Can you help me ?


texts: Hardness of problem related to number of subsets that satisfy a particular property

texts:
I have the following algorithmic problem.  I am given a set of elements.  Each element has a set of properties.  For example:

A: has properties p1, p2, p4
B: has properties p2, p4
C: has properties p2, p1

The task is to find the number of subsets of elements, where the union of the properties of the elements in the subset are equal to some predefined set.

For example if the predefined set is:

{p2}, then the answer is 0, because there are no subsets with a union of {p2}
{p1, p2, p4}, then the answer is 5, because we can take {A}, {A, B}, {A, C}, {B, C}, {A, B, C}

This problem seems like it might be hard (e.g., NP-hard), but I can not find anything similar in this list of NP-complete problems.  I do realize  that this is only small subset of NP complete problems.

Is there an efficient algorithm for this problem?  Or, is it NP-hard, and if so, how can we prove that?


texts: Is the language $L=\{a^nb^mc^k | k \ge max (m,n) \}$ CF

texts:
I'm trying to prove that the language $L=\{a^nb^mc^k | k ≥ max (m,n) \}$ is not CF. I consider the word $\alpha = a^pb^pc^p = uvxyz$ and i break the proof to the following cases :

1) if $vxy = a^l, b^l$ or $a^kb^l$ for some $k,l \le p$ i pump the word up, so
$a^l+s, b^l+s, s > 0 : l+s<p => \alpha \notin L$

2) if $vxy$ consists any $c$ then it can't consist any $a$s so if we pump down then $c^u, u = p - l, l > 0 => N_{c} < N_{a} => \alpha \notin L$.

But i keep thinking relying on my intuition that L is CF, because L build on the rule : if we print a then we print c, if we print b we print c, or we just print c. Looks like CF.
My question is is my proof wrong or my intuition?


texts:
Given $G(V,E)$ and $k$.
Is there a clique with size $k$?

Given set $X = \{x_1,x_2,\dots,x_n \}$, and collection $A = \{A_1,A_2,...,A_n\}$ of sub-sets of $X$ and $k$.
Are there are $k$ different elements in $A$, that every two of them has intersection that isn't empty? For example $A_1 = \{ x_1,x_2,x_3 \}$, $A_2 = \{x_4,x_5,x_1 \}$ so their intersection is $x_1$ and its valid, but it should be applied for every two $A_i,A_j$ in $A$.

Prove: That unnamed problem (which surely has a name) is NP-Hard.

The reduction is..

$X=E$, and every $A_i$ in $A$ is composed of edges that are connected to vertex $v_i$.

I can't understand the reduction, can someone explain why it works please?