texts: How to Compute the Fixed Point on a DataFlow Lattice

texts:
Wondering the general overview of how to compute the fixed point on a program's dataflow lattice.

A fixed point of a function $f(x)$ is one where the output of the function equals the input, so:

$$f(x) = x$$

Given $f$ is an order preserving (monotonic) function
$x ⊑ y \Rightarrow f(x) ⊑ f(y)$, in this presentation, they have $x_\bot$ be the least fixed point of $f: L \to L$, so $f(x_\bot) = x_\bot$, where $L$ is a program lattice. Then they say:

  Now, let $x_0 = \bot$ [the end of the lattice] and $x_i = f(x_{i−1})$

  By induction, $x_i ⊑ x_\bot$.
  Also, the chain $x_i$ is an ascending chain.
  If $L$ has no infinite ascending chains, sooner or later $x_i = x_{i+1} = x_\bot$

I'm wondering what this means. What happens algorithmically (the high-level steps) when we are iterating toward a fixed point. In the presentation they say "Do computation by simulating execution of program until reach fixed point".

This doc says "In this situation [data flow], the mathematical function is the flow function [so $f$], and the fixed point is a tuple of the dataflow analysis values at each point in the program (up to and including the loop)". They define flow function as a map from the dataflow info immediately before to after the program point / instruction.

So essentially, we divide the program into nodes or points where each point is an instruction/statement. We create a function showing the change of values from before and after each point (in and out, the flow function). We then iterate on the values somehow, that's where I'm unclear about. Wondering if we are iterating through the program points, calling $f$ for each point, or if we stay at one point and iterate on it with some sort of input until we reach a fixed point. Then wondering how that works. Not sure how the iteration works, or how $x_\bot$ works (if its part of some subset of the program points $L$ for each point (kind of like a neighborhood) or what.


texts: Determine what is the best order for running filters on a dataset

texts:
I'm trying to figure out what is the optimal order for running a sequence of tasks in a pipeline.

Each task filters a percentage of the dataset.

Assuming I got the tasks t1, t2, t3, ..., ti and a dataset. Each task have an execution time per item in the dataset denoted as e1, e2, e3, ..., ei and each task filters a certain percentage of the dataset denoted as f1, f2, f3, ..., fi.

What is the optimal sequence of tasks to achieve the minimum running time ?

I've first tried to examine two tasks - t1 and t2 with their representative execution time and filter percentage - e1, f1 and e2, f2.

I want to find the ordering predicate for getting e1 + f1*e2 < e2 + f2*e1. I'll get the condition e1 / (1 - f1) < e2 / (1 - f2). And I guess that from here I'll need to prove it in induction, but I'm stuck because the equation is some kind of recursion.


texts: How to change a grammar so that it can be unambiguous?

texts:
The original grammar is
$$ S \to SaS \mid SbS \mid ScS \mid d $$
My answer is
$$ S \to daS \mid dbS \mid dcS \mid d $$
Is that correct?


texts: Computational complexity classes not based on input size?

texts:
Computational complexity classes, such as $P, NP, PSPACE$, etc, are defined according to the factory by which computational time increases, as the input size $n$ increases.

But this doesn’t allow us to talk about the complexity of a particular problem (i.e. for a particular $n$).

For example, I believe that “generalized chess”, i.e. on an $n\times n$ board, is $NP$-hard. But this only tells us something about how the computational time of generalized chess increases as $n$ goes to infinity. It doesn’t tell us anything about how hard $8\times 8$ chess is.

On the other hand, simply giving a number, denoting the amount of steps required to solve $8\times 8$ chess with a Turing machine, is not very insightful.

Is there a different classification-scheme/framework for analysing the computational complexity of problems, that doesn’t refer to the input size $n$, that allows us to analyse e.g. the complexity of $8\times 8$ chess?


texts: Show that $0^i$ where $i$ is a power of 2 is not context free

texts:
I'm having difficulty trying to use the pumping lemma in order to show that $L= \{0^i \mid \ i \text{ is a power of 2 }\} $ is not context free.

I"m starting by stating that $ s = 0^p$ and then $ s = uvxyz $ and that in order for a language to be context free it must follow the 3 conditions: $|vy| > 0$ , $|vxy|\le p$ and for some $m \ge 0, \, uv^mxy^mz \in L$.

So I guess I"m struggling on how pumping something $uv^mxy^mz$ will not be in $L$. Would I try and use something along the lines of pumping down $uv^0xy^0z$ for this to not be in $L$. Any help greatly appreciated!


texts: Algorithm to shrink a DFA by introducing nondeterminism?

texts:
This is somewhat related to another question I asked, but I feel it's different enough to warrant its own question.

I'm doing research where I'm trying to find the structure of complements of a certain class of finite languages. It's easy for me to get the minimal DFAs accepting these languages, but I'd like to examine what kind of structure NFAs accepting these langauges have, particularly how nondeterminism helps with state-size of the automata (the DFAs are exponentially large).

The problem is, the main NFA reduction technique uses equivalences, which won't produce any reduction if I start with a minimal DFA (since it's basically using the same technique). If I start with a non-minimal DFA, it just spits out the minimal DFA.

What I'm wondering is, are there algorithms which can start with a DFA, and shrink it into a smaller NFA by introducing nondeterminism? Are there "standard techniques" to do this?

I have found preorder reductions, which look promising but hard to implement. I'm open to many suggestions.


texts: Is no language with the non-primes property context-free?

texts:
A language $L$ is said to have the "no primes" property if:

For every prime $p$ there are no words $w$ in $L$ s.t. $|w|=p$.
For every non-prime $m$ there is at least one word $w\in L$ of length $|w|=m$.

Given a language $L$ that has the no primes property, must $L$ be non-context-free?

Intuitively I believe yes, since the languages of all primes is not context free. But how can I prove this for every language that has this property?

I thiught proving using the sequence of lengths of words from any such language $L$, but this sequence is bounded by (at most) 3 (if 1 is consideres non prime, otherwise bounded by 2).

I also thiught proving by using the pumping lemma, but since I have no information on $L$ I am not sure if its possible.

Is there another method to prove so? Or a counter example that dissproves this?


texts: Conceptualizing a balance in a DFS traversal

texts:
I'm trying to use the concept of DFS traversal to go through a cycle, and attempt to get a balance of 0 in the end. Each student either owes or is owed some money, so I'm trying to go through all of said students and make sure each one can pay the other.

  The input for your algorithm consists of two lists $owing$ and
  $friendship$. The length of the list $owing$ is the total number of
  students; $owing[i]$ is the amount that student $i$ is owing $(0 \leq i \leq
 len(owing)-1)$, and it is an integer than can be positive (owing
  money), negative (owed money) or zero. The list $friendship$ is a list
  of pairs that represent the remaining friendships, i.e., a pair $(i, j)$
  means student $i$ and student $j$ are still friends and can still talk and
  give money to each other. Devise an efficient algorithm which, given
  the two input lists, returns whether or not it is possible for everyone to get
  even.

I've attempted to write psuecode for it, and it runs in O(|V + E|), the normal runtime of a DFS. I was wondering if it's correct, and whether there's a way to have it run more efficiently?

The general logic behind it is, visited all members in the owing list but paying the debts through friendship. Check that the total sum all frienships in this path can total up to 0. If it doesn't returns failure.


texts:
The project I'm working on has a number of objects arranged in overlapping sets. I need to classify them by whether they have a trait or not, using pre-classified objects that they are connected to (through shared set membership). I.e., the objects within the same set are likely to share whether they have that trait. The training data only consists of whether some objects have the trait or not.

To illustrate by example:

Green and red circles represent pre-classified objects (with having and not having the trait respectively). White circles are unclassified.
Objects A, C, D and E are likely to have the trait, and thus should have a positive score, because they are in common sets with other objects which are known to.
A should have a better score than C because there is more certainty (C's unclassified neighbor might or might not have the trait).
Similarly, D should have a higher score than A.
E is likely to have the trait because all of its neighbors are.
F and G should have a neutral score, because we don't know anything about F, and G has equally conflicting information.

I'm looking to sort all unclassified objects by score (likelihood to have the trait), which in this example would roughly be D, A, E, C, F, G, B, or at least get the top N objects with the highest score.

My set size is about 50 million objects across 10 million sets. The training size set (number of pre-classified objects) can vary from 1 to a few thousand. The objects are pretty well connected - the biggest "connected subgraph" contains 90% of all objects.


texts: Give a specific case where calling a polynomial time function n times gives an exponential time algorithm

texts:
We were asked this question in exam and I am not satisfied with the answer the teacher gave.

Let me justify my point of view. Let there be a polynomial time function having time complexity $n^{c_1}$. If we call the function polynomial times, say $n^{c_2}$ times, then the time complexity of the algorithm becomes $n^{c_1+c_2}$. Which is clearly polynomial.

Now the answer our teacher gave. Let there be a subroutine $S_i$ with time complexity $2^{i-1}n$ where $n$ is the input size. Therefore the time complexity of $S_n$ is $2^{n-1}n$. Which is exponential.

I am not satisfied with this answer because firstly the variable $i$ seems shady. We are not even calling any subroutines polynomial times, we are just assigning some value arbitrarily.

If our teacher's answer is correct could someone elaborate? If not, is there any answer to this question?


texts: What is required for universal analogue computation?

texts:
What operations need to be performed in order to do any arbitrary analogue computation? Would addition, subtraction, multiplication and division be sufficient?

Also, does anyone know exactly what problems are tractable using analogue computation, but not with digital?


texts: Is P^SAT with only one query equal to the union of NP and coNP?

texts:
I have a following problem:

Let $P^{SAT[1]}$ be a class of problems decidable by a deterministic polynomial Turing Machines with SAT oracle. (only one question to oracle).

Assume that:
$\mathrm{co}NP \neq NP \neq P$

Decide if $coNP \cup NP \neq P^{SAT[1]}$ or $\mathrm{co}NP \cup NP = P^{SAT[1]}$.

I know how to show that $\mathrm{co}NP \cup NP \subseteq P^{SAT[1]}$.

But I have no idea what about inverse direction. Any tips?


texts: is there a sorting algorithm of order $\log n!$

texts: Is there any sorting algorithm that takes order of $\log n!$ in the worst case? I know that this is the lower bound for sorting algorithms using comparison based sorting. I know that there are algorithms of order $n\log n$, but since $n!$ grows much slower than $n^n$, I wish to know of there is any algorithm of this order.


texts:
How can we convert a given Turing Machine into a Random Access Machine? I understand that we can use the transition function to come up with a sort of algorithm but how can we translate all of it into a set of instructions (load/add etc).
For example, here's a TM:
M = ({q 0 , q 1 , q accept , q reject }, {0, 1}, {0, 1, t}, δ, q 0 , q accept , q reject )

having a transition function as follows:

Now, how can I formulate a set of RAM instructions from this?
Sample Solution:


texts: Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms

texts:
In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity.

In practice, what is needed is an algorithm that would work fast on a finite (although possibly very large) number of instances.

An algorithm which works well in practice on the finite number of instances that we are interested in doesn't need to have good asymptotic complexity (good performance on a finite number of instances doesn't imply anything regarding the asymptotic complexity). Similarly, an algorithm with good asymptotic complexity may not work well in practice on the finite number of instances that we are interested in (e.g. because of large constants).

