texts: The C3 linearization algorithm for method resolution in multiple inheritance OO languages: Looking for a justification for some implementation detail

texts:
According to this description of Python's method resolution order (mro), a.k.a. C3 linearization, the algorithm can be described recursively as follows:

L(O) = <O>
L(C) = <C> + merge(L(B1),..., L(Bn), <B1,...,Bn>)

where

O is the class from which every class inherits.
C is a class that inherits directly from B1, ..., Bn, in this order.
< and > are list delimiters.
+ is the list-concatenation operator.
merge merges its list arguments into a single list, in a manner to be described below.

The above can be rephrased in words (quoted from the above Python document):

  the linearization of C is the sum of C plus the merge of the linearizations of the parents and the list of the parents.

The merge algorithm is described as follows (essentially quoted from the Python document, but slightly reworded):

  Consider the head of the first list, i.e L(B1)[0]: if it is a good head, i.e. if it is not in the proper tail of any of the other lists, add it to the linearization of C, and remove it from all the lists in the merge. Otherwise, consider the head of the next list, etc. Repeat until no more classes, or no good heads. In the latter case, it is impossible to construct the merge.

The following example is given as an illustration. Suppose A inherits directly from B and C, in this order, and suppose that the linearizations of B and C are

L(B) = <B, D, E, O>
L(C) = <C, D, F, O>

Then A's linearization is

L(A) = <A> + merge(<B,D,E,O>, <C,D,F,O>, <B,C>)
     = <A, B> + merge(<D,E,O>, <C,D,F,O>, <C>)
     = <A, B, C> + merge(<D,E,O>, <D,F,O>)
     = <A, B, C, D> + merge(<E,O>, <F,O>)
     = <A, B, C, D, E> + merge(<O>, <F,O>)
     = <A, B, C, D, E, F> + merge(<O>, <O>)
     = <A, B, C, D, E, F, O>

My question is: in terms of the original description of the algorithm, what purpose does it serve to give the list <B1,...,Bn> of direct parents as an argument to merge? Will the algorithm produce different results if this argument is omitted?


texts: Why does Skillicorn's Taxonomy allow us to design 30 models?

texts:
In Skillcorn, David B, "A Taxonomy for Computer Architectures", IEEE Computer, 21(11):46-57, Nov 1988, a taxonomy of multiprocessor architectures is described.

My teacher said that Skillikorn's Taxonomy allows us to design 30 different models, but only 7(9?) of them are reasonable.

What did he mean by that?


texts:
Given a simple undirected connected graph $G$, I want to find a min-cut
of $G$ using a randomized algorithm.
My attempt was to select a random edge in $G$ and reduce that edge to a
single vertex.  And recursively do it until the number of vertices is at
most 2.
The number of edges present (in the resulting multi-graph) will be the
min-cut.  This is the standard algorithm I found at many places.
Will this lead to the exact number of min-cut and how can I extract the
vertices on each side of the cut?


texts: What's the best bucket fill algorithm in terms of efficiency?

texts:
I am looking for an algorithm that fills a given region of connected particular nodes in minimum time. I have tried using flood flow algorithm but it's too slow and inefficient for large array, it checks each pixel more than once.  Is there any algorithm that is more efficient than flood flow algorithm.

If that helps, i want to implement this algorithm for a paint filling app


texts: DFA which visit a specific state at least once

texts:
Given a DFA M that satisfies language A, how do I modify M such that a new language B consisting of all strings that are accepted by M and cause M to enter a specific state r at least once are satisfied by the modified DFA?

I try to remember whether state r is visited or not. But as I known, unlike turing machine, DFA does not have any memory.


texts: residual network for a network with lower and upper bounds?

texts:
How does one construct the residual network in such a case?

The formula is for edge $(u, v)$  is

$$rf(u,v) = (c_{\mathrm{upper}}(u,v) - f(u,v)) + (f(v,u) - c_{\mathrm{lower}}(v, u))\,,$$

where $rf(u, v)$ is the residual flow on the edge $(u, v)$, $c_{\mathrm{upper}}$ and $c_{\mathrm{lower}}$ are capacities on the edge and $f$ is the flow.

If, say, my edge $(u, v)$ has capacities $[3, 25]$ and a flow $f(u,v)=1$, then what are $rf(u, v)$ and $rf(v, u)$?

what is $c_{\mathrm{lower}}(v, u)$?

Thank you.


texts: What algorithm should I use to find a minimal tree that include certain nodes within a graph?

texts: Assume we need to include a certain set of nodes in the tree within the whole graph, the generated tree can contain nodes other than the specified set of nodes. We also need the number of edges (or the total amount of edge weight) included in the tree is minimum.


texts: Binary search uneven split number of queries?

texts: For even split binary search (repeated halving) number of queries is log with base 2. According to Skiena's Algorithm Design Manual, if the split in binary search is by ratio 1/3:2/3 instead of 1/2:1/2, then number of queries is log with base 3/2. Why is this so? Would someone please help me get an intuitive understanding of why this works?


texts: Proving inequalities related to Dijkstra's algorithm

texts:
Define $spdist(s,t)$ as the distance of the shortest path from vertex $s$ to $t$.

Define $IN(v)$ as the set of in-neighbors of $v$.

Define $w(u,v)$ as the weight of the edge $(u,v)$.

I am asked to prove the following two inequalities to gain the correctness of Dijkstra's algorithm:

$$spdist(s,v)\leq min_{u \in IN(v)} \{spdist(s,u)+w(u,v)\}$$

and

$$spdist(s,v)\geq min_{u \in IN(v)} \{spdist(s,u)+w(u,v)\}$$

For the ≤ direction, it is quite obvious. Since we must go through either one of the edge $(u,v)$ to reach $v$, $spdist(s,v)$ is by definition smaller or equal to the RHS.

However, I am having trouble proving the ≥ direction. May I have some intuition of tips on how to prove the ≥ direction?

Thanks!


texts: Can two equal classes be separated wrt an oracle?

texts:
Is it known if there are two classes of languages $A$ and $B$ such that:

$A$ and $B$ are defined wrt the exact same type of machine (e.g. 1-tape Deterministic Turing Machines, 2-tape Deterministic Turing Machines, 1-tape Nondeterministic Turing Machines, etc);
neither $A$ or $B$ are defined wrt a restriction on space usage;
$A = B$;
there is an oracle $O$ for which $A^O \neq B^O$?


texts:
There are several periodic tasks (Period, Execution time),

e.g.:

A = (20, 9)
B = (12, 4)
C = (4, X)

What methods/tests can be used for finding the maximum execution time X for which the task set will be schedulable by Rate Monotonic.


texts:
It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item happens to land in the same bucket and the lookup time becomes linear ($\Theta(n)$).

Are there conditions on the data that can make hash table lookup truly $O(1)$? Is that only on average, or can a hash table have $O(1)$ worst case lookup?

Note: I'm coming from a programmer's perspective here; when I store data in a hash table, it's almost always strings or some composite data structures, and the data changes during the lifetime of the hash table. So while I appreciate answers about perfect hashes, they're cute but anecdotal and not practical from my point of view.

P.S. Follow-up: For what kind of data are hash table operations O(1)?


texts: Can the maximum single sell profit by divide and conquer be O(n)?

texts:
The single sell profit problem is:

Given a list of prices on each day, find the maximum profit that could have been made by buying on one of the days and selling on a later day.