Why do we use asymptotic complexity? How do these asymptotic analysis related to design of algorithms in practice?


texts: Time complexity to check if there is an edge between two nodes in an adjacency list

texts: I know that the time required to check if there exists an edge between two nodes in an adjacency matrix is $O(1)$ because we can access it directly (i.e: $M[i][j]$). However, I didn't really get why time complexity in an adjacency list to check would be $O(|V|)$, where $V$ represents the vertices. Shouldn't it be $O(|E|)$ instead? Because in the worst case, it needs to traverse through all of the elements (edges) in a linked list of a certain vertex.


texts: Ideas on reducing Traveling Salesman to Metric Traveling Salesman?

texts:
I want to show a polynomial reduction from TSP to Metric TSP. I know the rule is:
$(G, k) \in TSP \iff (G', k') \in MTSP$ where $G$ is some graph, and $k$ is some bound.
It seems like whatever I map $G$ to, the way I map $k$ to $k'$ should make it such that if $k$ is the length of the minimum path, $k'$ is also the length of the minimum path.

For example: Let's say $(G,11) \in TSP$ and 11 is the length of the minimum path. I have some method of changing my graph to $G'$ that involves shrinking a bunch of edges, but $k$ is kept the same. Now, the minimum path in $G'$ is 10. Then it would be the case that $(G, 10) \notin TSP$ but $(G', 10) \in MTSP$--so that wouldn't be an appropriate reduction. It would be the case similarly if I embiggened many edges in $G$ to $G'$, so that the minimum path was now larger.

Thoughts: it's simple if I just multiply every edge cost by a given number, to multiply $k$ by that much as well (this won't yield a metric graph, though). If I don't multiply every edge, then I have no idea how to change $k$ because I don't know whether edges I changed are in the Hamiltonian cycle. I thought about making every edge cost 1 (or 1's and 2's), but again I wouldn't know how to change $k$.

Any hints on what I should be doing to change the edge costs in such a way that I also know how to change $k$? (This is homework, so I don't want a complete solution, please.)


texts:
What is min # of pairs req’d for sufficient confidence from a given pairwise ranking algorithm?

Note: I'm a little rusty and don't have a comp sci background, just an undergrad math deg about 10 yrs ago, which I don't use in my day job much. But I have an issue which I could really use help understanding. If you have any insights, they'd be greatly appreciated ;). Here we go....

Assumptions:

N users
K items Aj, j=1,…,K to be ranked
Each of the N users has defined an ordinal ranking of the K items in advance, that is, for each user i, there is a ranking R(i) = (A1,…,AK), where Aj represents one of the K items and Aj < A(j+1).
These rankings are stored in tables, i.e. we know these rankings in advance.
Call the aggregate ranking of item j simply the average of its rank for each of the N users. So for example if N=2, and the two users have an item ranked 4th and 8th respectively, this item’s aggregate rank is (4+8)/2=6th. This then defines an aggregate ranking of K items. This is what we want to predict with our chosen algorithm.
Each of the N users will be asked to compare X pairs.
Let’s assume we use a very strong pairwise ranking algorithm (pick your favourite) to select what pairs to show each of the users (i.e. it can dynamically select pairs to display to users that take advantage of properties of transitivity)
Assume that when the algorithm is run for any particular user, it simply consults the table of predefined rankings for this user and makes the selection.
For any resulting predicted ranking output by the algorithm, we can define some measure of the error, or difference between the predicted ranking and the actual aggregated ranking. Let’s call this rank error (e.g. perhaps the average deviation in the location for items ranked would suffice).

Problem: How many pairs do we need the algorithm to look up for each user to minimize this rank error?

To get this into familiar confidence interval terminology, let’s give this problem some numbers (these are actually the numbers I care about but became interested in the problem in general).

N=10 users
K=15 items
We want to predict the aggregated ranking of the top 3 ranked items only
Now only have one parameter, X = number of pairs algorithm queries for comparisons

To do this, we could simply run the algorithm a very large number of times (10^whatever, i.e. a Monte Carlo simulation) and assign a value of 1 for each time the algorithm's predicted top 3 equals the actual top 3, and a value of 0 otherwise. To get different trial simulations we could vary the input (i.e. if the algo will produce the same result) randomly. The question then would be, what is the frequency of 1s in running this simulation? This can be our measure of confidence. So then the question becomes, for a given level of confidence, say 90%, what is the value of X?

One thing that seems intuitively clear is that the more dispersion there is between the different user's rankings, the less impact increasing N (# of users) would have on confidence levels. That is, if you imagine that all N have exactly the same ranking (i.e. zero dispersion), you'd only need to present them with at most the K*(K-1)/2 unique pairs to get a perfect ranking with 100% confidence. On the otherhand, if you assume that N=K! where each of the N users has each of the unique possible rankings, you would converge to 100% confidence very very slowly. Interestingly, in fact, you could argue that if the goal was to select a top 3 in this case, you'd be no better off than picking 3 at random in which case, you need zero users input! Thought that was interesting.


texts: Relation beetween log-space reduction and polynomial time reduction

texts:
I read somewhere that given two languages A and B, if A <=(log) B, then A <=(P) B (with <=(log) the log-space reduction and <=(P) the polynomial time reduction), but I'm not sure about the proof.

Could someone help me with that please.

Thanks.


texts:
What is the best algorithm to compute p-dominating set?

The p-dominating set problem is a parameterized version of minimum dominating set in which the problem takes a parameter $k$ also as an input, and the problem is now whether there exist a dominating set of cardinality at most $k$.

I know the problem is W[2]-hard so there is no chance of getting a $f(k) n^c$ running time algorithm unless the parameterized hierarchy collapses.


texts: What is meant by 'simultaneously computing' all partial derivatives of an arithmetic circuit?

texts: I was reading the proof that for every arithmetic circuit of size $s$ and depth $d$ we can find a circuit $D$ of size $\mathcal{O}(s)$ and depth $\mathcal{O}(d)$. I do not understand what is meant when we say that we can construct a circuit which 'simultaneously computes' all partial derivatives of a function. Does simultaneously computing mean that there are multiple output gates or does it mean that every partial derivative is computed by some sub-circuit of of $D$.


texts:
I have an unweighted and undirected graph, and I want to divide this graph into two connected components by removing some vertices. The main objective is to minimize the number of vertices which must be deleted in order to partition the graph into two sub graphs.

How can I accomplish this ?

The first thing coming to my mind is Ford Fulkersonalgorithm, but I think it is not appropriate for this problem.


texts:
I've read up on Finite State Automata in a lot of different books on compiler construction (two of which are actually called Compiler Construction) and I'm kind of at a loss. I understand the idea of moving from state to state and having a state that is accepted. What I don't understand is why in the world this theory is regurgitated in such an obscenely convoluted way?

If you were to tell me that the point of FSA within a compiler is for Lexical Analysis and that its purpose therein is just to go character by character and determine whether or not a word is an identifier, keyword, or other token, I would be completely confident in my understanding. Problem is that in every chapter of finite state automata I have to go over 50 pages of rigorous notation, differences between non-deterministic and deterministic finite state automata (including separate notation where Epsilon is three different things based on its styling) and a dozen or more of these graphs:

My question is this: Do I need to understand more than this to write a Compiler? Is there something unique about FSA that I'm just completely missing? Or is this just an over complication of a simple concept in regards to creating a compiler?


texts: Applications of Depth-First Spanning Tree

texts: I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that make use of the depth-first spanning tree?


texts: Can we use Big O notation to predict actual running time of the algorithm on machine?

texts:
As per my understanding, a program can take a different amount of time to run on different machines because it is dependent on hardware. So we use big O notation which is independent of hardware to compare the performance of two algorithms as the input grows.

I am working on an algorithm which has a complexity of $O( X + Y )$ and it takes a number as an input. My advisor has asked me to collect actual runtime(on the same machine) of the algorithm with different numbers as an input. Then determine coefficients a, b and c such that

$runtime=a.X + b.Y + c$

and use this equation to predict runtime for other inputs.
(for instance, consider BFS, in which case $X$ and $Y$ could be replaced by $V$ and $E$ and it takes a source vertex as an input. Now I am asked to record runtimes of the BFS execution using different source vertices as an input and determine the coefficients. The claim is, using the same hardware and same graph but different source vertex I should be able to get a good approximation of the runtime.)

As per my understanding, this approach is incorrect as big O notations are meant for comparison, as the input grows. But my advisor argued that big o notation captures all the operations in the code and therefore there must exist coefficients a,b,c such that the above equation gives a good approximation.

Is the claim made in the above argument is correct?


texts: How does it demonstrate that the computational model of rewriting is adequate?

texts: How can I demonstrate that the computational model of rewriting is adequate? For example, with it, it is possible to compute any computable function.


texts: How to implement the regret matching algorithm?

texts:
My question is the following: How to calculate the regret in practice?

I am trying to implement the regret matching algorithm but I do not understand how to do it.