There is a solution with a single scan that is easy to implement and runs in $O(n)$. This question is not about that. It's about the divide-and-conquer solution.
I've read twice that the divide-and-conquer solution to this problem  is $O(n \log n)$: once when this problem is discussed in Elements of Programming Interviews in Python by Aziz, Lee and Prakash (it's problem 5.6), and once in these PDF lecture notes by Kevin Zatloukal of UW (page 23). Both these sources say the divide and conquer solution is slower than a simple scan.
Neither source presents an implementation (it's not the best approach, so fair enough), and the descriptions are a little terse, but reading between the lines they seem to describe a simple divide-and-conquer down to a base case of a single element, whether the merged result is the maximum of the best trade in the two subproblems and the maximum price in the right minus the maximum price in the left.
Here's that in Python
def best_trade(prices: List[int]) -> int:
    if len(prices) < 2:
        return 0
    else:
        best_left = best_trade_2(prices[: len(prices) // 2])
        best_right = best_trade_2(prices[len(prices) // 2 :])
        return max(
            best_left,
            best_right,
            max(prices[len(prices) // 2 :]) - min(prices[: len(prices) // 2]),
        )

The running time of this for a problem of size $n$, $T(n) = 2 T(n/2) + O(n)$ because the max/min call outside the recursion are O(n). By the Master Method analysis this means the algorithm has time complexity $O(n \log n)$ ($a = 2$, $b = 2$, $d = 1$ so we're in the $a = b^d$ case where the complexity is $O(n^d \log n)$).
My question is: can this problem be solved by divide-and-conquer in $O(n)$?


texts: I understand that the general problem of program equivalence is undecidable, but I'm wondering what approaches exist to tackle the problem? I am familiar with Hoare-style verification, but are there any other frameworks for proving program equivalence?


texts:
Using the following relations:

consultant(id,Name,Skill)

CustomerCompany(Id,name Address, Phone, Email, WebAddr,Market)

project(id,StartDate,EndDate,ConsultantID,CustomerId,Days)

Invoice(id,Date,Customer,Amount,Status)

Im trying to work out the following scenario using SQL and Relational algebra

Find the names of the consultants and the names of customers, where the consultant has worked for the customer, and the customer received an invoice in the range of GBP 100k to 200k

Using SQL i have:

Select I.amount, C.name
from CustomerCompany C, Invoice I
where I.Customer= C.id and > all
(
  select C.name, Con.Name
  from CustomerCompany, Con Consultant
  where i.amount between 100 and 200
 );

Relational algebra:

amount = σ(Invoice, amount>=100 and amount<=200)

joininv= Ⓧ(amount, Customer, CustomerCompany, id)

joincon Ⓧ(joiniv, Consultant id, Project, ConsultantID)

π =(joincon, name, Name)

I was wondering if write or wrong?

Thanks for any help!


texts:
I have the following CFG,

$S \rightarrow CB$
$C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$
$B \rightarrow AB \text{ }|\text{ } \varepsilon$
$A \rightarrow a\text{ }|\text{ }b$

This is the CFG for the following language:

$$L= \left\{w \text{#} x\mid w^R \text{ is a substring of }\ x \text{, where }  x,w\in \{a, b\}^*\right \}$$

I have a problem with constructing PDA for this CFG.

My attempt

My idea was to store characters in stack until "#" character, then as soon as the sequence of reversed characters go, pop from the stack. If at the end of input stack is empty, then we are done.

The problem is that for the following string, for example:

abbaa#aabbbbbbb(aabba)bbbbbb

when we read characters after "#", PDA will pop 4 characters, the it will see that the sequence is not valid and proceed with input. How can I return these 4 characters back so that I can check sequence again because I need full stack to proceed with accepted reversed substring that I have showed in brackets?


texts: Why does my code work: bijecting binary trees to Dyck paths

texts:
The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan numbers. Another set of objects that follows the Catalan numbers is the number of binary search trees with $n$ nodes.
This suggests we can biject binary trees to Dyck paths (see here). We get a hint on how to do the bijection based on why the two objects satisfy the same recurrence (for Catalan numbers):
$$C_{n+1} = \sum\limits_{j=0}^{n}C_{j}C_{n-j}$$
Binary trees satisfy it because you designate one node as the root, then create a binary tree on its left (with $j$ nodes) and another one on its right. Dyck paths satisfy it by conditioning on the first time the path hits the y=0 line (which is what $j$ in the equation above represents). So we first take a mandatory step up, then we make a path of $2j$ steps that doesn't cross the $y=1$ line; then we go down one step to touch $y=0$ for the first time, and finally we make another path of $2(n-j)$ steps that doesn't cross the $y=0$ line.
This suggests we might be able to construct a Dyck path given a binary search tree (with node-keys labelled from $1$ to $n$ and there is just one way to assign them, see here) recursively, starting at the root. When we go to the left node of the tree, we need to consider the sub-path one level above the current level (where we start at level-0) and when we go to the right, we simply stay at the same level. Since the key of the node we're processing tells us where the path first struck the current level from the start, we know that it 2 times the number of steps representing the key from the start must be a step down.
The Python code below demonstrates this idea and works (tested it extensively). If you don't use python, the idea is very simple; I just set the path array to all 1's ("up" steps) and the recurse on the tree, inserting -1's ("down" steps) based on the keys on the tree nodes.
import numpy as np

class TreeToDyck():
  def __init__(self, tree_node, n):
    # Initially create an array of 2n ones. All steps are set to "up".
    self.path = np.ones(2*n)
    # Now insert downs at appropriate places.
    self.tree_to_dyck(tree_node, 1)

  def tree_to_dyck(self, tree_node, start):
    if tree_node is None:
        return
    # Go down. Bear in mind the "path" array is 0-indexed.
    self.path[start+2*tree_node.key-2] = -1
    self.tree_to_dyck(tree_node.left, start+1)
    self.tree_to_dyck(tree_node.right, start)

Now, the thing to note is that the key of the node we're at gives us many hints about the path. But, I ignore most of them and simply insert a "down" step. I start with all steps in the path array set to go up. Then, based on the keys of the tree nodes, I insert down steps.
Surprisingly, this is enough. Which means the following two statements must be true:

The down steps will never collide with each other. So, we'll never insert a "down" step at the same location twice. This will ensure we insert $n$ down steps, as the path must contain.
The last step in the Dyck path is always a "down" step. So, we will always end up inserting a "down" at the very last position in the array no matter the tree.

I want help proving the above two statements. And if there is any other requirement needed to prove that the algorithm will work.


texts: Determine aproximation factor in a greedy algorithm

texts:
Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences.
  We want to choose a menu such that we minimize the cost and such that at least one preference for each guest is satisfied.

I implemented an easy greedy algorithm that orders each element in respect of their $\frac{\text{# of people satisfied}}{\text{cost}}$ for example if element "a" satisfies 3 people if choose and has a cost of 10, its ratio would be $3/10$. I chose each element in a non-increasing order. Until i run out of people to satisfy.

How do i find the approximation factor for this algorithm? I think it should be around 2 since it's very similar to a greedy approach to knapsack problem, but i have no clue on how to demonstrate it.


texts:
Given two sets $A = \{a_1, a_2, \dots, a_n\}$ and $B = \{b_1, b_2, \dots, b_n\}$, both consist of positive numbers, this problem is to find a subset $S$ in $\{1, 2, \dots, n\}$ to maximize
$$
\left(\sum_{i \in S} a_i\right)\left(\sum_{i \notin S} b_i\right)
$$

A naive solution is to iterate over the powerset of $\{1, 2, \dots ,n\}$ and find the maximum value, which is $O(n2^n)$. How to use dynamic programming to solve this?

Any comments would be appreciated.


texts:
I encountered an interesting  problem based on tree-data-structure.

We are given a tree which has N nodes, with 1≤N≤105.
Time starts from second 1 and it continues for q seconds.
At each second, the value of each internal node is transferred to all of its child nodes. This happens with all the nodes, except leaf nodes.
Sometimes, at a given time p (seconds), we are asked to return the current value of node x.

There is this O(logN) approach: just find the pth ancestor of the given node x, and output its value.
A harder version of the same problem

Sometimes, at a given time p (seconds), we are asked to return the current value of node x, or we are said to update the value of node x to y.

How to solve this problem for q queries (seconds) efficiently, where 1≤q≤105.
Example
Input
N=5, q=8
Edges of the tree:-
4 3
3 1
5 2
1 2

Values of nodes 1 to 5:-
1 10 4 9 4

Queries:-

1st second:- Add(1,6). Add the value 6 to node 1.
2nd second:- What is the current value of node 3? (?,3)
3rd second:- Add(3,5)
4th second:- (?,3)
5th second:- Add(2,2)
6th second:- Add(5,10)
7th second:- (?,5)
8th second:- (?,4)

Expected Output

6
0
33
25

Explanation

1st second: 6,1,1,13,14 (Values of all nodes)
2nd second: 0,6,6,14,15
3rd second: 0,0,5,20,21
4th second: 0,0,0,25,21
5th second: 0,2,0,25,21
6th second:  0,0,0,25,33
7th second: 0,0,0,25,33
8th second: 0,0,0,25,33

How to answer the queries efficiently?


texts:
I'm a novice to the topic of provability so bear with me...

During a discussion with a friend, the question came up whether it could be possible that proving that $NP \neq P$ (or $NP = P$) is an unprovable statement. My friend opposed that, if indeed it was unprovable, then this would imply that there cannot be a polynomial time algorithm for NP-hard problems (as the existence of such proves the statement), thus implying $NP \neq P$. This seems to be imply that the statement cannot be unprovable or am I missing something?


texts: Learning Specific Topics In Machine Learning

texts:
I am a beginner in machine learning and I already have a good linear algebra/calculus background.

I am interested in being able to eventually understand and implement convolutional neural networks, feature-based classifiers, and boosting algorithms. Where should I start, and what steps should I take to reach my goal?

Thanks in advance.


texts:
I recently saw this question somewhere and thought a lot on it but was unable to find an efficient solution for it.
Asked on Stack Overflow but got no solution there.

The Problem is as follows -

Given a tree with $X$ number of nodes we need to assign values to each node.

You  are also given two arrays A[] and B[] each of size $X$. Assignment to nodes should be done in such a manner that if you assign number $N$ to some node $i$ then $N$ should lie between A[i] and B[i].

Also if two nodes are connected with an edge then they both should be assigned values that are co-prime (GCD = 1). For each node you need to find the sum of all possible values assigned to that node in every possible tree assignment that can be done.

You need to output $X$ numbers, one for each node.

Upper limit on $X$ is $50$.
Upper limit on A[i] and B[i] is $100000$.

Can somebody suggest an efficient solution to this problem?


texts: Minimize edges of a directed unweighted graph

texts:
I need to find an algorithm to find a sub-graph $G'=(V, E')$ of a directed unweighted graph $G = (V, E)$ where for all $(u, v)\in E$ there exists a path in $G'$ from $u$ to $v$ and the size of $E'$ is minimal.

As an example, $(1, 2) (2, 3) (1, 3)$ reduces to $(1, 2) (2, 3)$. Additionally, $(1, 2) (2, 3) (1, 3) (3, 1)$ reduces to $(1, 2) (2, 3) (3, 1)$.

This is not an MST (or arborescence) problem since we care every vertex as a root hence Edmond's algorithm does not work.

I am clueless at this point. At least a hint is highly appreciated.


texts: Augmenting AVL tree to calculate sum of subtree

texts:
Suggest a way to augment an AVL tree to support a $O(\log n)$ implementation of the function
calculateSum(key), which receives a key of a node and returns the sum of its subtree.
I implemented it this way:
sumSubtree(node):
    if node != null:
        return sumSubtree(node.left) + sumSubtree(node.right) + node.key
    return 0

calculateSum(key):
    node = Search(key) // assuming I have a search function
    return sumSubtree(node)

which solves it in $O(\log n)$.
But I read it is possible to maintain the sum during insertion and deletion. And augment an AVL tree this way.
Which solution would be better? Mine, or the other method? Does it matter?


texts: Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?

texts:
So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time complexity faster than O(N log N)? So I'm going to go into what I've been pondering, but have a couple specific questions at the bottom.

Comparision based
So the baseline case would just be to compare every element in array_a against every element in array_b, being O(N^2). So what I was thinking was using a sort O(N log N), and then iterating through each of the arrays, making comparing array[i] with array[i+1], if they are not equal, copy array[i] to a new array (or a linked list, since I'd just be accessing it in order for the next step) and then increment i, so that way I have arrays without duplicates. Then do a preliminary check to see whether the # of elements are the same in both lists. Then with the list, compare whether the first element in the linked lists are equivalent, then check the next node in the linked list, and so on. If all checks are equal then they represent the same set. So this would be O(N log N). Doing a sort with a tree might work as well, but again would still be in the same complexity class of O(N log N)...

Hashing?
So what I was thinking initially was looking at using hashsets to remove duplicates since operations with those would be amortised constant time, doing a preliminary check by checking whether both arrays have the same amount of distinct elements, adding the hashes of the elements of both arrays if they are not equal then there's no point in checking every element of each array and comparing it so that way a response of false would be relatively quick, if they are equal, then to check against collisions I'd sort it and then check arr_1[i] with arr2_[i] for i = 0, ..., n-1 - so the step of sorting would be the slowest giving this a time complexity of O(n log n) based on the sorting function used.

Questions
Other than using hashing-based structures or algorithms that would require elements to be sorted first,, what other data structures (like trees would work I'd supposed) could I use to remove duplicates in an efficient way? Are there any novel data structures (even if impractical in practice) or different approaches for removing duplicates?

If the only information known about the sets is that they have a total order relation, would this make any impact on whether each element can be hashed and the quality of the hashes on a theoretical point of view?

Are there any properties in set theory that I could exploit somehow for a faster algorithm design in a language-agnostic way?


texts: Find the center node on a weighted, non-directed graph

texts:
So I have a problem, and it's an assignment from school.

This is a figure made out of matchsticks.
The goal is to find the optimal location to light up the figure so that it burns in minimal time. You can only light it up at integer positions (C,B) but not A. Different matchsticks may have different burn times.

My approach to this problem:

Iterate through every possible "light up" point
For every "light up" point, light up the figure and wait it to burn completely
Store the time it took to burn
Once iteration is complete, find the lowest time and there's your answer

The problems with my approach

Burning each figure will take a while since it's done realtime. It's also possible to do it faster then realtime, but I still don't think it's a viable solution.

Problems with center of a weighted graph:

What if we come up with A as the center?

Solution:

Just pick the next potential center and check if it's a valid "light up" point.

So I'm looking for a graph algorithm that can calculate the center on a weighted graph. I've never dealt with graph algorithms before, so that's why I'm asking here.
I'm also just asking for you to point me in the right direction, and not write the code for me (although I guess some pseudo code will come in handy).


texts: Is the language in the description context free?

texts:
I am stuck on a question. Lets say there is a string that can be created from three alphabets a,b,c the condition is number of a<= number of b<= number of c. I can solve if there are a and b (two alphabets) but I am not able to solve for 3. Any help will be appreciated.
Thanks


texts:
My understanding of how a GPU works is kinda solid I think.

This is what I understood searching on the Internet:

VRAM (or framebuffer) stores what you see on screen.
Most of what the GPU does is encoding/decoding and processing data(mainly for 3D).
The GPU also sends (depending on the type of connection, HDMI, VGA etc..) data read from the framebuffer to the screen.

Anyway, I don't quite understand how this data is stored.

The GPU has serial ports which sends/receive data from CPU. But this is the part that I don't understand.
If the CPU sends only data(like images), how the GPU knows what addresses of VRAM will use for that piece of data if the CPU didn't send any address?

Old CPU architecture used 'inb' and 'outb' for reading and writing from and to an external device. Was it the same for GPUs?


texts: It is necessary to minimize the functional

texts:
Consider the town as a grid $N$ x $N$. Thus, there are $(N+1)(N+1)$ of junctions and $2N(N+1)$ two-way roads. Every intersection has a height. It is known that the upper left intersection has a height of $0$, and the lower right the height $1$. For each road we know how many people go in each direction on this road. In this case, if the road leads from the intersection $i$ to the intersection $j$ and the height difference $h = h_j - h_i$, the inconvenience of moving every person on this road is equal to $\max(h, 0)$. For all intersections except two angle are allowed to choose any height. It is necessary to minimize the total inconvenience. In the end, it is necessary to obtain only a total inconvenience, the individual heights are not needed.

I think all heights will lie in the set $\{0, 1\}$. It is clear that you can honestly cycle through all the bitmaps and choose the best. But you need to find more efficient algorithm. One of my ideas was to put all the intersections in the upper left part of the height equals $0$, and the right lower part of the height equal to $1$. Here would be required to find the optimal boundary. I came up with a way of solving by finding maximum flow of minimum cost in $O(N^8)$. Can it be better?

Example:

P. S. Sorry for my bad English.


texts:
PageRank is used and studied in incredibly many contexts. It is taught in many courses worldwide, with several books and thousands of papers devoted to it. To this regard, PageRank plays a quite unique role in network science.
The fact that Google put PageRank forward as the key ingredient of its search engine surely has something to do with this success. But PageRank also has key features that make it particularly appealing, and its extensions should certainly preserve as many of these features as possible.
I am therefore interested in identifying the most important scientific and technical strengths of PageRank.
Among them:

it has an intuitive and simple definition, and it gives relevant / easy-to-interpret insights;
it is mathematically tractable, thanks to its connections to Markov chains, random walks, and matrices;
its computation is fast, thanks to the power iteration method, its convergence, and possible approximations;
its computation requires limited space, thanks to a smart encoding of the underlying dense transition matrix;
it is prone to many extensions, that include edge weights, biased teleportation, temporal aspects, and others.

Do you think of any interesting addition to this list?


texts: Is there a tactic to help resolving existential quantifiers in Coq?

texts:
I am working on Software Foundations Volume 1 on my own it is its 2019 version by the way, and I have reached to its lesson Inductively Defined Propositions, and there, for almost one month I have been stuck on an exercise re_not_empty expressed like this in Coq (the exercise itself begins at Fixpoint):
Inductive reg_exp {T : Type} : Type :=
  | EmptySet
  | EmptyStr
  | Char (t : T)
  | App (r1 r2 : reg_exp)
  | Union (r1 r2 : reg_exp)
  | Star (r : reg_exp).

Inductive exp_match {T} : list T → reg_exp → Prop :=
  | MEmpty : exp_match [] EmptyStr
  | MChar x : exp_match [x] (Char x)
  | MApp s1 re1 s2 re2 (H1 : exp_match s1 re1) (H2 : exp_match s2 re2) :
      exp_match (s1 ++ s2) (App re1 re2)
  | MUnionL s1 re1 re2 (H1 : exp_match s1 re1) :
      exp_match s1 (Union re1 re2)
  | MUnionR re1 s2 re2 (H2 : exp_match s2 re2) :
      exp_match s2 (Union re1 re2)
  | MStar0 re : exp_match [] (Star re)
  | MStarApp s1 s2 re (H1 : exp_match s1 re) (H2 : exp_match s2 (Star re)) :
      exp_match (s1 ++ s2) (Star re).

Notation "s =~ re" := (exp_match s re) (at level 80).

Fixpoint re_not_empty {T : Type} (re : @reg_exp T) : bool Admitted.

Lemma re_not_empty_correct : ∀T (re : @reg_exp T),
  (∃s, s =~ re) ↔ re_not_empty re = true.
Proof. Admitted.

Although I am obliged not to tell anything about solutions but to get help I have to say at least about Fixpoint that is defined like this:
Fixpoint re_not_empty {T : Type} (re : @reg_exp T) : bool :=
  match re with
  | EmptySet => false
  | EmptyStr | Char _ => true
  | App re1 re2 => re_not_empty re1 && re_not_empty re2
  | Union re1 re2 => re_not_empty re1 || re_not_empty re2
  | Star re => re_not_empty re
  end.

I could prove the backward case easily. For the forward case I stuck at Star re there is a ∃ s, s =~ Star re in the evidences or context and a ∃ s', s' =~ re in the goals. The most probable thing to pass it is using inversion on that evidence but how to tell Coq with destruct to put s1 ++ s2 instead of s and put the results in the context instead of in the goals?


texts: Search Space for Population Metaheuristic Optimization Problem

texts:
Given that x objects (repetition allowed) can be arranged into y configurations, and that the population size is N, I am uncertain as to whether the size of the search space is |S| = |(y^x) * N| or |S| = |(y^x)^N|.

|y^x| comes from basic combinatorics: it is the number of ways to arrange |x| objects into |y| configurations.

As an example, suppose x = (1, 2, 3, 4) and y = (1, 2, ... 5) and N = 100. Clearly, |x| = 4 and |y| = 5. The xs are drawn from some probability distribution (e.g., uniform). A configuration might look like

1 1 3 2 4

Another might be

4 3 1 1 3

for some previously-specified probability distribution. The underlying metaheuristic algorithm generates N = 100 such configurations randomly.

I am just unsure on how to incorporate N.


texts: I'm having a hard time thinking of context free languages. The only example I've been able to think of is $0^n1^n$, but I'm having a hard time thinking of any others. Can I get some examples?


texts: Where does the terminology of open addressing resp. closed hashing come from?

texts:
One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books).

Why the names "open" and "closed", and why these seemingly contradictory names for the same method?


texts: Proof for values of d with d:= ||L|| - N(L) with $d \in \mathbb{Z}$ and N(L) Nerode Index

texts:
Let ||L|| be the sum of all lengths of words in L und N(L) the number of equivalence claesses for the Relation $\equiv_L$ from Myhill–Nerode theorem. Proof, which values d can have with $d:=||L||-N(L),d\in\mathbb{Z}$
Some conclusions I came up with so far:

|L|| is infinite, when L is infinite. Then d is not defined.
When N(L) is infinite for any non regular language, so L is infinite as well and $\infty - \infty $ wouldn´t be defined.
So say ||L|| is finite then N(L) is finite as well because every word hase to be in a certain class. If not ||L|| would be infinite. Though when N(L) is finite, ||L|| doesn´t have to be finite since we might have some symbols looping over states.
d is probably never negative, because if N(L) > ||L|| we would have classes which don´t belong to words in L.
When d = 0 then, N(L) = ||L|| and there would be a class for every word in L.

So d can be anything from $\{ 0,...,\infty \}$
Might this be enough for an answer or am I missing any cases/details? Where could I be proofing more formally?


texts: PDA for the language of strings containing the same number of a and b

texts:
Need idea for solving the following pushdown automata:

$\mathcal{L}=\{w\in\sum ^* | \#a(w)=\#b(w),|w|\geqslant 0\}  \,\,\,\, \sum=\{a,b\}$

In the beginning I thought to PUSH A for input a, and then to POP A for input b, but it doesn't work well for the word ba for example


texts: Complexity of an algorithm for bounding a region in 2D

texts:
First I apologize if the title is unclear, but I didn't find anything better.

I'm solving a differential equation that has two parameters , here denoted by points of a plane.These parameters are real numbers. For some points of the plane (or, equivalently, for some parameters of the differential equation) , the solution of the equation satisfies some condition and we denote such points of the plane with 1. This points make a simply-connected region in the plane, and I know that this region lies somewhere in $0<x<1.6, -.7<y<.3$ rectangle. My goal is to find this region.Remember that this region is on the real plane.($\mathbf R^2$)

My main question is this: I already know these two things about the wanted region:

The set of points on the plane that satisfy the conditions (the wanted region) , form a simply-connected region
This region lies somewhere in $0<x<1.6, -.7<y<.3$ rectangle

for example it may be something like this:

I want to use this two facts to find the region with less computations; i.e. instead of checking the condition on all points on the rectangle, actually , on a very high-resolution grid (this the first approach below), use an algorithm (below : Variant 2) that more quickly converges to the boundary (and so determines the region without inspecting all points).

(If you know a better approach ,I'll be happy to hear)

Variant 1 (the naive approach, noted above)

Divide each axis to identical steps (of length $\Delta$ ) and check the condition on each node to find the region.$\Delta$ must be as small as possible to find the region with an acceptable accuracy ($\Delta0.001$ suffices for my purpose) . (in the picture : nodes = intersections). This method needs a huge number of check operations , but can be used to find all kinds of regions; I mean if I didn't know that the wanted region is connected or it had sharp edges, etc. ,this method was the only way.

Variant 2

(It may be a famous method, but I haven't seen it before)

Because the region will be simply connected, it suffices to find its boundary .We use a recursive approach. We start from a grid (like the first step, but with much larger distance between nodes, say, $100\Delta$) and check the condition on this grid.For the next step, I assume the interval between two adjacent 1s is 1 everywhere and between two adjacent 0s is 0 everywhere. If two adjacent nodes gave different results (1 on one them and 0 on the other) , I put a point between them and check the condition on that point (red points in the picture) check this point. If it was 1, I put a new point between this point and the adjacent 0 and check that point; and if it was 0, I put a new point between this zero and adjacent 1 and check that point. I continue till I arrive at a distance of $\Delta$ between points.So I've found the boundary. (This method is like bisection method  for finding the roots of a function)

In the picture, the first iteration is shown.Black and yellow points are the points of the initial grid (that are distributed on the whole rectangle) and red points are those that are added after checking the initial grid nodes. Black points are points that are determined to satisfy the condition (are 1) and so are certainly inside the region. Yellow points are those that did not satisfy the condition and so are outside, and red points are those added in the 2nd iteration , between adjacent nodes with different results (between a 1 and a 0) ,according to the  above paragraph.

So , using this method I've found the region with the same accuracy as in the first method, and saved a lot of time too.

I want to know how much this method is faster. A qualitative answer that shows if it is better to implement this method , suffices. My problem is so computational intensive that I can't use the first approach.


texts: Algorithm for the function "drop" in a binary random-access list

texts:
In the book Purely Functional Data Structures by Okasaki, exercise 9.1 asks:

  Write a function drop of type int x a' RList -> a' RList that deletes the first k elements of a binary random-access list.  Your function should run in O(log n) time.

Using the features the author is using so far, i.e. a complete binary leaf tree and a dense representation, what does the algorithm look like?

It can't be a sequence of k calls to unconsTree because this would not run in O(log n).


texts: Formalizing basic category theory in Coq

texts:
I'm a total beginner in Coq and I'm trying to implement some category theory stuff as an exercise.

I surfed a little among git repos of the many avaible such implementations (HoTT, Awodey's Coq companion, etc.) it seems that every single project implements something like that

Record Category : Type :=
  mkCategory{
    ob : Type ;
    mor : ob -> ob -> Type ;
    compose : forall x y z : ob,
                mor x y -> mor y z -> mor x z ;
    identity : forall x, mor x x ;
    (* ... axioms ... *)
  }.

It is kind of natural, considering most definition of categories in modern book. However, I feel that it would be easier to implement it internally (if not mistaken, it was the common definition at Grothendieck's time) :

  Definition. A category is the data of

  a set/class $\rm Ob$ of objects,
  a set/class $\rm Mor$ of morphisms,
  functions $s,t \colon {\rm Mor} \to {\rm Ob}$, and $i \colon {\rm Ob} \to {\rm Mor}$ ($s$ stands for source, $t$ for target, and $i$ for identity)
  a function $\circ \colon {\rm Mor} \times_{s,t} {\rm Mor} \to {\rm Mor}$ whose domain is the fiber product of $${\rm Mor} \stackrel s \to {\rm Ob} \stackrel t \leftarrow {\rm Mor}$$

  satisfying some axioms...

The advantage of such a definition is that it generalizes directly by replacing "set/class" by "objects of some category" and "functions" by "morphisms of this category", leading to the concept of internal category. (Then you can talk of topological/differential categories, or categories inside a topos, etc.)

My problem is to formalize the fiber product in Coq. My first attemp would be to do something like

Record Category : Type :=
  mkCategory{
    ob : Type ;
    mor : Type ;
    s : mor -> ob ;
    t : mor -> ob ;
    compose : mor -> mor -> option mor ;
    i : ob -> mor ;

    adequacy : forall f g : mor,
                 (exists h, (compose f g) = (some h)) -> (t f = s g) ;
    (* ... axioms ... *)
  }.

But I feel that could lead to some curbersome later code. For example, chained compositions would be difficult to read.

Is there a project with an implementation based on the internal definition? Is there a quick way to define the fiber product I need in Coq?

Edit. By the way, I see a lot of

Ob :> Type

rather of

Ob : Type

What is the meaning of the extra ">"? From the doc, it seems it is some kind of coercion. What exactly does this mean?


texts: Elegant algorithm to semi-decide if two lambda calculus terms are equivalent

texts:
Given two lambda terms $t_1$ and $t_2$, it is semi-decidable if they are equivalent (i.e. can be rewritten as each other using alpha, beta, and eta conversions). An algorithm to do this is to try every sequence of rewrites starting with $t_1$, and if any of them end with $t_2$, then output true.

What other algorithms can be used? Are there any more "elegant" algorithms?

EDIT: [This] claims that a generalization of the Knuth-Bendix completion algorithm can semidecide the word problem. It has not citations though.


texts: Write the Brute Force Recursive Code to generate the longest substring containing k distinct vowels

texts:
Given a string s we have to find the length of the longest substring of s which contain exactly K distinct vowels.
This is the problem statment given on geeksforgeeks
Input : s = “artyebui”, k = 2
Output : 6
The only solution present on geeksforgeeks is the dynamic programming one. Can someone help with the recursive solution?


texts: Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient?

texts:
Yesterday StackOverflow was down for half an hour. Later, they wrote a blog post about it, detailing that the problem stemmed from unexpectedly high complexity of regular expression matching.

In short, the regular expression a+b, when running on the string aaaaaaaaaaaaaac, runs in $O(n^2)$ time where $n$ is the number of a characters, because it uses backtracking.

You can reproduce the issue with the following Python code, which on my computer, takes over 4 seconds to run:

import re, time
start = time.time()
re.findall(r'\s+$', ' '*20000 + 'x')
print(time.time() - start)

This was very surprising to me; I'd have thought that a regex matcher works more efficiently, e.g. by constructing a DFA from the regex and then running the wanted string through it, which I'd have thought would be $O(n)$ (not including the DFA construction).

(For instance, the book Introduction to Algorithms by Cormen, Leiserson, Rivest goes through a similar algorithm on the way to introducing the Knuth-Morris-Pratt algorithm).

My question: Is there something inherently difficult in regular expression matching that does not allow an $O(n)$ algorithm, or are we simply talking about an inefficient implementation (in Python, in whatever StackOverflow uses, etc.)?


texts: Show a sequence of distinct Primes number is O(log n)

texts:
Suppose I have a sequence:

$$n = \prod_{i=1}^{r(n)} p_i^{d_i}$$

for some primes $p_1 < p_2 < \dots < p_{r(n)}$, and each $d_i \geq 1$ an integer. The function $r(n)$ denotes the number of distinct primes divisor of $n$.

I'm trying to show $r(n) = O(\log n)$.

What I have tried:
I think I can establish an upper bound on $\prod_{i=1}^{r(n)} p_i^{d_i}$ to show its asymptotic bound.

To simplify and without loss of generality, let $d_i = 1$. Then,

$$n = \prod_{i=1}^{r(n)} p_i$$
$$\log n = \log (\prod_{i=1}^{r(n)} p_i)$$
$$\log n \geq \Sigma_{i=1}^{r(n)} \log p_i$$

Then not sure where to go from here.

I think I want to show something like:

$$\log n \geq \frac{r(n) + 1}{2}$$


texts: How to denote a graph class which allows only $k$ instances of a certain induced subgraph?

texts:
Suppose that a graph class $\mathcal{C}$ is defined as follows:

  A graph $G$ belongs to $\mathcal{C}$ if, and only if $G$ is chordal,
  but has at most $k$ $5$-cycles.

I am aware that the definition of $\mathcal{C}$ is contradictory. However, I am looking for a notation like

$G \in C_4\text{-free} + k*(C_5)$

Is there such notation in the literature?


texts: Is it possible for a stack-based programming language to be concurrent?

texts:
I have been reading about stack-based programming languages, such as FORTH and Cat, and it seems that given their nature, they can only execute one action at a time regardless of their paradigm (FORTH is imperative whereas Cat is functional).

An imperative language would modify the stack, and a purely functional language, such as Joy, would return a new stack, but the point is that only one stack is used at a time.

So, can stack-based programming languages be concurrent? Could they achieve concurrency by using multiple stacks at the same time or something alike?

Is it possible to implement lazy evaluation in a stack-based programming language?

Please correct me if I am misunderstanding anything about the languages and concepts mentioned above


texts: Solve a recurrence relation with two recursion calls using the iteration method

texts:
I can't figure out how to solve this recurrence relation using the iteration method:

$$T(n) =
\begin{cases}
0, & \text{if $n=0$} \\
1, & \text{if $n=1$} \\
3T(n-1)+ 4T(n-2),  & \text{if $n >1$}
\end{cases}$$


texts: Proof Idea: There are irrational numbers whose decimal expansion cannot be computed

texts:
The online lecture I am watching stated a proof idea:

The set of all possible programs is countably infinite, yet
the set of irrational numbers is uncountably infinite.

I don't think this is sufficient, it assumes one program can only return one irrational number.
How to show that I can not write one program that returns all irrational numbers?


texts:
So I have the question: show "Show $\{0^1^|≠\}$ is not regular". I've already seen various proofs for this question, but they all have one step I don't get.
They all take: $\bar{L}∩(0^∗1^∗)$ ($\bar{L}$ is the complement of $L$) and show that it's not regular. I don't get why we can't just take $\bar{L}$. Because isn't $\bar{L} = \{0^1^|m=n\}$ which is the same as $\{0^n1^n|n ≥ 0\}$ which we know is not regular? What am I missing?


texts: Is a rational game playing agent still rational when not staying off terminal states when it looses in all child states?

texts:
I am working on a programming assignment to implement a Minimax algorithm and heuristic for the game Lines of Action.

The rules are pretty simple, each player alternates turns moving a single piece. A piece may move in rows, columns, and diagonals and it must move the exact number of spaces that there are other pieces in that "line of action". A piece may capture an opponent piece, jump its own pieces, but it may not jump other players pieces. The game is over when all of a players pieces form a connected graph.

I have been debugging my implementation of Minimax and have found a case in which an "odd" move is made. For debugging I have been using a smaller board than the usual 8x8 version used in normal play. In the image below you can see the pieces for the Black (human/myself) and Red (computer/minimax) players across and entire game on a 4x4 board, the final board showing the "odd" move made by Red.

As you can see the "odd" move is that Red opts to end the game by taking Black's piece which results in Black's win, Red seems to cause its own demise. But this doesn't seem so bad. If you look at Red's possible moves after Black's starting move below

There is no possible way that Red can stop Black (a totally rational player; myself) from winning after its move. Can this move by Red still be seen as a rational move?

(Seeing that I wrote the minimax implementation) I want to think that in a no win situation any move by a rational agent can be seen to be rational if there is no possible way to win. Though in the case above Red could still increase its utility before its demise. For instance, Red could try to block one of Black's moves

If an agent can still gain utility in the short run but always loose in the long run, must it to still be rational?


texts:
Is there a class which is to APX what BPP is to P?

I'm looking for a definition that is like the following:

"For $r > 0$, an $r$-RPCA (randomized polynomial-time constant-factor approximation) algorithm for a function problem $T : \Sigma^* \to \mathbb{N}$ is a probabilistic Turing machine $A$ with the following property: $A$ runs in time $poly(|x|)$ and has $\mathbb{P}( r^{-1} T(x) \leq A(x) \leq r T(x)) \geq 2/3$."

I think that either a class like this exists and has a standard name, or there is something wrong with it. I'm looking for a similar definition with which to cleanly state a result.


texts: Determining whether Turing machine halts on input: primitive recursive?

texts:
In Elements of the Theory of Computation by Lewis and Papadimitriou, the authors use a specific function for proving that application of unbounded minimization on a primitive recursive function need not be regular.
They choose a peculiar function to prove so, defined as follows.

Let $M=\{K,\Sigma,\Delta,s\}$ be a Turing machine. Define
$G(n,m)=0$ if $n$ does not belong to $\Sigma^*$ or if $m$ is the output of Turing machine $M$ when presented with input $n$, and let $G(n,m) = 1$ otherwise.

They then go on to show why an application of unbounded minimization on the above reduces to the problem if $M$ halts for every $n$. My question is why is $G$ even primitive recursive? Because $M$ may not be primitive recursive.


texts: Confusion in Turings proof of the undecidability of the Entscheidungsproblem

texts:
I was reading Turing's paper on computable numbers and the Entscheidungsproblem. There is this part of Section 9, Part II that I cannot quite seem to understand. He says:

It is pretty straight forward until the part where he introduces $\mathfrak{U}$. So $\mathfrak{U}$, he says, includes the Peano axioms; but what else does it include? I guess it includes the axioms for $G(x)$ as well, because only then would $\mathfrak{U}$ be able to "define" the sequence $\alpha$ that is being computed by $G(x)$. I am taking the word "define" here in its usual sense, but Turing explains what he means by "$\mathfrak{U}$ defining $\alpha$" as:

So for $\mathfrak{U}$ to define $\alpha$, $-\mathfrak{U}$ must not be provable? I am not sure why that is required? Because by restricting that $-\mathfrak{U}$ must not be provable we are saying that $\mathfrak{U}$ must not be refutable, which means that the sequence $\alpha$ cannot be all 0's (or so I think). But why would we want $\alpha$ to not be all 0's?
I am also confused about the two formulas ($A_n$ and $B_n$) he has written above. I am not sure why if has included the $F^{(n)}$ part. If $x$ satisfies the Peano axioms and the axioms of $G(x)$, then $U$ being a conjection of all these axioms is given to be TRUE, and if $x$ does not satisfy these axioms then $\mathfrak{U}$ is obviously FALSE. So, just based on $\mathfrak{U}$ we can tell whether $A_n$ is TRUE or $B_n$. So what is the point of $F^{(n)}$ here? I think the following set of implications say pretty much the same thing as what Turing has?

Sorry if I am overlooking something here.
Edit 1:
Here are the footnotes:


texts: Bresenham's line drawing algorithm guarantees

texts: I am considering implementing my own version of Bresenham's line drawing algorithm, found here, my one question is does the algorithm guarantee that both endpoints will be covered/drawn. I am doubting this because of the error accumulation factor (decision variable), but I may be wrong.


texts:
Algorithms for the finding of an MST in a graph can be applied for both maximum and minimum spanning trees.

It is well known, however, that the finding of a max-cut in a graph is an NP-hard problem while the min-cut problem can be easily solved in polynomial time.

Why aren't the two equivalent?

What is the restriction that I’m missing here?

Thanks!


texts: Oracle Relations Between Complexity Classes

texts:
I'm trying to get a better handle on oracle separations between complexity classes but I keep running up against some (seemingly) silly issues that make me think that I'm fundamentally misunderstanding something (or more than one thing).

For example, I understand that for an oracle separation to hold in the unrelativized case it must hold for all possible oracles (which is why we cannot answer P=NP? this way). However, is it not true that for any two complexity classes we can always construct an oracle such that they are equivalent in relation to that oracle? For instance, by choosing a higher level of the arithmetic hierarchy to use as the oracle?

i.e. given two complexity classes $A$ and $B$ such that $A,B \subseteq \Sigma_{n}^{0}$, is it not always the case that $A^{\Sigma_{n+1}^{0}} = B^{\Sigma_{n+1}^{0}}$, given that the arithmetic hierarchy doesn't collapse? If not, why?


texts:
To cut a wooden board, a sawmill charges proportional to the length of the board. The cost of cutting a single board into many smaller boards will thus depend on the order of the cuts. As an example, lets say cutting a $10m$ board into two pieces costs $10$. Then to cut a $10m$ long board at marked positions $3m$ and $5m$ costs $10+7=17$ if it is ﬁrst cut at position $3m$ and then at $5m$. On the other hand, if it is cut at $5m$ position ﬁrst, and then at $3m$, it would cost $10+5=15$. As input, you are given a board of length $n$ with $k$ marks on it. You need to give an algorithm that, given an input length $n$ and a set of $k$ desired cut points along the board, will produce a cutting order with minimal cost in $O(k^c)$ time, for some constant $c$

I'm getting $O(k!)$ complexity :(


texts: If you can represent/model a Conditional IF statement with AND + NOT or OR + NOT

texts:
I am still trying to wrap my head around this, which shows how to simulate control-flow without using an if-statement.

I've been looking at basic logic today and learned that you can represent all logic with 1 (like NAND), 2 (AND + NOT, OR + NOT, etc.), or 3 logical primitives.

This makes me wonder if you can represent the if-statement using just AND + NOT or OR + NOT (and what it might look like), such that a program loop would be able to evaluate an expression such as if (a) b(), or something more complex like in the first link above.


texts: Proof of 0/1 knapsack optimal substructure

texts:
I'm trying to understand why exactly the 0/1 knapsack problem actually has the optimal substructure property.

Let $E$ be the set of items to consider and $v$ and $w$ the value and weight functions defined over $E$.

Now, suppose that, among all solutions weighing at most $W$, $S \subseteq E$ is the best solution. How can I prove that $S - \{x\}$ is the best solution weighing at most $W - w(x)$, considering the set of possible items as $E - \{x\}$? I tried to suppose that $S' \subseteq E - \{x\}$ is a better solution (that is, $v(S') > v(S - \{x\})$ and $w(S') \leq W - w(x)$), but I get stuck when I try to find a contradiction.

Any help?

Thanks in advance!


texts: Why is the processor's pipeline delay calculated as N*max(Delay) ? why not N*(D1 + D2 + D3 ... )?

texts:
Consider a four stage pipeline, and each stage has delays D1, D2, D3 and D4, so the total delay because of the various stages should be N * (D1 + D2 + D3 + D4) where N is the number of instructions, but I see that this is not the case, I see here that the delay is calculated as N*max(D1,D2,D3,D4) , why is only the max value taken into account ?

I try to apply the above two ideas for the below chart and none of them work.

For the below chart consider that the numbers on top are the time and the S1, S2, S3 and S4 denote the time spent any stage of an instruction on the pipeline

with N*(max(S1,S2,S3,S4)) = 4*(4) = 16,
and with N*(S1 + S2 + S3 + S4) = 4*(1+2+4+1) = 32

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
S1 S2 S2 S3 S3 S3 S3 S4
   S1    S2 S2       S3 S3 S3 S3 S4
      S1       S2 S2             S3 S3 S3 S3 S4
         S1          S2 S2                   S3 S3 S3 S3 S4


texts: In C++ how does "sizeof(array)/sizeof(array[0])" give the number of elements in an array? Why isn't it affected by the length of each element?

texts:
I'm playing around with C++ and was looking at how to loop through an array of unknown length. The following code was suggested and works perfectly from the little testing I've done:
std::string words[5] = {"Lorem ipsum dolor sit amet orci aliquam.", "Hi", "Welcome", "World", "LoopyDoopyDoo"};
for (int i = 0; i < sizeof(words)/sizeof(words[0]); i++){
     DO STUFF
}

From what I've read the sizeof() operator returns the size of a variable in bytes.
What I don't understand is how this isn't affected by the number of characters in each element of the array. I printed out the sizeof() value to check and the array size is always evaluated at 160 bytes and element 0 as 32 no matter how many characters are present. I thought that it might be allocating 32 bytes but not using them all so I stored some text that should use 40 bytes, but still no change. Am I missing something here? Is text stored differently in C++?
Any help in understanding how this actually works would be appreciated, thanks!


texts: Is there a way to make chess an absolutely fair game?

texts:
Chess is usually considered a mostly "fair game" between White and Black because the opening position of pieces has mirror symmetry (between players). In practice it also appears to be a fair game because it is combinatorially complex, so if White has a first-move-advantage, it is hard to detect in actual play.

What are some examples of changes in the rules of chess where the game can be made exactly mathematically fair, including eliminating any possibility of White's possible first-move-advantage, and without adding any chance events (such as a coin toss as to who moves first)?


texts: Is class of threshold functions Agnostic PAC Learnable?

texts:
In "Understanding Machine Learning, From Theory to Algorithms" by Shalev and Ben-David, on page 44 example 6.1, it is proved that the class of threshold functions are PAC learnable.
on the other hand, The Fundamental Theory of Statistical Learning States that A-PAC learnable is equivalent to PAC learnable.

So can we say that class of threshold functions is also A-PAC learnable?

My second question is what is the difference between the two?


texts: How to solve $T(n)= T(n - 1) + \frac{1}{n\log n}$?

texts:
I am interested in the asymptotic bounds of the following recurrence:
$$T(n)= T(n - 1) + \frac{1}{n\log n}$$
with base case $T(1) = 1$. I'm having trouble while solving this recurrence. It seems much more tricky than I initially thought.
I've tried out by iterative method and since $\log(n!) = n\log n$,
I've got $\frac{1}{n\log n}$.
At this point, I've got that the summation of $\frac{1}{i}$ is equal to $\Theta(\log n + O(1))$.
So at the end, I've come up with this bound (by simplifying the two terms):
$\Theta(\frac{1}{n})$.
I'm not so sure about this bound. What is a good way to approach this problem?


texts: 3D Convex Hull Divide and Conquer Advancing Mechanism

texts:
I am currently trying to implement the divide and conquer method of computing the 3D convex hull given by Preparata, outlined here:

http://www.cs.jhu.edu/~misha/Spring14/Preparata77.pdf

On page 91 it reads:

  The convex hull CH(A, B) of A and B may be
  obtained by the following operations (see Figure 4
  for an intuitive illustration):

  (1) Construction of a "cylindrical" triangulation $\Im$,
  which is tangent to A and B along two circuits $E_{A}$
  and $E_{B}$, respectively.

  (2) Removal both from A and from B of the respective
  portions which have been "obscured" by $\Im$.

Here is where the paper describes the construction of the "cylindrical" triangulation.

  We now describe the advancing mechanism of the
  procedure. If we temporarily exclude degeneracies,
  i.e. we assume that each face of $\Im$ is a triangle, each
  step determines a new vertex, whereby a new face is
  added to $\Im$. We shall discuss later the case in which the
  restriction on degeneracies is removed. In our illustration
  (Figure 4), $a_{2}$ and ($a_{2}$, $b_{2}$, $a_{1}$) are, respectively, the
  vertex and the face of $\Im$ constructed in the previous
  step. The advancing mechanism makes reference to
  the most recently constructed face of $\Im$. To initialize
  the procedure, the reference face is chosen as one of
  the half planes parallel to the $x_{3}$ axis, containing the
  initially determined edge and delimited by it. Let ($a_{2}$,
  $b_{2}$, $a_{1}$) be the reference face for the current step. We
  must now select a vertex $\hat{a}$, connected to $a_{2}$, such that
  the face ($a_{2}$, $b_{2}$, $\hat{a}$) forms the largest convex angle
  with ($a_{2}$, $b_{2}$, $a_{1}$) among the faces ($a_{2}$, $b_{2}$, v), for all
  v $\neq$ $a_{1}$ connected to $a_{2}$ ; similarly we select $\hat{b}$ among
  the vertices connected to $b_{2}$. For reasons to become
  apparent later, we call these comparisons of type 1.

  Next, once the "winners" ($a_{2}$, $b_{2}$, $\hat{a}$) and ($a_{2}$, $b_{2}$, $\hat{b}$)
  have been selected, we have a run-off comparison, called
  of type 2. If ($a_{2}$, $b_{2}$, $\hat{a}$) forms with ($a_{2}$, $b_{2}$, $a_{1}$) a larger
  convex angle than ($a_{2}$, $b_{2}$, $\hat{b}$), then  $\hat{a}$ is added to $\Im$
  ($\hat{b}$ is added in the opposite case) and the step is complete.

My question is how do you determine the vertices of the new triangle after you have chosen the winner?


texts: How can we get small test error reducing only train error?

texts:
My question is about mathematical part of machine learning algorithms, especially about using it in neural networks. We train network reducing train error and I was thinking about how then test error is also small (discarding overfitting and underfitting), what is mathematical proof for it. I found about that in this book http://www.deeplearningbook.org, chapter 5.2. Here is a part of that chapter:

  How can we affect performance on the test set when we can observe only
  the training set? The field of statistical learning theory provides
  some answers. If the training and the test set are collected
  arbitrarily, there is indeed little we can do. If we are allowed to
  make some assumptions about how the training and test set are
  collected, then we can make some progress. The training and test data
  are generated by a probability distribution over datasets called the
  data-generating process. We typically make a set of assumptions known
  collectively as the i.i.d. assumptions. These assumptions are that the
  examples in each dataset are independent from each other, and that the
  training set and test set are identically distributed, drawn from the
  same probability distribution as each other. This assumption enables
  us to describe the data-generating process with a probability
  distribution over a single example. The same distribution is then used
  to generate every train example and every test example.

I want to transfer this theoretical part to a more concrete example for better understanding. Assume we have images and we need to select train and test datasets. My questions are

What the author means by "example"? Is it every image? If yes, is that mean, that we consider every image as a random variable and every time it selected or not?
I totally can't understand why we need to do this assumption: "the examples in each dataset are independent from each other". Maybe I misunderstood the example part in my first question and it's come from that.
If the training set and test set are identically distributed why always in practice the training set is about 90% of all data and the test set is 10%, I can't see identical distribution in this situation.

Also, I would be glad if you will give me some references to read about this in other books/topics.


texts: Why are lambda-abstractions the only terms that are values in the untyped lambda calculus?

texts:
I am confused about the following claim: "The only values in the untyped lambda calculus are lambda-abstractions".

Why are the other terms not values? What does it mean for a lambda-abstraction to be a value? The first thing that came to my mind was that maybe lambda-abstractions are the only possible normal forms, but this is not true of course, e.g. $(\lambda x.\; x)\;y \to y$.

Can someone enlighten me?


texts: The time complexity for finding the kth smallest number in a min-heap

texts:
Suppose that $k < \sqrt n$, what is the time complexity to find the $k_{th}$ smallest number in a min-heap?

I thought that we can remove the root element for k times and each time we apply heapify? So it should be $O(k \log n)$ but the answer is $O (k \log k)$. What did I do wrong?


texts: Do all decidable problems lie in the class NP?

texts:
All decision problems (i.e.language membership problems), which are verifiable in polynomial time by a deterministic Turing machine are called NP problems. Further, these problems can be solved by a non-deterministic Turing machine in a polynomial time and in exponential time by a deterministic Turing machine.

Do we have a decision problem that is not verifiable by a deterministic Turing machine in polynomial time but decidable?


texts:
I had a test a couple of days ago and one of the question had 2 statements :

$L^+ = L^\ast$
$L$ contains $\varepsilon$

I had to say does 1 imply 2, does 2 imply 1 or do they both imply each other.

I answered that only 2 implies 1 but the answer is that they both imply each other.

But I don't understand, if $L = \emptyset$ (Empty Language), then $L^\ast = \{\varepsilon\}$ and $L^+ = \{ \varepsilon \}$, they are equal and $L$ doesn't contain $\varepsilon$.

Am I wrong?


texts: If there is a transition with no input in the FA, when it is converted to a regular expression should it be accepted as ɛ transition? As an example picture shown below, should regular expression showing possible transitions between 1 and 3 (1-2-3 , 1-3) be accepted (ab+ɛ) or just ab?


texts: Where are C++ templates inside of the lambda cube?

texts:
C++ templates have type variables and can express lambdas, so they must have System F embedded. But is that exactly where they are located in the lambda cube? Can C++ templates produce new types or express dependent types?

(I originally posted this to Stack Overflow, but they referred me over to here.)


texts: Where I can I find Pre Trained CNN Datasets for Facial Emotion Recognition?

texts:
I am working on a project that involves recognising emotion from images. There are two parts in the project: One where I will generate features from images using API's and then classify the emotion and the other part is where I will first use a CNN on a dataset and then take some layer of features and then give it to SVM to classify.

So, I need a dataset of images as well as pre-trained CNN on that dataset also. I have searched quite a lot on google and I am not able to find any. In some cases, I found a pre-trained CNN dataset but could not find the original dataset of images on which CNN was trained.


texts: Is it feasible to solve this subset cover problem with SAT solver?

texts:
The problem is to find $\mathcal{S}$, a minimal collect of subsets of $\{1,\dots, 17\}$ such that the two conditions are satisfied:

if $S \subseteq \mathcal{S}$ then $|S|=6$;
for any $A \subseteq \{1,\dots,17\}$ with $|A|=3$, there exists a $S \in \mathcal{S}$ with $A \subset S$.

See here for a related combinatorial problem..

I think this can be formulated as a Min SAT problem.

For each $S \subseteq \{1,\dots,17\}$ with $|S|=6$, we introduce a variable $X_S$. And for each $A \subseteq \{1,\dots,17\}$ with $|A|=3$, we introduce a clause
$$
\vee_{S: A \subseteq S, |S|=6} X_{S}
$$
Then in principal we can use a SAT solver to find the minimal number of $X_S$ that needs to be true to satisfy all the clauses.

This needs $\binom{17}{6}=12376$ variables, $\binom{17}{3}=680$ clauses of length $\binom{17-3}{3}=364$.

I have very little experience in actually using SAT solvers. So is this actually worth trying on my laptop or there's no hope at all?

——-

Update

Turn out there are many research on set covering. It seems that I was over ambitious to try to solve the problem for the parameters  (17, 6, 3).

It is already an open problem for (12, 5, 3).

See here for more details.

———

Update 2

Tried to write everything in pure SAT and it’s quite a bit faster using cadical than z3.

Also, it is significantly faster to find a solution than to show no solutions exist.

I tried to break the symmetry by adding the constraints that the first and the last subset in lexicon order must be selected.


texts:
I'm interested whether there is the standard solution to the following problem.
Some number of train routes is given:

Route1: First City -> Next City -> ... -> Last City

Route2: ...

...

We need to list all possible ways to get from one given city to the other with possible transfers but without visiting any city more than once. So, for example, if we're given

R1: A -> B -> C

R2: B -> D -> E

R3: C -> D -> A

R4: C -> E -> F

than the routes from A to E are the following:

A -> [R1] -> B -> [R2] -> E

A -> [R1] -> C -> [R4] -> E

I hope i've managed to explain properly. And thank you very much in advance for any tips.


texts: Is there any specific name for strings of data that have well defined format ? For example URLS, domain names, IP Addresses, Email addresses, File Paths etc. are all having well defined delimiters and data formats. What are these special strings in general called ?


texts: How is this algorithm in these two complexities?

texts: How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal to, but I am not fully sure. Any have any ideas? Thanks.


texts: Smarter recursion to compute #tilings of $m \times n$ board with small shapes that fit in $2 \times 2$ square?

texts:
This is a generalization of another question I posted because I wasn't clear that I cared about more than $2 \times 1$ dominoes (it's just a special case), and there is an explicit tractable formula for $2 \times 1$ dominoes. I was wondering about how to computationally (e.g., with recursion) obtain the number of tilings of an $m \times n$ board with a given subset of the contiguous shapes that are subregions of a $2 \times 2$ square (the $1 \times 1$ square, $2 \times 1$ dominoes, the $2 \times 2$ square, and the L-shapes).

If $m \leq n$, then we can use recursion on $n$ by keeping track of the which squares are filled in the $n$th column, which gives $2^m$ cases to keep track of for each value of $n$, with the cases related between $n-1$ and $n$ based on how the empty spaces in the $(n-1)$th column are filled with the various shapes.

I was wondering, are there any significant improvements possible for this type of recursion? For example can we take advantage of some symmetries somehow? If improvements are possible, can it change the asymptotics for the computational time? For the current recursion, if the coefficients expressing cases for the $n$th column in terms of cases for the $(n-1)$th column are precomputed, then the running time is $O(nM)$ where $M = O(2^{2m})$ is the number of non-zero coefficients. If $n \gg m$ then successive matrix squaring can be used to get the running time to $O(2^{3m} \log n)$.


texts: Connecting The Informal and Formal Definitions of Decidable With Each Other

texts:
From pg. 64 of Lambda Calculus and Combinators, the author formally and informally defines the notion of "decidability":

1 Formal Definition

  Definition 5.4 A pair of sets $\mathcal{A}$, $\mathcal{B}$ of natural numbers is called recursively separable iff there is a
  recursive total function $\phi$ whose only output-values are $0$ and
  $1$, such that

  $$ n \in \mathcal{A} \implies \phi(n) = 0, $$ $$ n \in \mathcal{B} \implies \phi(n) = 1 $$

  A pair of sets of terms is called recursively separable iff the
  corresponding sets of Godel numbers are recursively separable. A set
  $\mathcal{A}$ (of numbers or terms) is called recursive or
  decidable iff $\mathcal{A}$ and its complement are recursively separable.

2 Informal Definition

Shortly thereafter, the author states

  Informally speaking, a pair $\mathcal{A}$, $\mathcal{B}$ is
  recursively separable iff $\mathcal{A} \cap \mathcal{B}$ is empty and
  there is an algorithm which decides whether a number or term is in
  $\mathcal{A}$ or in $\mathcal{B}$.

3 How to Connect These Definitions

Why is the existence of a recursive total function $\phi$ satisfying the properties of (1) logically equivalent to the notion that "there is an algorithm which decides whether a number or term is in the disjoint $\mathcal{A}$ or $\mathcal{B}$"?


texts: Can there exist more than one optimal solution in a dynamic programming problem?

texts:
In any dynamic programming problem can there exist more than one optimal state ?

If so how would I enumerate all of them ?

For example: in the subset sum problem for the given set $\{-3, -2, 7, 5\}$ and target sum $0$.

There exists two ways of reaching $0$. ie. $\{\}$ = empty set as a sum of zero, or $\{-3, -2, 5\}$ = also which has a sum of $0$.

In dynamic programming how would you distinguish between these two ?


texts: Soft question: program result verification

texts:
Let's say there's a cloud computing service that allows people to run arbitrary programs and get the results. The idea being that your machine is too slow, and you don't want to overwhelm it. If your program is something like "factorize 15672965357291016", then it's a perfect candidate for this service, because you can very quickly verify that a result handed back to you is correct. But if your program is long and complicated, and you can't think of a quick way to verify that a given input/output pair is correct, then you're stuck with running the program on your own machine to verify the results, which defeats the purpose.

One solution would be to use the blockchain and have a lot of people verify that some given input/output pair is correct--then you only accept the result as true when whatever block it's on has enough confirmations. The problem with this is that it could really slow down the network if your program is resource-intensive.

What would be nice to have is a programming language where a given program P, an input to it I, and a supposed output O, can be verified quickly (i.e. P(I) == O). That way, making confirmations would be fast, and the whole network would speed up.

I don't think this can be done in general because you could use it to solve the halting problem. If you have some function V(P, I, O), which verifies that P(I) == O, then running V(P, I, halts) would check that P halts on input I.

However, the fact that V does exist for every problem in NP makes me think that there has got to be some middleground, where you could make a really restricted language for which V always exists, and it can easily be determined from the structure of P (a trivial implementation is just V(P, I, O) = P(I) == O). I'm not really sure what my question is, but is this an existing problem? What search terms should I use to learn more about this?


texts:
Community,

I'm working on a project lifting assembler code to a AbstractSyntaxTree-like structures like these:

In order to be able to evaluate the final value of a tree given only leafes with constant values, I implemented an recursive approach: Each node class has its own value function. For all nodes except constants, it will query the value function of its children.

e.g. A add node has a value function which works like this:

self.children[0].value() + self.children[1].value()

This seems simple and stores Operation-Logic where it belongs: into operation nodes. The main problem is that these trees tend to be become very large and I fear an recursive approach might not be the best way here.

The most common operations ran on this tree are tree merging and optimization (transversal + modification). At the moment we use single-linked notes, since this serves the use cases in the best way.

Is there any iterative way of archiving this value evaluation? Any help appreciated.


texts: 'simple' algorithm that can predict disk usage or 'time to be full'

texts:
Let say I have time series of disk usage of last 30 days..
Given this information and with the assumption that the disk usage 'pattern' isn't changing dramatically over time, what would be a naive/simple algorithm to predict when is disk going to be full?


texts: How does a Turing machine with one tape read its input?

texts:
It's often implicitly assumed that we don't have to pay much attention to the difference between the program (which specifies the function being computed) and the input (the value on which that function is evaluated) when reasoning about Turing machines. In particular, people are often happy to assume that the program and inputs are encoded on the same two-sided tape. How this actually works out okay isn't obvious to me though.

Let's say I have a UTM, $\Phi_f$, which has a partially filled two-sided tape specifying a program for calculating the function $f$. Since the program is a finite set of symbols, it begins on cell $b$ and ends on cell $e$ where $b < e$. Now I want to encode the input on the same tape, so I begin at cell $b-1$ and work in the negative direction to encode my specific input, taking up as much space as I need.

My understanding is that as long as the encoding methodology I use to specify the inputs is computable and fixed in advanced, I can use any input encoding I want. The fact that it needs to be fixed in advanced is clear, since the actual program for calculating $f$ for two different encodings is very likely different. Intuitively, it makes sense that I can use any encoding I want because if we fix some standard "base" encoding then computing $f$ on an input encoded by the function $g$ is the same as computing $f(g^{-1})$ on an input encoded by the base encoding.

I have two questions:

Is the above correct? In particular, is it always possible to pick an encoding and a function, and then find a single program that computes $f$ on an arbitrary input using that encoding?
On the tape, what does the operation of the TM look like? The symbols used to encode the input have a meaning to the TM as a program (or can), and that seems like it could cause problems. For example, the (2, 18) UTM has symbols that always result in the head moving left and others resulting in the head always moving right. It seems like if you chose those symbols to encode the input you could run into problems where the UTM could never escape the input section of the tape.

EDIT: You can read about the (2, 18) UTM I mention for free here. The table presented on page 237 of the journal / page 23 of the PDF shows the table defining the machine. It's a bit hard to read, but it's two main columns each with three subcolumns. A row of $q_1\;1c_2\;Lq_1$ is read "if you are in state $q_1$ and read the symbol $1$ write the symbol $c_2$, move Left, and transition to state $q_1$. The row with a dash instead of a transition is the halting condition.


texts: How is this expression a valid lambda expression?

texts:
Can you explain how this expression follows the grammar of the lambda calculus?

$$\lambda x.x((\lambda y.yy)x)x = λx.x(xx)x$$

I am not sure why we have the parentheses following the $.x$ (on both sides of the equation).


texts:
I am trying to solve a problem with regards to a DFA. What is the minimal number of states for the following language:

$$L:=\{x\in\{a,b\}^n\ \ | \ \ |x|_a=|x|_b\}$$

where $|x|_a$ denotes the amount of $a$'s in the word $x$. I have done some calculations and got $3\cdot2^{(n/2)}-1$. Is this the correct number of states?

Here is the DFA for $n=4$:


texts: Design a turing machine that accepts $L=\{ww^Rw\mid w\in\{0,1\}^*\}$

texts:
I need to design a turing machine that accepts $L=\{ww^Rw\mid w\in\{0,1\}^*\}$.
$w^R$ is the reverse of $w$.

I don't have a good idea yet how to do that, I know I should check:

the length of the word must be equal $0\mod 3$

$ww^R$ is a palindrome

the prefix $w$ equal to the suffix $w$.

I thought maybe to divide the word to three parts and use non deterministic TM to move from one part to another.
Need help with the algorithm.


texts:
NOTE: This question is NOT the same as this other nearly-identically worded question with some amazing answers. I learned a lot from it regarding the mathematical importance of the empty string, but my question is specifically regarding its usage and purpose in a context-free grammar.

Update: After @Raphael's comments, maybe a better way to word my question is this: If the presence of the empty string in a non-terminal's RHS derivation is intended to remove the non-terminal from the resulting string, why would one want to do this? In what case would it make sense to remove a non-terminal?

Original Question:

I had an assignment to create a non-deterministic derivation, which I created as follows:

\begin{align}
A \rightarrow aAaBaC \ | \ aAaBc \ | \ aAaBC \ | \ aABC \ | \ d
\end{align}

This I then left-factored into the following deterministic grammar:

\begin{align}
A & \rightarrow aAA{'} \ | \ d \\
A' & \rightarrow aBA'' \ | \ BC \ | \ \epsilon \\
A'' & \rightarrow aC \ | \ c \ | \ C \ | \ \epsilon
\end{align}

This was marked as correct by my professor.

My question though is regarding the use of the empty string. I wasn't sure if including the empty string in the derivations was correct, but it was the pattern used in some examples I've seen and I followed that usage thinking that including the empty string was expected (or implied) in every factored derivation.

But when I asked the professor for clarification on that point he stated that the empty string is not implied in every derivation, and its usage has important connotations and is rarely used.

So given that:

What is the importance of the empty string in CFG derivations? I read that it is used to "erase" a LHS, presumably to terminate derivation and proceed to the next derivation? But I'm not clear on if there is more to it than that.
If the empty string is rarely used in a derivation or factored derivation, when is it actually meant to be used? If it should be used sparingly I'd like to have some guidance on that so I don't just litter my derivations with it.

Thank you.


texts: Clarifying "operation" in the definition of data type

texts:
A definition of data type I've seen is along the lines of "a set of values and a set of operations".

What exactly does an operation in this set comprise?

For instance, might an operation be considered as:

an identifier (e.g. integers have an operation, +)
an identifier with signature (e.g. + operates on two integers and results in an integer)
an identifier with signature and established behaviour (e.g. 1 + 2 = 3)
an identifier with signature and behaviour, together with some underlying implementation

or some other concept?


texts:
Let us consider the subset sum problem with $S = S_i = \{1,2,..,i\}$. There are of course $2^{|S|}$ different sums that can be formed.

Now it seems that though the sums are not in order and thus not searchable efficiently there is some structure as indicated by the picture below. In the image there are the cases i = 1..7. The "boxes" in bold indicate runs of increasing numbers, that is increasing values of sums, while the row numbers indicate how many numbers the sums consist of. Now it appears that the minimums (and maximums) of these boxes are in order. Now, to me it seems one could exploit this structure to make a search in $O(|S|^3)$ -time.
That is, pick a number in a box, then iterate below and above to find the min and max of the box. This is $\Theta(|S|)$. If the max is less than the target, then pick some box to the right of the current one. If the min is greater than the target, then pick some box to the left of the current one. The maximum size of a box is exactly |S|. There are |S|+1 rows to consider (to perform a binary search on). Thus the running time is $O(|S|^3)$, even though the number of boxes is $2^{|S|-2}+2$.

An example of the contents of boxes is the case of i=4, where the box structure is |0|;|1 2 3|4|;|345|567|;|6|789|;|10|;, where the rows are separated by semicolons. Here the |567| box is the |123| box (1-row) of the i=3 case with 4 added to each sum. And the |345| box is the box from the 2-row in the i=3 case. The key property is that the min's and max's are in order (in this case). So: 5 >= 3 and 7 >= 5. So, if looking for 6, one could conclude that it must be in the box other than |345|, if it exists at all. Maybe not so good an example as there are only two boxes.

A more illustrative example, perhaps:

S = {x1}
0: 0
1: x1

S = {x1, x2}, x1 <= x2
0: 0
1: x1 <= x2
2: x1+x2

S = {x1, x2, x3}, x1 <= x2 <= x3
0: 0
1: x1 <= x2 <= x3
2: x1+x2 <= x1+x3 <= x2+x3
3: x1+x2+x3

S = {x1,x2,x3,x4}, x1 <= x2 <= x3 <= x4
0: 0
1: x1 x2 x3 x4
2: x1+x2 <= x1+x3 <= x2+x3 ? x1+x4 <= x2+x4 <= x3+x4
3: x1+x2+x3 <= x1+x2+x4 <= x1+x3+x4 <= x2+x3+x4
4: x1+x2+x3+x4

S = {x1,x2,x3,x4, x5}, x1 <= x2 <= x3 <= x4 <= x5
0: 0
1: x1 x2 x3 x4 x5
2: x1+x2 <= x1+x3 <= x2+x3 ? x1+x4 <= x2+x4 <= x3+x4 ? x1+x5 <= x2+x5 <= x3+x5 <= x4+x5
3: x1+x2+x3 <= x1+x2+x4 <= x1+x3+x4 <= x2+x3+x4 ? x1+x2+x5 <= x1+x3+x5 <= x2+x3+x5 ? x1+x4+x5 <= x2+x4+x5 <= x3+x4+x5
4: x1+x2+x3+x4 <= x1+x2+x3+x5 <= x1+x2+x4+x5 <= x1+x3+x4+x5 <= x2+x3+x4+x5
5: x1+x2+x3+x4+x5

And so on... One can add as many xi's as one wishes.
The question mark indicates a box boundary, where one doesn't know the order of x2+x3 and x1+x4 unless they are fixed to some values.
But what is known is that eg. for the |S|=4 case: x1+x2 <= x1+x4 and x2+x3 <= x3+x4, allowing one to find the right box.

The question is: did I miss something obvious in the analysis? Can this be generalized to some other kind of sets?

edit:
Actually, it looks like what is found is a range of boxes instead of a single box. I mean, what prevents the target to fit between the min and max of every box other than the first and the last on a row, say?

So the updated question is: Is there a sub-exponential upper bound on the number of boxes to search?


texts: Description of lists with functions in LISP

texts:
I have been given the following implementation of basic list functions in LISP:

nil = (lambda (k) (k ’none ’none))
(cons x y) = (lambda (k) (k x y))
(car l) = (l (lambda (x y) x))
(cdr l) = (l (lambda (x y) y))
(null? l) = (l (lambda (x y) (= x ’none)))

As an intent to show that data can be constructed using only pure functions.

I don't understand very well this code. For starters, what's the role of k? Can you show how I can come up with this implementation? Basically, I'm looking for some intuition on how this works and if you can show in some manner how you deduce the implementation.


texts: Which combinations of pre-, post- and in-order sequentialisation are unique?

texts:
We know post-order,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

and pre-order

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

and in-order traversal resp. sequentialisation.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

One can easily see that neither describes a given tree uniquely, even if we assume pairwise distinct keys/labels.

Which combinations of the three can be used to that end and which can not?

Positive answers should include an (efficient) algorithm to reconstruct the tree and a proof (idea) why it is correct. Negative answers should provide counter examples, i.e. different trees that have the same representation.


texts: Time complexity of this solution to N-queens problem

texts:
I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of them). The relevant code is briefed below.

bool isSafe(int board[N][N], int row, int col)
{
    int i, j;

    /* Check this row on left side */
    for (i = 0; i < col; i++)
        if (board[row][i])
            return false;

    /* Check upper diagonal on left side */
    for (i=row, j=col; i>=0 && j>=0; i--, j--)
        if (board[i][j])
            return false;

    /* Check lower diagonal on left side */
    for (i=row, j=col; j>=0 && i<N; i++, j--)
        if (board[i][j])
            return false;

    return true;
}

/* A recursive utility function to solve N
   Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
    /* base case: If all queens are placed
      then return true */
    if (col >= N)
        return true;

    /* Consider this column and try placing
       this queen in all rows one by one */
    for (int i = 0; i < N; i++)
    {
        /* Check if queen can be placed on
          board[i][col] */
        if ( isSafe(board, i, col) )
        {
            /* Place this queen in board[i][col] */
            board[i][col] = 1;

            /* recur to place rest of the queens */
            if ( solveNQUtil(board, col + 1) )
                return true;

            /* If placing queen in board[i][col]
               doesn't lead to a solution, then
               remove queen from board[i][col] */
            board[i][col] = 0; // BACKTRACK
        }
    }

     /* If queen can not be place in any row in
        this colum col  then return false */
    return false;
}

/* This function solves the N Queen problem using
   Backtracking. It mainly uses solveNQUtil() to
   solve the problem. It returns false if queens
   cannot be placed, otherwise return true and
   prints placement of queens in the form of 1s.
   Please note that there may be more than one
   solutions, this function prints one  of the
   feasible solutions.*/
bool solveNQ()
{
    int board[N][N] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };

    if ( solveNQUtil(board, 0) == false )
    {
      printf("Solution does not exist");
      return false;
    }

    printSolution(board);
    return true;
}

From what I can tell, the recurrence is T(n) = n*T(n-1) + N*n, which leads to O((n+1)!). When one more recursive call is made, at least one more isSafe() should return false. So the number of recursive calls decreases by at least 1 each time. And for the overhead in isSafe(), since col rows has been filled already, there are at most min(col, N-col+1) iterations of for (i = 0; i < col; i++). But the for loop in solveNQUtil() runs a fixed number of N. That's why N*n exists.

But many people argue that N-queen runs O(n!) with recurrence T(n)= n*(T(n-1) + O(n)), such as here and comment on geeksforgeeks. So I start doubting myself.. surely O((n+1)!) != O(n!).

Could anyone here throw some light on this? Have been struggling with it for a while.


texts: What is the field studying the search and generation of computer programs?

texts:
This Github repo hosts a very cool project where the creator is able to, give an integer sequence, predict the most likely next values by searching the smallest/simplest programs that output that integer sequence. I was trying to approach the same idea using lambda-calculus instead of a stack-based language, but I was stuck on the enumeration of valid programs on LC's grammar.

Anyway, what is the field studying that kind of idea and how can I grasp the current state-of-art?


texts:
I'm reviewing for a computability test, and my professor has not provided solutions to his practice questions. I came up with a "solution" to this problem, but it really seems like my answer is wrong (since I call upon $\mathsf{Halt}$ twice)...

We are given this initial language for some machine $M$:

$\mathsf{2Strings} = \left\{ \left<M\right>\ |\ L(M)\text{ contains at least 2 distinct strings }\land M\text{ is a }TM \right\}$

And we are told to "[s]how that [the language] is recursive-enumerable." The problem title is Reduction, so I assume we are supposed to use that.

My solution is as follows:

Pass $\left<M\right>$ to the following reduction:
Create $w_1 \in L(M), w_2 \in L(M)$, so that $w_1 \not= w_2$, and let $M' = M$.
Pass $\left<M', w_1\right>$ to $\mathsf{Halt}$. If the answer is Yes, proceed to step 4. Otherwise, return No.
Pass $\left<M', w_2\right>$ to $\mathsf{Halt}$. If the answer is Yes, return Yes. Otherwise, return No.

Basically, this is my logic: We pass each of two distinct strings from $L(M)$ to $\mathsf{Halt}$ separately; if either one says No, our answer is No. If both say Yes, the answer is Yes.

Is my answer valid? More importantly, is it correct? If not, what should I do to fix it?


texts: Can there be functions in o(1) in algorithm analysis?

texts:
I saw a similar question to this one here but it's not quite the same as mine:

Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?

I've just started a course in data structures and introduction to algorithms and there's a question on a homework assignment whose answer is a little unclear to me:

Given $f:\mathbb{N}\rightarrow\mathbb{R}^+$, prove or disprove $f(n) = \Omega(1)\ \ $.

I'm a little conflicted about this because on one hand, I know that $\Omega(1)$ is the set of all functions $f$ for which there exist some $c,n_0\in\mathbb{R}^+$ such that for every $n > n_0 \in\mathbb{N}$, $f(n) \geq c$ . So wouldn't $f(n) = \frac{1}{n}$ not be considered an element in that set? No matter how we choose the positive constant $c$ there will always be some $n$ where $f(n) < c$ since $f(n)$ gets smaller as $n$ gets larger.

On the other hand, this is a computer science course and I'm not aware of an algorithm whose complexity is $\Theta(\frac{1}{x})$ so perhaps I'm overthinking this?


texts: Understanding an upper bound in the analysis of Karger's algorithm

texts:
I'm reading the wiki page of Karger's algorithm for a self-study of CLRS to get some and I'm confused by one of the bounds they have.

Here, under the section about finding all min cuts, they have this line $$(1-P(n))^{O(\log^{2} n)} \le (1-\frac{c}{\ln n})^{\frac{3}{c} \ln^{2} n}$$. I get that they are using the definition of big O to insert these constants, but what feels fishy to me is the choice for the constant in the exponent of $\log^{2} n$ of $\frac{3}{c}$. Why can't I just choose the coefficient to just be, $\frac{2}{c}$ and get a tighter bound? How do they know here that $\frac{3}{c}$ is the smallest coefficient that may be chosen?

I understand the rest of the argument, for the record (They're using $e^{x} \ge 1+x$)


texts:
I have been trying to solve this question and am kinda stuck. Wondering on how to proceed and finish this proof. Prove that the language $ L = \{a^{2^n} | n >= 0\} $ is not regular. I have been trying to use the pumping lemma but am stuck at:

Suppose L were regular, let p be the pumping length given by the pumping lemma. $ w_p = 1^{2^n} $. Clearly, $ |w_p| >= p $ and $w_p$ is in L. So, by the pumping lemma, there must be some choice of x, y, z satisfying the conditions of the pumping lemma; $ |xy| <= n $ and $y > 0$.

I am stuck here, I do not how to proceed with solving the $(xy^iz)$ part.

Thanks


texts: How do binary trees use memory to store its data?

texts:
So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists (not linked lists) make use of static arrays and when data is appended to the list, if there is no room, a new static array is created elsewhere in memory larger in size so more data can be stored.

My question is, how do binary trees use memory to store data? Is each node a memory location which points to two other memory locations elsewhere...not necessarily contiguous locations? Or are they stored in contiguous blocks of memory too like a static array or dynamic list?


texts: How to apply the pumping lemma to $\{0^m 1^n \mid 2n \leq m \leq 3n, m,n \geq 0 \}$?

texts:
I'm not really sure the how you would go about proving this language isn't regular with the pumping lemma:

$L= \{0^m 1^n | 2n \leq m \leq 3n, m,n \geq 0   \}$

Does this indicate that $S = 2$, so we start by by using a string $\geq 2$?


texts: What is the bit complexity of Gaussian eliminaton over $\Bbb F_q$?

texts:
Given matrix $M\in\Bbb F_q^{n\times n}$ with rank $r$ what is the complexity of converting to row-echelon form?

  Is it $O(n^3\log q)$ or $O(n^3q)$ bit operations?

Technically $O(n^3)$ row operations in $O(\log q)$ bit words should be $O(n^3(\log q)(\log\log q)^2)$ bit operations in worst case when $q$ is prime.

What I am confused about is

when $q$ is prime power
incorporating complexity of modular operations.


texts:
I need to find N! (mod 232-5) such that 0 ≤ N ≤ 264 for i cases, 0 ≤ i ≤ 1000 in 1 sec.

Credits: https://dmoj.ca/problem/factorial2

I am aware that I only have to handle 0 ≤ N ≤ 2 ≤ 232-6 because once N ≥ 232-5, N!≡0 (mod 232-5) . A naive solution would take O((232-6)*1000). I have also tried using Wilson’s Theorem and a naive solution, which would run in approximately O(4000000000*1000) time (Calculated from the highest point when O(N) intersects with O(232-5-N)log(N))).

I cannot find a solution to this problem with a fast enough run time.
Any help would be appreciated.


texts: Is the set of LL(*) grammars the same as the set of CFG grammars?

texts: Is the set of LL(*) grammars the same as the set of context-free grammars?


texts: Why isn't it simple to count the number of words in a regular language?

texts:
Given a DFA, A, let L(A) denote the number of words A accepts.
I think it's easy to calculate L(A):
Translate the encoding of A into a regular expression.
If the Kleene star appears anywhere in the expression - the language is infinite.
Else:
Go through and count all the combinations of words that are possible to make using the expression (basically if there is a + operator on the expression, multiply the amount of legal words by the amount of strings connected by the +..)

Is this wrong?
Thanks in advance


texts: Is there any difference between Time Complexity and Running time?

texts:
Is time complexity and running time of the program/algorithm one and the same thing?
Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that program took to run. So, can we say that running time is same as computer complexity?