First, I have $n$ players with the joint action space $\mathcal{A}=\{a_0, a_1,\cdots,a_m\}^n.$
Then, I fix some period $T$. The action set $A^t\in\mathcal{A}$ is the action set chosen by players at time $t$. After the period $T$ (every player has chosen an action). So I get $u_i(A^t)$.
Now the regret of player $i$ of not playing action $a_i$ in the past is: (here $A^t\oplus a_i$ denotes the strategy set obtained if player $i$ changed its strategy from $a'_i$ to $a_i$)
$$\max\limits_{a_i\in A_i}\left\{\dfrac{1}{T}\sum_{t\leqslant T}\left(u_i(A^t\oplus a_i )-u_i(A^t)\right)\right\}.$$
I do not understand how to calculate this summation. Why there is a max over the action $a_i\in A_i$? Should I calculate the regret of all actions in $A_i$ and calculate the maximum? Also, In Hart's paper, the maximum is $\max\{R, 0\}$. Why is there such a difference?

I mean if the regret was:  $\dfrac{1}{T}\sum_{t\leqslant T}\left(u_i(A^t\oplus a_i )-u_i(A^t)\right),$
the calculation would be easy for me.

The regret is defined in the following two papers [1] (see page 4, equation (2.1c)) and [2] (see page 3, section I, subsection B).

A simple adaptive procedure leading to correlated equilibrium by S. Hart et al (2000)
Distributed algorithms for approximating wireless network capacity by Michael Dinitz (2010)

I would like to get some helps from you. Any suggestions step by step how to implement such an algorithm please?


texts: Can we make at most 3 comparisons in the closest points algorithm instead of 7?

texts:
Let's say I am using the divide and conquer algorithm outlined here, but I only want to return the minimum distance. I understand why that algorithm puts an upper-bound at 7 but I think that can be trimmed down further. I can't come up with a geometry of points where if you are comparing them in order by sorted y value you would need more than 3 comparisons to get the closest distance. A counterexample would be greatly appreciated.
Put more rigorously, here is what I am trying to prove:

Say I have points, p1, p2...p5 sorted by y values non-decreasing and their x values satisfy -delta <= x <= delta.
All points are either in Set A or Set B.
Points in Set A satisfy -delta <= x <= 0 and all of them are >= delta apart in distance.
Points in Set B satisfy 0 <= x <= delta and all of them are >= delta apart in distance.
Delta is <= to the minimum of these two values:

The smallest distance between points of Set A
The smallest distance between points of Set B

It is impossible to come up with an arrangement of points that satisfy these conditions so that p1 and p5 are the closest two points and the distance between p1 and p5 is less than delta.


texts: Why can't a server provide guaranteed service with only bounded nondeterminsm?

texts:
The wikipedia page Actor Model and Process Calculi History, presents the following claim:

  The semantics [of CSP] provided bounded nondeterminism unlike the Actor model with unbounded nondeterminism. However, with bounded nondeterminism is [sic] impossible for a server to guarantee service to its clients, i.e., a client might starve.

However, there is no citation provided for the claim. Carl Hewitt makes the same claim in this video, so it's not a mistake by a wikipedia author. Can anyone provide the source (or their own proof) of this assertion?


texts: Expander Graph - Is the following graph family an expander graph?

texts:
Consider the family of graphs of degree $6$ with vertex set $V_n=(a, b, c)$ for all  $0\leq a, b, c \leq n-1$ with $(a,b,c)$ being connected to $(a-1, b, c),(a+1, b,c), (a, b-1, c), (a, b+1, c), (a,b,c-1), (a,b, c+1)$, with all operations modulo $n$. Show that this  is not a family of expander graphs.

I've been struggling with this question for over a week.
I tried looking at from the algebraic perspective and show that the spectral gap is getting smaller as n(the number of vertexes) rise. But I got stuck a long the way and now I don't know if I'm on the right track at all.


texts: The use of binary search when determining whether a point lies inside a given convex hull

texts:
In an answer to the problem of determining whether or not a point lies inside a given convex hull, a thesis is mentioned, which says :

  For repeated queries with preprocessing allowed, we develop a special
  method that relies on the convexity of the polygon. Recalling Theorem
  3.5, the vertices of a convex polygon occur in angular order about any interior point. Find such a point O and consider the N rays from O
  that pass through the vertices of P. (Figure 4.8.) These rays
  partition the plane into N pie-shaped wedges. Each wedge is divided
  into two pieces by a single edge of P. One of these pieces is wholly
  interior to P, the other wholly exterior. Treating O as the origin of
  polar coordinates, we may find the wedge in which z lies by a single
  binary search, since the rays occur in angular order.

How would one do the binary search (assuming the convex hull's vertices are given in counter-clockwise order)?


texts: Is there an algorithm to add edges to a DAG to make it strongly connected with minimum cost?

texts:
I have a weighted DAG and a function computing the weight of edges that is not connected in the DAG. The weight of u to v equals to the weight of v to u.

I want to connect edges to make the DAG a single strongly connected component (any vertex in the new graph can reach any other vertex) with minimum total weights of added edges.

I know that the minimum number of added edges equals to $\text{max}(|source|, |sink|)$ but which vertex connects to which vertex so that the total weights is minimum?


texts: NP-completeness of solving quadratic equations over $\mathbb{Z}_2$

texts:
Let $\chi$ be a degree 2 equation over $\mathbb{Z}_2$ of the form:
  $$x_{i_1}x_{j_1} + x_{i_{2}}x_{j_1} + \cdots + x_{i_m}x_{j_m} + x_{k_1} + \cdots + x_{k_l} = b $$ for $ k_i \in \{1, \dots, n\}, b \in \{0,1\}$ for some $m, l \in \mathbb{N}$

  Prove that deciding whether a system of such equations has a solution is NP-complete.

So, we should to prove two things:

1) The problem $\in NP$

2) Another  NP-complete problem can be reduced to that problem.

I have no idea how to start. Please hint me. It is tempting to use $SAT$ problem, but, when I am trying to convert that problem I got stuck:
How to get $1$ (the truth value)?


texts: VC dimension of a combination of two hypothesis classes

texts:
I have found this exercise and I cannot solve it:

In $X=\mathbb R^2$, let's observe two models $H_1$ (rectangle with sides parallel to the coordinate axes) and $H_2$ (lines). We define a model $H_3$ such that every hypothesis is a combination of one hypothesis from $H_1$ and one from $H_2$.
Prove or disprove that the model $H_3$ has a larger VC dimension than the VC dimensions of the models $H_1$ and $H_2$.

From my lecture notes I know that the VC dimension of $H_2$ is $3$, and I have proven that the VC dimension of $H_1$ is $4$, but I don't know what method to use to get the VC dimension of $H_3$.


texts: Can we specify the pumping length while applying pumping lemma

texts:
In all the examples I have seen, the pumping length $p$ is not specified. The string is a pattern that somehow has the $p$. E.g. when proving $L=\{a^n b^n c^n | n \geq 0\}$ is not context free, we assume the string $s \in L$ has the form $a^pb^pc^p$, and continue.

Do we have to select such a general pattern?

E.g. Can I just say, $s=aaabbbccc$, where $p=3$, and reason continuing this?


texts:
Now my knowledge of this comes through watching The Imitation Game, a glance of a wiki article, and a couple of computerphile videos, so forgive me if it's obvious.

While watching the Imitation Game, I couldn't help but think that the Bombe that was being developed was just doing a naive search through all possible combinations, so there would be some days where you'd run through all 159 quintillion odd settings before you got to the right one. So why was it so good?

I understand that quite a few setting could be discounted, as the enigma machines couldn't map a letter to itself, but surely that's still quite a lot of settings to search through. And while it'll be faster than doing it by hand, it's still quite a lot.

So naturally, I'm guessing that one of my assumptions is wrong, and Turing and co. are in fact, smart cookies. What sort of algorithm are they using to break the cypher, or how are they filtering the possible iterations down?


texts: Finding Connected Components Dependent on Order?

texts:
It seems to me that the outcome of a connected components algo is dependent on the start vertex. Is this correct?

Say we had the graph

If we started our connected component search from the vertex on the upper right then we would end up with different set of connected components than if we started our search with the vertex in the upper left?

Is this correct?


texts:
I am given a list of $n>1$ arrays, where each array has fairly small number of elements (rarely above $5$). Also $n$ is quite small in practice (around $6$).

My problem is that I would like to efficiently map each element product to unique integer. Also, I would like to efficiently compute the integer, when I change the order of the arrays in the list.

I was thinking something in the line of integer factorization.

Take first $n$ primes ($p_1, p_2, ..., p_n$) and remeber the index of the array in the original list with $ind: A \rightarrow \mathbb{N}$. So the initial function would be $ind(A_i)=i$.

Also we denote with $a_{i,j}$ the $j$-th element of the $i$-th array in the list. So the function $F:A_1 \times A_2 \times \ldots \times A_n \rightarrow \mathbb{N}$ would be:

$$F(a_{1,i_1}, a_{2,i_2}, \ldots, a_{n,i_n})=\prod_{j=1}^{j=n}p_{ind(A_i)}^{i_j}$$

In more common words, we initially assign a prime number $p_i$ to array $i$ and raise $p_i$ to the index of the element in array $i$.

This guarantees us the uniqueness and also if we change the order of the arrays in the list, we just need to change the $ind$ function. But the problem here is that these products are fairly large and will overflow soon enough (even with using doubles).

Do you have any better idea how to enumerate these products without the large number constraint? I am implementing this in Java and I really would not like to use BigInteger implementation.


texts: Graph theory, $n$ people sitting around table

texts:
$n$ people want to have dinner together around a table for $k$ nights so that no person has the same neighbor twice.

How big can $k$ be in terms of $n$?
Does everybody get to sit next to everybody else?
How many seating arrangements are there?


texts: Find a weighted median for unsorted array in linear time

texts:
For days, I'm trying to figure out, whether it is possible to find an item in array which would be kind of weighted median in linear time.
It is very simple to do that in exponential time.
So let's say that we have an array, each item $x$ of this array has two attributes - price $c(x)$ and weight $w(x)$. The goal is to find an item $x$ such that
$$
\sum_{y\colon c(y) < c(x)} w(y) \leq \frac{1}{2} \sum_y w(y) \text{ and }
\sum_{y\colon c(y) > c(x)} w(y) \leq \frac{1}{2} \sum_y w(y).
$$
If the array was sorted by price, it would be simple:
Go from the first item one by one, count sum and if the sum becomes greater that half the total weight, then you found the desired item.
Could you give me some hint how to find such an item in linear time?


texts: How to bridge theory and implementation for while loops?

texts:
I'm working on my own little programming language for educational purposes, and I've run into a little bit of a problem. There are a few different solutions for it, but all of them seem inelegant - and from what I understand, unnecessary. But reading through the books I have and google searches, I can't find the elegant solution.

So, the problem is that I'm building off basic lambda calculus as I understand it. I have defined true/false as abstraction terms. I can combine these with functions to do if/then/else sort of behavior. The problem comes with loops. I can define a basic while loop via recursion, but in practice, that causes a stack overflow. As I understand it, the usual solution would be to perform Tail Call Optimization, but I don't see how I can - conditionals are defined in-language. Because of that, the compiler doesn't know that the body of the while loop is in tail position.

The dragon book focuses on implementing the loop assuming there is labels and gotos. I could certainly do that. It looks as though other languages that don't build in looping constructs at least build in conditionals and then do TCO. And I could certainly do that too. But my understanding is that as long as I can apply abstractions and perform reductions, then loops (and everything else) should be able to be built from those basic blocks.

So what am I missing? Or is this one of those cases where "you can model anything once you have X and Y" isn't the same as "you can model anything once you have X and Y on a real computer" and built-ins are necessary for practical purposes?


texts: What would be the process state in a multi threaded process, in which threads are in different states (running, waiting, blocked etc)


texts: How many cycles required in Instruction Level Parallelism?

texts:
L1: LD F1,0(R2)
L2: LD F2,8(R2)
L3: FADD F3,F1,F2
L4: SD F3,8(R2)
If the instruction fetch for L1 starts at clock cycle 1, in which cycle the instruction L4 access memory to store the data?
I am getting the answer as 8 but the correct answer is 11. Could someone help here?


texts: Decidability problem solved by an alogrithm step by step difference between Decision and decidable problem

texts:
How Decision procedure and Decidable problem are different from each other?
Both are having solutions in yes and no form. Is any else solution for both?


texts:
I'm taking an introductory quantum computations class and I am attempting to solve the following question(s), but we haven't touched on black box algorithms like this in class, and I honestly don't know how to solve the question at all.  Would it be possible to help me through the steps?

Question.  Consider the set of all functions $f:\{0,1\}^n \rightarrow \{0,1\}$ that are of the form $f(x_1,x_2,...,x_n)=x{_j{_1}} \oplus x{_j{_2}} \in \{1,2,...,n\}$ with $j_1 \neq j_2$.  Suppose we are given such a function as a black box (without information about $j_1,j_2$ and our task is to determine the set $\{j_1,j_2\}$.

(a) Show that any classical algorithm must male at least $\Omega(log(n))$ queries to f to solve this problem exactly.  (We have used the $\Omega$ notation to give lower bounds, defined as following: Suppose $f(n), g(n)$ are functions form the positive integers to the real numbers.  Then we say $f(n) \in \Omega(g(n))$ if there exists a positive, real c, and an integer $n_o$ such that for all $n>n_o, f(n)\geq cg(n)$.

We are also given the following hint: Note that the data that a k-query classical algorithm obtains is a k-bit string. Next, consider how big k needs to be so that there are enough k-bit strings to be uniquely assigned to each $\{j_1,j_2\}$.

(b) Give a quantum algorithm in the black box model that solves ths problems exactly with a single query to f.

Any possible assistance would be amazing.  Thank you!


texts:
It is not possible to losslessly compress all files of size $n$ using a single algorithm, as there are more files of size $n (2^n)$ than of size $p, p: p < n ( 2^n-1)$. Via the pigeon hole principle, if we only tried to compress files of size $n$ with a single algorithm, there would be at least one file it was impossible to compress.

If we wanted to be able to compress files with differing lengths $n_k$, the number of files of length $n_k$ we can compress for each $n_k$ becomes even smaller.

Today when reading a story about how a file that was several gigabytes when compressed uncompressed to one gigabyte, I had an idea for a universal compression algorithm.

Let $a_i$ be a compression algorithm.
Let $g_j$ be a file.
$|g_j|$ denotes the length of $g_j$.
Let $f(a_i, g_j)$ be a function that returns $(|g_j| - |a_i(g_j)|)$.

Let $S_N = \{g_j : |g_j| \le N\}$.

Let $A =  \{a_i : \, \forall \, g_j \in S_N \, \exists a_i in A : f(a_i, g_j) \gt \lceil(\log_2{\#A})\rceil\}$.
$\#A$ denotes the number of elements in $A$.

Let $m$ be the length of the label of the compression algorithm chosen. The first $m$ bytes of every compressed file denote the compression algorithm chosen.
$m = \lceil(\log_2{\#A})\rceil$.

Then you can compress all $g_j \in S_N$, by iterating through A until you find $a_i : f(a_i,g_j) - m \gt 0$.

Even better.

For each $g_j$, let $a_j$ be the corresponding compression algorithm.

Let $h(a_i, g_j) = f(a_i,g_j) - m$.

$${ \, \forall \, a_i \in A, g_j \in S_N, a_j = \displaystyle{ \underset{a_i \in A, g_j \in S} { \operatorname{argmax} } } \, (h(a_i, g_j))}$$

Is there a reason why the above is not done?

While the above is an algorithm, and one could argue that the pigeon hole principle thus applies, this does not imply what it may at first seem to imply.  The above algorithm call it $a^v$ is a little different.

Let $a_i: S_N \to Y_N^i$ denote that algorithm $a_i$ maps a family of files $(S_N = \{g_j : |g_j| \le N\})$ is mapped to another family of files $Y_N = \{y_j : y_j = a_i(g_j)\}$.

$\forall a_i \in A, a_i: S_N \to Y_N^i$.
However, $a^v : S_{N+m} \to Y_{N+m}^v$.
So $a^v$ compresses a different family of files from $a_i \ in A$.

The pigeon hole principle merely states that $a^v$ cannot compress all files of length $N+m$; this is irrelevant, since $a^v$ only intends to compress a small subset of files of length $N+m$ (those whose first $m$ bits are the labels of some $a_i \in A$.


texts:
I am curious about utilization calculation in the bitmap protocol. especially if there's a difference between if only station 0 wants to broadcast(and the others doesn't) or only some other station want to broadcast(but the others doesn't)

an example of a problem regarding this: in a bit map protocol with 10 station(numbered 0-9). knowing that the contending time is t and the length of each broadcasting frame is 20t.

a)what is the utilization of the network if all of the stations want to transmit in every time slot?

b)what is the utilization of the network if only station 0 wants to broadcast and the others doesn't?

c)what is the utilization of the network if only station 2 wants to broadcast and the other doesn't?

this is what i tried

a)in the beginning of the contending time, 10 stations want to broadcast so: $\frac{20*10p}{20*10p+1}$

b)$\frac{20*10p(1-p)^9}{20*10p(1-p)^9+1}$

c)$\frac{20*10p((1-p)^9)^3}{20*10p((1-p)^9)^3+1}$

explanation for b and c: only one station wants to broadcast, and in c there are 3 additional points in time we can not broadcast(0,1,2)

i tried looking on this site and on other sites for this topic, but with no luck sadly. there's not much information regarding calculation of utilization of the bitmap protocol, especially single stations in the network.


texts: Construct a PDA for the complement of $a^nb^nc^n$

texts:
I am wondering if this is even possible, since $\{a^n b^n c^n  \mid n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n  \mid n \geq 0\}$ from the rest of $\{a^*b^*c^*\}$ might as well accept it, which sounds contradictory to me.

I guess I need to take advantage of the non-deterministic nature of PDAs but I'm out of ideas. If you could offer some advice I would very much appreciate it.


texts: Decision if there exists a path between $s$ and $t$ of length $k$

texts:
I conisder a problem:

  It is given a graph $G$, vertices $s,t$, $k$- length of the graph. Prove that decision whether there is a path between $s$ and $t$ of length $k$ is NP-complete.

Please note that in our problem we have a path, not a **simple path* **

*It is trivial when we have a simple path (define as sequence of vertices where every vertice occurs at most once (there is no cycle) ).

I don't know how to start. I cannot come up what's problem I should reduce. Please hint me.


texts: Density of uniform distribution over two disjoint squares

texts:
A probability distribution $P$ over $X \times \{0, 1\}$. $P$ can be defined in term of its marginal distribution over $X$ , which we will denote by $P_X$ and the conditional labeling distribution, which is defined by the regression function
$$
\mu(x) = P_{
(x,y) \sim P}
[y = 1 \mid x]
$$
Consider a 2-dimensional Euclidean domain, that is $X = \mathbb R^2$, and the
following process of data generation: The marginal distribution over $X$ is uniform over two square areas $[1, 2] \times [1, 2] \cup [3, 4] \times [1.5, 2.5]$. Points in the first
square $Q_1 = [1, 2] \times [1, 2]$ are labeled 0 (blue) and points in the second square
$Q_2 = [3, 4] \times [1.5, 2.5]$ are labeled 1 (red).

Describe the density function of $P_X$, and the regression function, Bayes predictor and Bayes risk of $P$.
In the image, I have defined the Probability density function. I am having trouble in figuring out the pdf of this function in 2 dimensional space.


texts:
I know that monotone 3SAT is NPComplete. Also, 1 in 3SAT is NPComplete. I think  both conditions together also leave the problem NP Complete (need confirmation).

If possible can someone please help with the smallest non trivial problem of this form that is unsatisfiable. Would be grateful.


texts: L = {w belongs to {0, 1} * ∣ w has at most three 0’s}. Why is this regular language?

texts:
L = {w belongs to {0, 1}* ∣ w has at most three 0’s}. Why is this regular language?

According to pumping lemma, what I think is that....
Suppose $x$=$0^2$, $y$=$0^1$, $z$=$1^n$ ($w=xyz$=${0^2}{0^1}{1^n}$),  then if we pump $y$, we may have more than three $0$s. What am I missing?


texts: Some confusion about segment tree and line sweep method for finding area of union of axis parallel rectangles

texts:
I am having some confusion about finding the area of union of $n$ axis parallel rectangles in $O(n\log n)$ by the line sweep method. The following pictures are from the book of Shamos and Preparata.

In this case one needs to find the total height of the shaded region efficiently. So initially build a segment tree with the y-coordinates.This can be done in $O(n\log n)$. (Sorting $O(n\log n)$ and building the tree $O(n)$). The following pseudo code calculates the area.
Here $b_i$ and $e_i$ are respectively the minimum and maximum ordinate at $X[i]$. $m[v]$ is the contribution of interval associated with node $v$. The code for INSERT is

PROCEDURE INSERT(b,e;v):
    if(b <= B[v] and $e >= E[v]) then
        C[v] = C[v]+1
    else
     if(b < floor((B[v]+E[v])/2)) then
         insert(b,e;LSON(v))
     if(e > floor((B[v]+E[v])/2)) then
         insert(b,e;RSON(v))
     UPDATE(v)

DELETE has similar structure And procedure for UPDATE (at line 9) is

PROCEDURE UPDATE(v) :
    if (C[v] != 0) then
        M[v] = E[v]-B[v]
     else if(v is not a leaf node) then
        M[v] = M[LSON(v)] + M[RSON(v)]
     else
        M[v] = 0

I do not understand how $m[root(T)]$ is the total height of the shaded region. It would also include the height of the 'not shaded' region and therefore computes the total area swept by the sweep line during two consecutive event points, not the actual area of the intersected rectangle. Can someone please help me understand this. Thank you. Also if some one can provide the link of the original papers (by Victor klee and Bentley), it will be much appreciated. I have looked through internet in vain.


texts: Is there any research on allocating memory across multiple non-contiguous regions?

texts:
From my understanding, malloc and-the-like allocate contiguous blocks of memory. It then returns to you the start address of the memory block.
This (and other things) leads to memory fragmentation where, after allocating/freeing many times, you have holes where there is unused memory that can't be accessed.
I am imagining that one way to mitigate this problem is to have malloc return not just a single address, but an array of addresses and sizes for each address. So it would give you back several non-contiguous regions of memory, linked together which for all intents and purposes would feel like a single piece of memory, or you could treat it as such (for example, having arrays use this system).
Does any language or system do anything like this? Has anyone researched this? If not, why not? What are the potential problems with this approach?


texts: Hilbert's 10th Problem and Chaitin's Diophantine Equation "Computer"?

texts:
In Chaitin's Meta Math! The Quest For Omega, he briefly talks about Hilbert's 10th Problem. He then says that any Diophantine Equation $p=0$ can be changed into two equal polynomials with positive integer coefficients: $p=0 \iff p_1 = p_2$.

Then he says that we can think of these equations like a "computer":

  Diophantine Equation Computer:
  $$L(k,n,x,y,z,...)=R(k,n,x,y,z,...)$$
  Program: $k$, Output: $n$, Time: $x,y,z,...$

With left side $L$, right side $R$. He says $k$ is the program of this computer, which outputs $n$. He also says that the unknowns are a multi-dimensional time variable.

What confuses me is that he then says that Hilbert's 10th Problem is clearly not solvable when viewed in this way. He basically says "because of Turing's Halting Problem". But I don't see the connection (I'm just beginning to learn the theory). I was hoping someone could more clearly explain what Chaitin's point is here.

I know that Turing's Halting Problem basically states that you cannot predict when a program will halt before it actually halts (given a finite amount of time). What is the application to Hilbert's 10th Problem, using the notation laid out by Chaitin?


texts: Why is the number of comparisons in a BST missing key lookup about 2 ln N?

texts: In (An Introduction to the Analysis of Algorithms) by Philippe Flajolet and Robert Sedgewick it's written that: Insertions and search misses in a BST built from N random keys require ~ 2 ln N (about 1.39 lg N) compares, on the average. I didn't get it well, even after I read their explanation, can you help to understand it by simplifying the idea to me? I mean why do we have 2 ln N compares?


texts:
Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=x_i) =p_i$.

More specifically, I assume $A$ can generate a uniformly distributed real number in the interval $[0,1]$ in a constant time, and try to characterize the distributions $P$ which can be sampled in $o(|X|)$ time.

For example, if $P$ is the uniform distribution, I can assign to each element of $X$ a string from $\{0,1\}^{\log(n)}$, then sample each bit uniformly (toss of a coin) and independently, which means I can sample in $O(\log(n))$ time. Are there distributions such that any algorithm requires $\Omega(|X|)$ time? Are there known results in this direction?


texts: fast and stable x * tanh(log1pexp(x)) computation

texts:
$$f(x) = x \tanh(\log(1 + e^x))$$

The function (mish activation) can be easily implemented using a stable log1pexp without any significant loss of precision. Unfortunately, this is computationally heavy.

Is it possible to write a more direct numerically stable implementation which is faster?

Accuracy as good as x * std::tanh(std::log1p(std::exp(x))) would be nice. There is no strict constraints but it should be reasonably accurate for use in neural networks.

The distribution of inputs is from $[-\infty, \infty]$. It should work everywhere.


texts: Whether language of all turing machines is decidable or undecidable or semi-decidable?

texts:
I recently came across this language:

$L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$

It was asked in the question to find out whether language L is decidable or undecidable.

As far as I could reason out, language L is the set of all recursive enumerable languages or set of all turing machines.

But I can't figure out whether this language is decidable or not.

Can anyone please help me out??

Thanks in advance!!


texts: Why doesn't subset sum solution violate Exponential Time Hypothesis?

texts:
The quickest algorithm for solving subset sum currently is $2^{n/2}$ (via Wiki).  Why doesn't this violate the Exponential Time Hypothesis which states that “there is no family of algorithms that can solve 3-SAT in $2^{o(n)}$ time.”

Couldn't a 3-SAT problem be translated to a subset sum problem in polynomial time and then solved in $2^{n/2}$ time.  What am I missing here?


texts: Kolmogorov complexity of a sequence of prime numbers

texts:
Let's say $p_1, p_2, p_3, \ldots $ is the increasing sorted sequence of all prime numbers. Prove that there exists a constant $n_0 \in \mathbb{N}$, so that for all $n \ge n_0$:
  $$K(p_n) < \log_2(p_n) − 2.$$
  Hint: Prime number theorem: $p_n \in \Theta (n  \ln n)$.

I think, I could have a program A, which generates $p_n$ in $n\ln n$. I could just give A the index of my prime number and it would generate it.

Another idea of mine was to prove it by contradiction and assume the opposite is true but I can't really make that work.
My biggest problem is that I can't find an upper limit to the representation of prime numbers and start from there. Normally I'd just use the factorization for integers…

Any help is appreciated!


texts: Finding the two largest of five small integers as quickly as possible

texts:
I use a variation of a 5-cross median filter on image data
on a small embedded system, i.e.

    x
  x x x
    x

The algorithm is really simple: read 5 unsigned integer values, get the highest 2, do some calculations on those and write back the unsigned integer result.

What is nice is that the 5 integer input values are all in the range of 0-20. The calculated integer value are also in the 0-20 range!

Through profiling, I have figured out that getting the largest two numbers is the bottleneck so I want to speed this part up. What is the fastest way to perform this selection?

The current algorithm uses a 32 bit mask with 1 in the position given by the 5 numbers and a HW-supported CLZ function.
I should say that the CPU is a proprietary one, not available outside of my company. My compiler is GCC but tailor made for this CPU.

I have tried to figure out if I can use a lookup-table but I have failed to generate a key that I can use.

I have $21^5$ combinations for the input but order isn't important, i.e. [5,0,0,0,5] is the same as [5,5,0,0,0].

It happens that the hash-function below produces a perfect hash without collisions!

def hash(x):
    h = 0
    for i in x:
        h = 33*h+i
    return h

But the hash is huge and there is simply not enough memory to use that.

Is there a better algorithm that I can use?
Is it possible to solve my problem using a lookup-table and generating a key?


texts: Are the two LTL properties $GF(\psi_1 \land F\psi_2 )$ and $GF(\psi_2 \land F\psi_1 )$ equivalent?

texts:
Is $GF(\psi_1 \land F\psi_2 )$ equivalent to the property $GF(\psi_2 \land F\psi_1 )$?

Attempt:

In the first property each state must eventually see $\psi_1$ and $\psi_2$, in the second property as well each state must eventually see $\psi_1$ and $\psi_2$, as such the two properties must be equivalent. Is this correct?


texts: Difference between diameter of a graph vs longest path of the graph

texts: I am curious what is the difference between diameter of a graph vs longest path of a graph. I just read diameter of a graph can be solved using Floyd warshall in O(V^3) while longest path can be calculated in O(V + E) using topological sort.


texts: In information theory, why is the entropy measured in units of bits?

texts:
In information theory, we have the quantity "information".

Suppose we have some discrete random variable $X$, that can take values $\{{a,b,c\}}$ with corresponding probability distribution $\{{\frac{1}{2},\frac{1}{4},\frac{1}{4}\}}$. Then, information, $h$, is measured as $h(x) = -\log_{2}P(x)$.

So now we can say: $$h(a) = -\log_2 \bigg(\frac{1}{2}\bigg) = 1 \text{ bit}$$ $$h(b) = -\log_2 \bigg(\frac{1}{4}\bigg) = 2 \text{ bits}$$.

My question is, why does that computation result in a quantity measured in bits?

Explanations I've seen all say something along the lines of: "this quantity is measured in units of bits because of the log base 2" with no further explanation as to why. So why does taking the log (base 2) of a probability result in a quantity measured in units of bits?

Is it somehow related to the idea that if a system can be in $N$ states, then we can encode those $N$ states using $log_2 N$ bits? E.g. if a system can be in 4 states, we can encode those 4 states in binary with $log_2 4 = 2 \text{ bits}$: $00, 01, 10, 11$.


texts: Proof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete)

texts:
I need to prove that TAUT is coNP-complete. I showed that $\text{TAUT} \in \text{coNP}$ by reducing $\text{SAT}$ to $\overline{\text{TAUT}}$. However, I cannot figure out how to prove that every problem in coNP can be reduced to $\text{TAUT}$ in polynomial time. To do that, I would need one of two things:

A known coNP-complete problem for reduction or
a proof that a problem is coNP-complete if its complement is NP-complete.

Neither of these was given to us in lecture, so I cannot use anything without proving it myself. Did I miss anything which should have been obvious? Where should I start?


texts: Need for random bits in final PCP theorem statement

texts:
PCP theorem states that $$PCP(O(\log n),O(1))=NP.$$ Could we not run through $O(\log n)$ bits deterministically?

Does PCP theorem statement mean any set of $O(\log n)$ random bits out of $2^{O(\log n)}$ choices of such bits suffice? If so, why cannot I choose all $0$ bits? If not why not?


texts: Divide numbers into fewest groups with each group's sum bounded

texts: We have an integer $K$ and an array of $N$ positive integers each smaller than $K$. How do we group the numbers into the minimum number of groups where the sum of each group is less than or equal to $K$?


texts: Prove that there isn't a DFA characterized by (a*)+(b*) for which |Q| = 3

texts:
Let $R=(a*)+(b*)$ be a regular expression. Prove that there cannot exist any DFA $M=(Q,\Sigma,\delta , q0, A)$ such that $|Q| = 3$ and $L(M)=L(R)$.

The problem is, I think IT IS possible to construct such a dfa that has 3 states in total.

Am I missing something?


texts: How to show working for summing of Big O notation

texts:
The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed?
$$\sum_{i=1}^{n-1}O(lg n) = O(nlgn)$$


texts: What Is The Complexity of Implementing a Particle Filter?

texts: In a video discussing the merits of particle filters for localization, it was implied that there is some ambiguity about the complexity cost of particle filter implementations.  Is this correct?  Could someone explain this?


texts: How to prove that average complexity is N/2 for linear search in the unsorted array

texts:
All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the items in the list are randomly distributed.

Can anyone show how I would arrive at N/2 if I have items randomly distributed? Or does it come out of randomly shuffling array bazillion times and recording the number of operations?


texts: Recognizability of machines which halt in $n$ steps on some input

texts:
We define the following language:
$$L = \{M \mid \text{$M$ is a TM and there exists an input $x$ on which $M$ halts in at most $|x|$ steps}\}.$$
Following this question I understand that $L$ is not decidable, but I know that it is recognizable, and therefore I'm looking for a reduction from the HALTING problem to $L$.
I thought of the following reduction:
On input $M$ for $L$, create a Turing machine $M'$ that for input $y$ for the HALTING problem runs $M$.
If $M$ halts, then $M'$ halts too, but I'm having problems proving the reduction.
Another way of proving this problem in my opinion is by building an $M'$ that recognizes the language by running $M$ all inputs for their length.
If $M'$ halts on some input it accepts, otherwise it keeps going.
Does this solution work?


texts: Exceptions from exceptions, does such a thing exist?

texts:
I am intrigued: In many languages there are both normal control flow and exceptions.
But I never saw "an exception from an exception" or "an exception from an exception from an exception". Why?
Why there are just two variants?
My guess is that an "exception from an exception" would be just another class of exceptions, but this needs to be elaborated further.


texts: Writing a regular grammar for a regex of decimals

texts:
So I've got the regex /[1-9][0-9]*(\.[0-9]*[1-9])?/ and I'm trying to write a regular grammar for it.

I started off like this:

S ∶≔ EAB
A ∶≔ DA | ε
B ∶≔ .AE | ε
D ∶≔ 0 | 1 |  2 | 3 |  4 | 5 |  6 | 7 |  8 | 9
E ∶≔ 1 | 2 |  3 | 4 |  5 | 6 |  7 | 8 |  9

But I realised that this does not follow Chomsky's rules for regular grammars. So I was wondering how could I adapt this logic into proper notation.

Thanks!

EDIT: So below is the NDFA generated from the regex above:


texts: Would saying "Call the printf function" be the same as "Call the printf method"?


texts: what is actually a circular array and representation

texts:
There are two ways to implement a circular array either take a new array of size 2N where N is the size of the initial array and copy initial array twice into that new array

array = [1,2,3,4,5]
new_array = [1,2,3,4,5,1,2,3,4,5]

Or we can use (i % N) where N is the size of the array, i is the index of that element

for(var i = 0; i < N + i; i++)
{
    console.log(arr[i%N])
}

What does exactly circular array mean? Is a normal array while representing?


texts: Correctness proof: 2-approximation of greedy matching-algorithm

texts:
Input: number of edges and vertices, and array of all edges in graph.

Output: array of edges that construct a matching, so that:
$$\frac{\text{the number of edges in this matching}}{\text{the number of edges in maximum matching}} \geq \frac{1}{2}$$

Algorithm I implemented

Loop:

take a random edge (actually in order it was given);
if we can add it to our matching then add;

Finally we get a matching.

The proof of condition from given section by contradiction: let's compare our matching with the maximum one. Let's consider one edge from our matching. There're two cases: the same edge is in the maximum matching or not. If it belongs to the maximum then it's OK. If not, then there's could be not more than two adjacent edges in maximum matching. Let's assume that it happened with each edge in our matching. Nevertheless, our matching satisfies the given conditions: it has not less than 0.5 of number of edges in maximum matching.

However the proof seems not really good to me. I guess there also should be a proof by induction by edges of matching. But I can't come up with a good idea.


texts: Access control matrices: who are the subjects: users or processes?

texts:
I'm studying the basics of security in computers. The doubt I have is that the access control matrix is presented as a matrix whose rows are the subjects and the columns are the objects. Also subjects are defined both in Windows and Unix (and Multics for that matter) as processes, threads, not users, but processes.

My question is why then, when I check the Windows ACLs, I get the permissions that each user has instead of the permissions that each process under each user has.

It seems to me that more than a matrix a cube is needed, because the subject permissions, i.e. the processes permissions, are bound to the identity of the user logged in.

From what I've read it seems ambiguous: in some cases subjects are processes, and in others subjects are user accounts. Which one is the correct form?


texts: Smallest(k) in red-black tree. How is it O(logn)?

texts:
Is it the same as find minimum for a binary search tree?
I know recoloring runs in O(logn) and rotations are O(1).

Even if we are wanting it to find the 'k-th' smallest key in the red-black tree.

Could someone help me understand it in more detail? Thank you!


texts: How to choose between UC and PL when using the DPLL algorithm?

texts:
We know DPLL algorithm is backtracking + unit propagation + pure
literal rule.

I have an example. There is one example to solve following Satisfiability problem with DPLL. if assign of "0" to variables is prior to assign "1" to variables, Which of Unit Clause (UC) or Pure Literal (PL) is used to solve this specific example?

  $\{\lnot A \lor B \lor C\}, \{A \lor \lnot B \lor C\}, \{A \lor B \lor \lnot C\}, \{A \lor B \lor C\}$

Olympiad Solution is: PL and UC.

Our Solution is just UC.

Who can satisfy me why Olympiad solution is correct ?!

Unit propagation is not possible as there are no unit clauses.

Pure literal rule is not applicable as there is no literals that occur
only positively or only negatively.

Update:
I think in node (3) we can user PL or UC. Isn't it?


texts: How to show composition of one way function is not such?

texts:
I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function?

Specifically: Say $f$ and $g$ are one-way functions (either weak or strong).
How do I prove that their composition $g(f(x))$ is not necessarily a one-way function?


texts:
I've constructed an algorithm on (rooted) binary trees, where the running time at a node depends on the size of its smaller subtree, where we compute from each leaf upwards towards the root.
More specifically, at each node, a constant amount of time is required for each node in the smallest of its 2 subtrees.

The running time for a tree with $n$ nodes is then easily bounded by $O(n^2)$, however, I conjecture that the running time is bounded by $O(n \log n)$, since I think $\sum_{x\in V(T)}\min(|V_l(x)|, |V_r(x)|) \leq O(n \log n)$ holds.

How would I go about proving this?


texts: Finding optimum point that minimizes maximum distance

texts:
Does anyone know how I should approach this algorithm? It needs to have $O(n^3)$ complexity and I can only come up with an algorithm that has $O(n^4)$ complexity (of doing a n^2 min path from each vertex to $n-1$ other vertexes, and since I need to do this n times, it will be $n^4$ or so I think...

Input: Array $A[1...n][1...n]$ such that $A[i][j]$ gives length of edge(distance) between two points or $-1$ if there isn't and edge.
Output: a vertex $v$, such that distances(total lengths) to all other vertexes are minimized.

Can someone explain in pseudocode or in words how to do this?


texts: Show that a language is not regular by Pumping Lemma

texts:
Possible Duplicate:
  How to prove that a language is not regular?

Show that $L_2=\{a^nb^k|n\not= k-1\}$ is not regular by Pumping Lemma.


texts: Check if two items are equal after replacing

texts:
Let's say that an item is either a natural number or a list of items. Examples of items are:

1
[2]
[4, [3, 1], 3, 4]

A rule states that two items are equal. For example:

1 = 2
3 = [3, 1]
[4, 3] = [1, 5]

When using these example rules, we can transform [4, [3, 2]] into [4, [3, 1]] into [4, 3] into [1, 5] and we can say that  [4, [3, 2]] equals [1, 5].

I want to find an algorithm that, given items $a$ and $b$ and a finite set of rules, determines if $a = b$.

I already thought of an algorithm that works in some cases. But I hope to find an efficient algorithm that works in all cases. It would also be nice if the algorithm can detect $a \not= b$ instead of infinitely searching for ways to let $a = b$. Is this a known problem? Any help is appreciated.

Note: We can simplify the problem by only allowing the number 1 instead of every natural number. This is equivalent, because we can transform 1 into [1], 2 into [1, 1], 3 into [1, 1, 1], etcetera.


texts: Are hash functions really quantum resistant for commitment schemes?

texts:
It is commonly stated that hash functions remain secure in a post quantum world, the justification being that a quantum computer only has the advantage of Grover's search to give it a quadratic speedup.

However, there is active research into, for example, commitments such as https://eprint.iacr.org/2015/361.pdf. These state that in a quantum setting (whatever that means), the old way of doing commitments by requiring collision resistance doesn't work.

My understanding (possibly wrong) is that one cannot implement a hash function with quantum operators and gates because the quantum operators are unitary and therefore the hash function becomes invertible. The classical hash function uses compression to lose information and is hence, non-invertible. Is there then a possibility that if we attempted a quantum implementation of SHA-2, that would end up showing us how to break it?

Consider $x \rightarrow y = H(x)$. If I have an implementation of $H$ with quantum gates, I could take any $y$, put the remaining registers into whatever state I want (corresponding to the lost information) and then invert to obtain a valid $x$. My only assumption here is that I implemented the quantum $H$ but I can't see why this is forbidden, or even difficult.


texts: Why companies that create native mobile apps are forced to make duplicate versions on other platforms?

texts:
I am not computer savvy, so forgive me for asking why companies that create native mobile apps are forced to make duplicate versions on other platforms. "Duplicate" means the "same", so it means those companies don't have to modify the original version of the native mobile app for other platforms. I am guessing "other platforms" refer to other types of smartphones ... The question is based on the following statement. Please let me know if I have posted on the wrong forum. Thank you!

"However, this type of app is expensive to develop because it is tied to one type of operating system, forcing the company that creates the app to make duplicate versions that work on other platforms."


texts: How is the dimensionality of the volume in ConvNets determined for a general case?

texts:
In ConvNets, I understand how the dimensionality of a flat image changes after convolving it with a single filter. For example, if you convolve a P x P x 1 image (assume no padding) with a filter with dimensionality FxF, with stride S, the output dimensionality D can be computed from a simple formula $\frac{P - F}{S} + 1 $. For example, for a 28 x 28 x 1 image convolved with a 4x4 filter with stride 1, the output we get has dimensionality 12 x 12 because:
$D = \frac{P - F}{S} + 1 = \frac{28-4}{2} + 1 = 12$
Typically, however, input images have dimensionality P x P x 3 (3 because of the three RGB color channels). More generally, within the ConvNet, we are taking a convolutional layer with dimensionality P x P x Q, where Q is arbitrary, and convolving it with a filter F x F x G and stride S. I understand how the P, F and S can be used to compute the output dimensionality D (by the formula above); but I don't understand how the Q and G interact to produce an output depth. In particular, can Q and G be entirely arbitrary, or does one have to be a multiple of the other?


texts: Negative cycle detection using Bellman-Ford and its correctness

texts:
I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford.

I have 2 doubts about the correctness of the algorithm:

Why are we relaxing (num of vertices - 1) times all the edges? Why not some finite number of times till earlier values and new values remain same?
The second for loop (lines 5,6,7 in algo image) is for detecting negative edge cycles. Then I have gone through this correctness. I have seen a theorem that if there is a negative edge cycle reachable from source s then we can find an edge uv such that d(v)>d(u)+w(u,v) [I understood the proof by contradiction (if summing all vertices of negative edge cycle results in sum of all weights along negative cycle positive which means contradiction as it must be negative - page 2 of https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf]

But I am not able to visualise such an edge if I have some negative edge cycle from source vertex s. Please help me: how can such an edge exist?


texts: Artificial intelligence and undecidibility

texts: Can artificial intelligence solve problems like Post correspondence problem?


texts: What is the difference between undecidable language and Turing Recognizable language?

texts:
I was wondering what is the difference difference undecidable language and Turing recognizable language. I've seen in some cases where they ask:

Prove that the language $ A_{TM} = \{ \ <M,w> | \ M \mbox{ is a Turing Machine accepting } w\}$ is undecidable.
Prove that the language $ A_{TM} = \{ \ <M,w> | \ M \mbox{ is a Turing Machine accepting } w\}$ is Turing Recognizable.

Are they the same thing? Can someone elaborate on this issue?

Another one, is the question at hand is known as the halting problem? Or is it different from halting problem?


texts:
This appears to be a knapsack / bin-packing problem, but I seem to have got stuck and could appreciate contributions.

Scenario 1: Tough (for me!)
There is a one day conference with a set of (4 or more) sessions.
The conference will be attended by a number of companies, each one being represented by a (1 or more) representatives.

Across sessions the number of representatives for each company will vary (and may be zero), with each individual having the same chance of being present as any other individual (so there is an increasing likelihood of a company being represented when it has more representatives).

There is a single row of seats in the conference. There are more than enough seats for the most popular session. (e.g., if the most popular session has 100 delegates, there could be 120 seats for the whole conference).

Constraints

A rep. belongs to one company
A rep. must be seated in a session they are going to.
A rep. must not change seats across consecutive sessions
A rep. is assigned to one chair in each session they attend.

Goal
To fit the constraints and priorities optimally.
Example. 15 chairs, 4 companies (A-D), 4 sessions (S1-S4).

// Session attendees by company
S1: A2 B6 C3 D3
S2: A4 B5 C1 D2
S3: A3 B3 C4 D1
S4: A5 B2 C5 D0

// Possible solution (I did this manually!)
S1: [AA.BBBBBBCCCDDD]
S2: [AAAABBBBBC...DD]
S3: [AAA...BBBCCCC.D]
S4: [AAAAA..BBCCCCC.]

Question
How can I solve this algorithmically?  The algorithm doesn't have to be particularly fast but it does need to yield working results.

Scenario 2: Tougher?!
The same as above but the row of seats has enforced break points (like pillars, walkways, etc).
I think this latter issue is merely a 'knapsack'-type modification to the above problem

Thoughts towards a solution
It seems that it should be possible to have consecutive seating available in most cases, which implies that a solution could be found by identifying company-invariant seats by filling the minimum company representation across all sessions, leaving gaps between companies that are somehow calculated based on the variation of the company and it's neighbour.

It is trivial to find cases where there is only a partial solution, eg the following, but that's okay. I still need to get the best solution I can.

S1:   [AAAACB]
S2:   [ACCCCB]

Edit: I managed to resolve this, using OR-Tools.  It required 3 separate solvers in the end, in order to split the problem into tranches.

Tranche division is done with a solve for the rows, based on a count of seats to work per tranche.
This uses two slack criteria to allow for (a) allocation wiggle room - and (b) one for an overflow (where there are large rows)!

Then a weight-change-over-each-session bin-packing variation to allocate organisations to the tranches.

Finally, seat allocation is managed. The seat allocation can manage about 100 representatives per tranche before it slows down due to scaling problems that seem to be inevitable with constraint programming systems. The constraints are as listed above. eg. for the constraint that one rep belongs to one company:

model.AddImplication(del_chairs[d_tuple], org_chairs[o_tuple])


texts: fastest way to identify "singular row" of a matrix

texts:
Suppose I have a matrix that I know to be singular. This means that there is at least one row in the matrix which is a linear combination of the other rows. What is the fastest way to identify which row that is or which rows they are?
I'm aware that the solution to this problem is not unique in general. The goal is to determine a set of rows which, if removed, leave only linearly independent rows. Then, more linearly independent rows can be added to get a non-singular matrix. Obviously I'm leaving out a bit of context regarding why I would be doing this, but I believe I have included everything relevant to the question.
My thinking is basically to attempt to attempt Gram Schmitt and just mark whatever step returns a zero vector. I doubt there's a faster approach than this, but suspect this problem has been studied to the point that a definitive answer exists.
Edit: To be clear, I only want to find a minimal set of rows such that, if they are removed, I get back a linearly independent set of vectors.
Also, let me give an example of the algorithm that I am proposing. I'm using an example given by nir shahar but slightly modified.
Suppose I have a matrix with rows (1, 0, 0), (0, 1, 0), (1, 0, 0)
The Gram Schmitt algorithm returns
first:  (1, 0, 0)
second: (0, 1, 0) - 0 * (1, 0, 0)
third:  (1, 0, 0) - 1 * (1, 0, 0) - 0 * (0, 1, 0)
I'm not actually returning this set of vectors. All I care about is the fact that the third step returns the zero vector. So, I flag the third row as being a "problem."


texts: DFA & RE from descriptive definition of given regular language

texts:
I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them.

Some strings which are accepted by the above regular language are;

{010, 0100, 0101, 1010, 0010 .......0101110.....}

In the above strings there is only one 010 substring. If there is more than one 010 substring in a string such as.

{01010, 01011010... }

then the DFA of the above language should not accept that string.

If someone provide me ony DFA of the above lang. then i would be able to make the RE by state elimination. Or if someone provide me the RE of the above lang. then i could make the DFA by other kleene theorem.

My work: I made the following DFA for that language;

This DFA is accepting all the strings like 010, 0100, 0101, 1010, 0010.... and its also rejecting the string with more than 010 like 01010. But with that its rejecting 0101110 string which is part of the language.

Note: I go through the question which is already on the CS stackexchange as previously my question was marked duplicate. This question is about "How we can prove that a given language is regular or not". But in my question i have provided the descriptive definition of a regular language. And i am trying to get its RE or DFA.


texts: RPI cluster performance related to network performance

texts:
I'm writing my thesis and i have built a RPI cluster, containing 10 nodes which consists of RPI model 3b. I've them connected to two gigabit switches. I don't know the CAT of the cables. They are not connected to the Internet, they just live in their private network.

Further more, i've calculated the theoretical performance by the formula:

number of cores * average frequency * 16 FLOPs/cycle = x GFLOPS (Got the formula from https://www.slothparadise.com/how-to-run-hpl-linpack-across-nodes/ )

after i applied it, it turns out i should have 76,8 GFLOPS in theory assuming that the source is relaiable and correct. When i benchmark it using HPL 2.1 i've only reached little about 7 GFLOPS at best when trying out various variations.

Now to my question: i've read up on the RPI model, and it says it only have 10/100 Ethernet. Is that the source of my problem? Seeing i get out GFLOPS from a node, but the network transportation is much less then Gigabit speed which would mean 76,8 GFLOPS * 0,1 Gigabit/second = 7,68 GFLOPS (in theory). Or am i way off the tracks in my thinking?

I really appriciate any help, so i can know if i have to keep working on the configuration for the benchmarking or if i can move on. Also, i'm sorry if i have posted in the wrong place.

Stay safe out there!


texts: Complexity of simplifying two-variable algebraic expression

texts:
Given algebraic expression of two variables x and y, I want to simplify this algebraic expression until it cannot be simplified anymore.  What algorithm can I use for this?

For instance:

x+x+y+y = 2•x+2•y = 2•(x+y)

x•x+y•y=x2+y2

(x+y)•(x+y)=(x+y)2

x•x+x•y+x•y+y•y=x2+2•x•y+y2=(x+y)2

The most simplified algebraic expression is the one with the fewest characters.  Expressions will have only addition, multiplication, and exponentiation with a constant.

What is the complexity of this problem?

Does exist polynomial time and space algorithm to solve this problem? I tried to find over the Internet the algorithm to simplify algebraic expressions, but I didn't find anything.
The problem is that I don't know where to start.


texts: Representation of connected components in the $O(|E|)$ time/space variant of Karger's algorithm

texts:
I'm trying to understand the various optimizations given in the original 1992 paper on Karger's algorithm. Specifically, looking at section "3.1 Unweighted Graphs", I don't understand what data structure is used to represent the variant of the algorithm that works in $O(|E|)$ time and space (the other variant, which uses union-find  and takes $O(|V|)$ space and $O(|E| \log |E|)$ time, makes sense).
Specifically: how would you represent the edges so that it is possible to

track the connected components induced by a sequence of $m$ edges in a random order in $O(m)$ time?
contract a sequence of $m/2$ edges in a random order in $O(m)$ time?

I must be missing something obvious, but I couldn't find any implementation for this variant (everyone seems mostly interested in implementing the union-find variant of the algorithm).


texts:
Call a family of sets $\mathcal{F} = \{S_1, \dotsc, S_k\}$ "diverse" if each set $S_i \in \mathcal{F}$ has at least one unique element.  What are possible approaches for finding the largest diverse set $S$ in a family of sets $\mathcal{F}$?

One approach is to solve a modified set packing problem.  Suppose $\mathcal{F}=\{S_1,\dotsc,S_k\}$. Let $K$ be a subset of elements, $K \subset \bigcup S_i$, and let $\mathcal{F}_{-K}=\{S_1 \setminus K,\dotsc, S_k \setminus K\}$.  Then the maximal diverse set $S$ corresponds to the largest maximal set packing obtained from $\mathcal{F}_{-L}$ where $L$ is the set of all non-unique elements in $\mathcal{F}$.

But, what's a good heuristic for choosing $K$?  Or are there better approaches altogether?


texts: Looking for some references on voting theory

texts:
After reading through this paper on optimizing the sum of sigmoid functions,  http://www.web.stanford.edu/~boyd/papers/pdf/max_sum_sigmoids.pdf, I am interested in the problem addressed in section 7.3 (Political marketing example). Specifically I am interested in any work on the following problem.

Suppose there is a set of candidates $C$ and set of voters $V$ where each candidate $c_i = <c_{i, 1}, ..., c_{i, l}>$, and each $v_j = <v_{j, 1}, ..., v_{j, l}>$ is a vector of real numbers over $l$ issues. And voters have some logistic probability to vote for each candidate depending on how much the candidate and voter "agree" on each of the $l$ issues, e.g. $v_j$ votes for $c_i$ with probability $\phi\big(-(c_i \bullet v_j)\big)$ where $\phi$ is just some sigmoidal function.

Assume all voters positions and all candidate positions are known and static, expect for $c_1$. The objective of the problem is to select the position on issues for $c_1$ such that $c_1$ has the highest probability of winning the plurality vote. That is select

$$\max_{c_1} \sum_{v_j} \phi\bigg(-(c_1 \bullet v_j)\bigg)$$

The paper discuss a general method of solving this problem using a branch and bound technique (which has a nonpolynomial runtime) for sigmoidal programing problems. However, the paper, and the references, do not give a hardness proof of this specific voting problem, and the references do not appear to mention any other techniques for solving this problem.

Any literature addressing the hardness of this problem, or more specific techniques for this problem would be greatly appreciated.


texts: Data structures used for variable length integers

texts:
I've just had a thought about multiple precision number (i.e. variable length integers). The naive way to represent numbers is to use an array sized in such a way that the number of required bits can be stored. Example say we dispose of words of size $L$ and we want to store $N \leq 1$ bits, then we need an array of size
$$
n = \left\lfloor \frac{N+L-1}{L} \right\rfloor
$$
Assuming the representation base is $2$, it means that

$$
x = \sum_{j=0}^{N-1} x_j 2^{j} = \sum_{j=0}^{n-1}y_j2^{jL}
$$

However I see many problems with this representation, from the storage point of view I can make the following example. Say there are two indices $0 \leq j_0 < j_1 \leq N-1$ such that $x_j = 0$ for each $j \in \left\{0,\ldots,j_0-1,j_1 + 1,\ldots, N-1 \right\}$. If $j_1 - j_0+1$ is much less than $N$ many of the $y$ variables would be actually $0$, namely not used which means sparsed. However I observe that under such hypothesis

$$
x = \sum_{j=0}^{N-1} x_j 2^{j} = 2^{j_0} \sum_{j=0}^{j_1-j_0} x_{j+j_0}2^j
$$

Which implies that naming $m = \left\lfloor \frac{j_1-j_0+L}{L} \right\rfloor$ I would have to use $m$ words instead of $n$, and given my hypothesis I would have $m$ much less than $n$. In conclusion in that specific case I could use a pair $(j_0,\vec{y})$ (offset plus vector) to represent my number. I can generalize this approach probrably to obtain something which is very compact. I don't know about general algorithms, but I can see there's at least the memory benefit.

Are there studies about best ways to represent large numbers in a computer? I'm not aware of such studies and I would like to find out if there are any.


texts: A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

texts:
Wikipedia states on sparse languages that

  There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from a NP-complete language to a sparse language iff NP $\subseteq$ P/poly.

Is that correct in that it is so far proven for an arbitrary Turing reduction and not a limited P-time reduction? (Could it be true for P-time reductions also, but maybe not proven so far?) It cites this without reference. What is a reference for this?


texts: Algorithm for cycle-detecting comparison

texts:
I am looking for an algorithm that I can use to compare nested and potentially recursive data structures, for example to implement the Scheme equal? function.  equal? recursively compares two objects for equality and properly handles cycles.  Specifically, the algorithm needs to return true iff the (possibly infinite) unfoldings of the graphs would be equal, e.g.

(letrec ((a (cons 1 (cons 2 a)))
         (b (cons 1 (cons 2 (cons 1 (cons 2 b))))
  (equal? a b))

is true because a and b are both cyclic lists that repeat the sequence (1 2) infinitely.

Destructive modification of traversed nodes is thread-unsafe, requires a spare bit in object headers, and requires a separate traversal to reset the bit.  Using a hash table to store object addresses is not safe in the presence of a moving garbage collector unless the GC is blocked for the duration of the traversal (so the operation cannot be implemented except as a primitive).


texts: Is there an affordable experiment which shows chips can't get much smaller?

texts: If I am correct, chips cannot get much smaller because of Heisenberg's uncertainty principle. My friend and I want to perform an experiment (which is cheap, i.e. doesn't require million-dollar equipment) which shows that if a chip is too small, it will mess up. Is there any such experiment?


texts: Formal notations of equivalencence between floating point expressions

texts:
In an informal context, most programmers might call these two expressions "equal" and no one would be mislead:

(a + b) + c
a + (b + c)

For floating point numbers, we know that these two expressions are not strictly equivalent (in the sense that they evaluate to equal values for any a, b, and c) because floating point addition is not associative. Nonetheless, these expressions seem to be similar in interesting and useful ways. For many inputs, these expressions produce nearly equal or equal outputs. The real number counterparts of these expressions are equivalent. In many programming contexts, these expressions can be swapped without concern.

Are there notions of equivalence between floating point expressions that describe this sort of similarity?

Stating simply that the real number counterparts of these expressions are equivalent is a bit too literal to be a useful answer.


texts: Is it correct to say that there are similarities between CORDIC and digit recurrence algorithm for division?

texts:
I've been studying recently some variations of the CORDIC, and it seems to me that the logic behind at least the basic cordic or the redundant CORDIC is very similar to the logic used to design digit recurrence for the division (using redundant digit set). Is this statement correct?

At each iteration they have to guess a digit to construct the final answer, I would also say that the division is a particular case of the CORDIC iteration, indeed the CORDIC used in linear mode actually allows to retrieve the iteration for the division.

Therefore I'd say that a good understanding of the division is essential for understanding CORDIC, because it teaches you how to use Robertson and PD diagrams, tools that are used also in the Redundant CORDIC for example.

Are these observations correct?


texts: With a halting oracle, can tell whether something will have finite output?

texts:
A program can have finite output, yet still not halt. Example:

1: output "Yolo"
2: output ""
3: go to step 2

This only ever outputs "Yolo", despite never halting.

Is there some way, with a halting oracle, to determine whether a program will have infinite output or not?

Bonus: If not, what would be the Turing Degree of a machine capable of such a feat?


texts: Prime attribute dependant on another prime attribute allowed under BCNF?

texts:
I have been studying DBMS ans I have a question that I got conflicting answers to:
Is prime attribute that is dependant on another prime attribute allowed under BCNF?

Meaning P->P.

I know that NP->P is not allowed.
and also NP->NP (as it is not 3NF - transitive relation)
Thanks.


texts: Find maximum element in sorted arrays in logarithmic time

texts:
Been stuck on this for a while, would really appreciate some help:

  Suppose you are given an array A[1...n] of sorted integers that has been circularly shifted k positions to the right. For example, [35,42,5,15,27,29] is a sorted array that has been circularly shifted k = 2 positions, while  [27,29,35,42,5,15] has been shifted k = 4 positions. Give an algorithm for finding the maximum element in A that runs in O(log n) time.

The elements in A are distinct.

I understand that to achieve O(log n) time I'll probably have to search through the list by starting at the middle, and then going left or right, then splitting the list in half over and over, but I'm not sure how to attack it beyond that.


texts: In reference to the Chomsky hierarchy (and automatas), Which is the linear feedback shift register Languages/automaton?

texts:
The Chomsky hierarchy is a guideline on language expressive power. The linear feedback shift register is a very interesting "element" to structure a language and there is a large theoretical literature.

In reference to the Chomsky hierarchy (and automata), which is the linear feedback shift register languages/automaton ?


texts: Mathematical topics in computer science with applications

texts:
I just got my master's degree in mathematics, it was related to abstract algebra. I'm thinking about applying for a doctoral degree, however, I deeply want to study something with an "applied" appeal.

Does anyone know a branch of computer science that can be done by math students but that can still be considered math?


texts:
Given an n variable boolean DNF formula and a number k, does this formula has satisfying input combination greater than k?. (0<=k<=2^n).
Where input is infinite number of n tuples where repeating tuple is possible.
For exampl.  F(a,b) =ab + a'b. Input set is (11,00,11,01) and k=2.
Answer is 3 here so decision says yes as 3>k.
Can i define this problem in more formal way and prove that it is np/npc/ anything else. I am looking for suggestions specially for infinite number of tuples. I am aware of npc and reduction stuffs but need help to classify this problem properly.


texts:
I am trying to implement the Deutsch algorithm.
My steps were:

Write down $|01\rangle$ in a matrix form $A$;
Apply $H^{\oplus2}$ gate to $A$ matrix;
Multiply it with $U_f$ matrix;
Apply $H$ to the first qubit;

After the above steps, I got a matrix:

array([[ 0.        ],
       [ 0.        ],
       [-0.70710678],
       [ 0.70710678]])

How should I perform a measurent step on the first qubit to get the answer?


texts:
I am given a complete weighted graph and I need to make pairs among the vertices so that the sum of weights is maximum.
(If I have vertices $v1, v2, v3, v4$ and if I make pairs $(v1,v2)$ and $(v3,v4)$ then only the edges connecting the vertices in the pairs respectively will contribute to the sum.)

On doing some research, I found that it can be solved with Blossom's algorithm but I am having difficulty in writing the code by myself. And also, I can't find any proper implementation of this algorithm.


texts: Context-free Languages closed under Reversal

texts: In class this week we've been learning about the CFLs and their closure properties. I've seen proofs for union, intersection and compliment but for reversal my lecturer just said its closed. I wanted to see the proof so I've been searching for the past few days but all I've found is most people just say that to reverse the productions is enough to prove it. Those that do go a little more formal just state there is an easy inductive proof you can give. Can anyone provide me with some more information/hints about the inductive proof? Try as I might I can't come up with it.


texts: Show that C(n) = {a^k | k is a multiple of n} is a regular language

texts:
I came across this question in an exam book and was unable to find a solution:

Prove that C(n) = {a^k | k is a multiple of n} is a regular language for every natural number n ≥ 1.

I wasn't able to construct a DFA as the number n is left variable in the original question. Is it possible to construct a DFA with a variable number of states?

Any help would be greatly appreciated.
Thank you!


texts:
I've a question regarding this diagram. I'm thinking of adding a new state between q5 and q6 that accepts a lambda value but I'm not quite sure or this diagram is correct?
And in what situation we add a state that accepts an epsilon/lambda?
RE:1*(00|011*)*00


texts: How to show that two vertices in a connected component are in the same set? (bi conditional)

texts:
Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set.

The CONNECTED-COMPONENTS algorithm is the following:

It seems pretty obvious that when we keep adding the vertices of the direct edges of a connected component to a set, eventually the set formed has all the vertices in the connected component - directly connected as well as indirectly connected.
But how do I formally prove that? Also it seems like a biconditional to me.
I've thought of things like loop-invariant or a proof by contradiction. But unable to exactly figure out what to do. Any help is appreciated.


texts: Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time

texts:
This is from CLRS problem 24.3-5:

  Professor Gaedel has written a program that he claims implements
  Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for each vertex
  $v \in V$ . Give an $\mathrm{O}(V+E)$ time algorithm to check the output of the
  professor’s program. It should determine whether the $d$ and $\pi$
  attributes match those of some shortest-paths tree. You may assume
  that all edge weights are nonnegative.

All the answers I find online, explain how to solve this problem, but not why their solution is correct.

Let us look at what we need to do:

We need to make sure that for the source node $s$ we have $s.d = 0$ and $v.\pi = \emptyset$. This can be done in $\mathrm{O}(1)$ time.
We need to verify that the $\pi$ table corresponds to a tree. This is simple, we just build the undirected graph corresponding to the $\pi$ table, and then run a DFS traversal to see if the graph has cycles or not. Can be done in $\mathrm{O}(V+E)$ time.
For every node $u$ not reachable from $s$, it must be the case that $u.\pi = \emptyset$ and $u.d = \infty$. Another simple check, find everything you can reach in the tree that you drew in step 2, and for every other node do the checking. Another $\mathrm{O}(V+E)$ term.
For every edge $(u,v)$ in the shortest path tree it must be true that, $v.d = u.d + w(u,v)$. Check to ensure that this is the case. Because the professor might put random guesses for the distance values that turned out to be correct, but they had absolutely no connection to the shortest path tree given.

Everything until this point is 100% simple and clear. But the last point, is what I find difficult to argue about.

Relax every edge of $G$ exactly once, if any distance values change, then the shortest path tree given is wrong, if all stay the same then it is correct.

Why is this true? How to prove that if indeed the shortest path tree is wrong, relaxing every edge of $G$, no matter the order, will definitely improve at least one of the distance values?


texts:
I am missing something obvious here. Does ACC0 reach a ceiling AC0[m] with m being constant?
By another description, ACC0 can use any m, which can trivially test modulus gates from [n/2,n] over all inputs. Any modulus active in that range indicates MAJ returns true, implementable as an OR over the current range of gates.