texts: Why is my bubble sort taking longer to sort a random array as opposed to a descending array?

texts: I am in an entry-level algorithms class, and for our final project we are coding and thoroughly analyzing 6 different sorting methods. Part of the analyzation is timing the methods and comparing the runtime results depending on the original order of the array (in order to more fully grasp the concept of constant costs, I suppose). I coded the bubble sort in Java, and when I run it on an array that is in descending order, it returns a sorted array FASTER than when I run it on an array of random ints, even though it is doing, on average, twice as many swaps. It seems to me that doing twice as many operations should result in taking much longer to finish. I have NO idea what could be causing this discrepancy, and any help would be appreciated.


texts:
Consider a square, ABCD. Intuitively it seemed to me that its chromatic polynomial is $\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)$ where there are $\lambda$ colours available..

That is there are $\lambda$ ways in which a colour for A can be picked, there are $\lambda - 1$ ways for colours for B and D to be picked(B and D are adjacent to A) and $\lambda - 2$ ways for colours for C to be picked.

However using the decomposition theorem (slide 47, Example 11.33) and decomposing the square into a path of length 3 and a triangle, shows that my initial reasoning is wrong.

Could you tell me where I am going wrong with my thinking.


texts: Why does a DFA have multiple final states?

texts: I am taking a course on programming language design and we got to the DFA part. It is known to be formally defined by a 5-tupple but they did not make it very clear to us why a DFA can have multiple final states. I know that the languages that it can accept are involved, but nothing else.


texts: Minimum circles to cover a set of points and avoid another set of points

texts:
Points are in 2d euclidean space. Given a set of n points, A, and a set of m points, B, what is the minimally sized set of circles such that this set of circles covers all points in A and no point in B is covered by a circle?

circles can have arbitrary radius

any thoughts about the difficulty of this problem? any thoughts on non trivial exact algorithms?


texts:
I have an algorithm similar to this:

i=1
while(i < n) {
  //something in O(1)
  while(i < n && cond) {
    //something in O(1)
    i++
  }
  i++
}

Where "cond" is some condition which can be checked in $\mathcal O(1)$. It is clear that this algorithm is $\mathcal O(n^2)$. But is it also $\mathcal O(n)$?

I'd say yes because the statement "i++" is executed $\mathcal O(n)$-times since both loops end when i reaches n.

Is it possible to rewrite the algorithm in a form with equivalent runtime so that it can be seen more clearly?


texts: Modifying Dijkstra’s algorithm to favor the path with least amount of edges

texts:
I need to modify the Dijkstra's algorithm to get the shortest path in a directed graph and get the one with the least amount of edges if there are equal paths.

I am thinking to add another data field to count the number of edges from start and compare them in same way as weights. Would that work?


texts:
I would like to know how to prove that the Job Scheduling decision problem is strongly NP-complete using 3-partition.

Input: A set of $n$ tasks of length $t_1, t_2, \ldots t_n \in \mathbb N$ and $k$ processors.

A feasible solution is a function $\alpha: \{1, \ldots ,n\} \rightarrow \{1, \ldots k\}$  which assigns each task to a processor.

The usage time $u_j$ of a processor $j$ is the sum of the lengths of all the tasks assigned to it, that is to say that $u_j = \sum_{i: \alpha(i)=j}t_i$.

We try to minimize $\max_j u_j$, that is to say the time of use of the most used processor.

In the JS$_{dec}$ decision problem corresponding to JS, the instance is accompanied by a target value $T$ and we are trying to find out if there is a solution where all the processors have a usage time limited by $T$.


texts: Number of substrings possible with even characters

texts:
Consider a string 'ABBAA'
Possible substrings with even number of characters are $4$
'ABBA' : Count of 'A' is even and 'B' is even
'AA' : Count of 'A' is even and 'B' is even - ($0$)
Similarly 'BB' and 'BBAA' substrings.
So a total of $4$ substrings are possible.
If given string is 'AABCCBBCAA'
substrings possible are "AA" "BB" "AA" "CC" "BCCB" "CCBB" "CBBC" "CBBCAA" "AABCCB"
So total $9$ substrings are possible
Is there any pattern or sequence or algorithm to find this?


texts: Solving Recurrence Relations 'Chip & Conquer'

texts:
I've been tasked with solving some recurrence relations, and I've been running into trouble with so called 'chip & conquer' relations.

Here are some example problems:

$$T(n) = T(n-5) + cn^2$$

and

$$T(n) = T(n-2) + \log{n}$$

I'm supposed to be giving an answer in $\Theta$ notation. How do I go around and solving relations like these?


texts:
Does our PC work as Turing Machine?  The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have 256^30128000000 states and thus, it has finite states.

I know that we can write a type of program that, if during execution we run out of memory, will request to swap memory disk with empty memory disk and resume execution.

But what if we don’t swap memory disk, in this case is it right to consider PC as FA?


texts: Courses that give good insight on the nature of a Computer Science major?

texts: I'm a business informatics student so I am taking introduction to computer science and computer programming, and so far I hate everything that has to do with this major aside from these 2 courses which I am really enjoying so far, so I am considering changing to a computer science and engineering major, but I want to make sure this is what I will enjoy before I make this change so I am researching some stuff relating to computer science online, one of which being discrete mathematics. Do you think discrete maths gives good insight on how CS is like? How about 'Theory of computation' and 'Intro to Artificial Intelligence'? Do you have any other recommendations for courses or subjects that DO give good insight on CS and do not have any course prerequisites so I can look into them and be able to follow? Thanks in advance to those who take the time to answer and help :)


texts: Why is quiescent consistency compositional, but sequential consistency is not

texts:
I'm having trouble in comparing these two memory consistency models.

Essentially for  sequential consistency I think of real code like this:

int x, y;

void ThreadA()
{
   x = 20; //Write
   int a = y; //Read
}

void ThreadB()
{
    y = 20;
    int b = x;
}

In a  sequential consistency environment it's impossible for a or b to not be 20. That is either a = 20, b = 20 or a = 20 && b = 20.

But how does quiescent consistency fit in to this example, and why is it compositional?


texts: Are Linear Bounded Automatons Turing Complete?

texts:
Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape.

But this causes them to not be Turing Complete? Why?


texts: Acceptable language in computational complexity

texts: What are acceptable languages in computational complexity? Is it Turing recognizable? I was searching online and found this description. Does anyone beg to differ?


texts: Why can't hash tables provide O(n) sorting?

texts:
Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then retrieving them in order?

You just insert each number into the hash table, and remember the lowest and highest number inserted. Then for each number in that range, in order, test if it is present in the hash table.

If the array being sorted contains no gaps between values (i.e. it can be [1,3,2] but NOT [1,3,4]), this should give you O(N) time complexity.

Is this correct? I don't think I've ever heard of hash tables being used this way - am I missing something? Or are the restrictions (numeric array with no gaps) too much for it to be practically useful?


texts: Can a programming language be designed to use a fixed amount of memory?

texts:
I have been toying around with the idea of creating a programming language as a side-project, specifically trying to get extreme performance out of a machine.

I have been thinking about the efficiency-memory tradeoff, and was wondering if it would be at all possible to design a language which always uses a fixed amount of memory.
That is, it allocates a large chunk of memory (16K, 64K, 1M, depending on the task), and instead of allocating from a heap, just gives some more memory out of the block we've already allocated.

The idea here is not to be practical, but rather to pose a challenge: design a fast algorithm that works on a fixed amount of memory.

If this sounds like a fun project, please let me know and I'll get on it.

If, however, this is a very naive thing to say (I don't know much about the inner workings of programming languages), I would very much appreciate some resources as to where I can learn more.


texts: Retrieve shortest path between two nodes using Bellman-Ford-Moore algorithm sequentially

texts:
This is my first question here and I hope you can help mt clarifying a doubt.
Basically, I'm studying shortest path algorithms, for instance Dijkstra, Bellman-Ford-Moore, and I came up with a doubt.
From what I understood, given a node of a graph, these algorithms calculate all the shortest paths to the other nodes. So, if I block the execution when a specific condition is met, I can get just the shortest path between two nodes.
I don't have problems with Dijkstra but I can't prove this assumption with Bellman-Ford-Moore algorithm. Consider this example:
G = (V,E) directed graph where V = {1,2,3,4,5,6}, E = {(1,3),(1,2),(3,2),(3,4),(2,5),(5,4),(4,6),(5,6)} and each arch has the following costs, respectively: 2,1,3,3,1,2,2,5.

The shortest path between node 1 and node 4 is: 1 -> 2 -> 5 -> 4 whose cost is 4.
If I try to execute BFM on this graph, assuming nodes are added in the queue with this order: 1,3,2,4,5; the result is not what I'm expecting because the algorithm terminates returning the path 1 -> 3 -> 4, whose cost is 5.

This is the pseudocode I'm using:

bfm(GRAPH G, NODE r, NODE s, integer[] T)
   integer[] d <- new integer[1...G.n]
   boolean[] b <- new integer[1...G.n]

   foreach u in G.V() - {r} do
      T[u] <- nil
      d[u] <- inf
      b[u] <- false

   T[r] <- nil
   d[r] <- 0
   b[r] <- true

   QUEUE S <- new Queue()
   Q.enqueue(r)

   while not S.isEmpty() do
      NODE u <- S.dequeue()
      b[u] <- false
      if u = s then return

      foreach v in G.adj(u) do
         if d[u] + w(u,v) < d[v] then
            if not b[v] then
               S.enqueue(v)
               b[v] <- true

            T[v] <- u
            d[v] <- d[u] + w(u,v)

d is a vector to track distances, b is a vector to track which node is currently in the queue, T is a vector of fathers, G.adj(u) returns all nodes adjacent to node u and w(u,v) is the cost function.

Since Dijkstra and BFM algorithms are quite similar, I thought my assumption would be valid for both of them but it seems that I'm wrong. Can you please help me understanding if and how I can use BFM to get the shortest path between two specific nodes?

Thank you so much!


texts: Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA?

texts: Every proof I can find of this result is by way of regular expressions. Is there any "constructive" proof that defines the corresponding DFA (probably NFA)? For instance the proof of concatenation closure is most often presented by demonstrating the NFA. I'm just curious whether this is out there somewhere


texts: Paris-Traceroute and Traceroute Difference

texts:
I am trying to understand the difference between Paris-traceroute and normal traceroute.

I am using this website ( https://paris-traceroute.net/about) and trying to get the idea, what is Paris-traceroute trying to achieve.

If I understand correctly,original traceroute does not care about the flow that is assigned by the load balancers, which is something that Paris-traceroute is trying to solve, so all the probes that are hashed the same way by the load balancers would follow the same path.

However, I don't understand how does that work in the case of UDP. Image at the bottom of the page mentions that Load-Balancers just use Source port and Destination Port in case of UDP, and Paris-Traceroute is trying to use Checksum to navigate same probes through the same path/flow.

Questions:

1) If load balancers only use Source Port and Destination Port, where is the checksum even used? Is it assuming that we should add Checksum to the identification mechanism of each flow? In summary, is it assuming that Load Balancers now use Source Port, Destination Port and Checksum to identify a flow?

2) I don't understand how Traceroute is incrementing a Destination Port, which seems to be claimed on this website. Why would it do that?


texts: Recurrence $f(n+1)=2f(n)-f(n-1)$ with initial values $f(0)=0,f(1)=1$

texts:
How do I solve the following recurrence?
$$
f(0) = 0, \quad f ((1)) = 1, \quad f((n+1)) = 2*f(n) - f(n-1).
$$


texts: In first order logic, how do we normally represent a statement?

texts:
I wanted for an example such as:

Everyone has a mother.

I've seen that it is represented in FOL as: $\forall x \exists y:$ Mother(x, y)

I'm seeing that as:For every x, there exists a y, such that y is a mother of x.

I want to know why isn't the following suitable:

$\forall x:$ hasMother(x)

Which I feel can be said as: For every x, x has a mother.


texts: Selecting objects to maximize value while under multiple constraints

texts:
I think it will be best to explain the problem first and then explain what I am thinking:

I have a dataset similar to the following:

fruit,calories,cost
apple,100,1
apple,200,1.5
apple,150,2
pear,300,3
pear,100,.5
pear,250,2
orange,100,1
orange,120,1
orange,400,2

And I am trying to maximize my calories while keeping my cost within a certain range. At this point it is just a knapsack problem, but what if I have to have 1 apple, 1 pear, and 2 oranges, or some other arbitrary set of fruit numbers?

I can't really wrap my head around how this should work, given the extra constraint. I've thought about trying to merge my cost and calories into 1 metric somehow, but I am pretty sure that can't work since it loses.

My most recent thought is potentially keeping track of fruit count in a list, and if the proper amount of fruit has been reached it will skip to the next fruit. I am thinking about this in a similar way to a knapsack with 3 constraints, weight, value, and size, but the size is just fruit count essentially.

Hoping someone on here can tell me if I am heading in the right direction or if there is an algorithm that does this that I can look into.

Thank you!


texts: Examples of difference between Hidden Markov Model and Bayesian Network?

texts:
I am trying to more deeply understand the difference between Hidden Markov Models and Bayesian Network? The general idea is that HMMs have a single variable which has probabilities of entering different states, known and unknown, whereas the Bayesian network relates multiple random variables.

So, given that, what would examples of particular problems that would be appropriate for each?


texts:
What are the steps required to perform average case analysis?

Basically, how do you attempt average case analysis?

There exists a series of steps that need to be taken to perform it right?

I am just not sure what these are (and can't seem to find any good material explaining how to do it).


texts: Minimum sum of distance from entrance gate

texts:
Assumes we have N position, and 3 entrance gate. For example 10 position:

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

For each entrance gate, there is some people waiting to enter and fill positions, first number is position of gate, associated with chair(front of what chair) and second number is number of people to enter:

5 -> 4

6 -> 2

10 -> 2

If each people seats on chair front of gate, it's cost is 1, for every chair in right or left, the cost increase by 1. What is minimum total sum of cost of people distance to their gates?
For example:

10 (number of chairs)

4 5 ( gate front of seat 4 with 5 people)

6 2 (gate front of seat 6 with 2 people)

10 2 (gate front of seat 10 with 2 people)

Minimum cost is 18. The seats cost is is:

4 3 2 1 2 1 2 0 2 1

Zero means nobody sits on chair 9.

For above example number of gate associated with each people is:

1 1 1 1 2 2 1 0 3 3

Another example:

10

8 5

9 1

10 2

Answer is 24 and positions are:

0 0 7 5 4 3 2 1 2 1

And number of gate associated with each chair is:

0 0 2 1 1 1 1 1 3 3

What algorithm do you propose?


texts:
The effective address for the LDI instruction is the contents of the nearby memory location determined by the PC-Relative addressing mode.
Let's assume that the address 0x5011 contains 1010 100 001000000, and the address 0x5052 contains 0111 0011 0000 1111. I want to find the effective address for the instruction stored in 0x5011.
Step 1:
the nearby memory location = 0x5012 (incremented) + 0x0040 = 0x5052
Step 2:
the effective address for this instruction = contents of the nearby memory location = 0x730F.
So, the effective address for 1010 100 001000000 is 0x730F.
Am I understanding this correctly?


texts: Is it possible to write an AND gate using XOR gates?

texts: How could I express an AND gate using only XOR gates ?


texts:
What does $\tilde{O}_P(N^\alpha)$ mean? It appears in an estimation error mention in this paper, in the second paragraph on page 3.

What does big O subscript P mean in a probability context?


texts: Is there a upper bound on the length of the shortest paths by degree of vertices?

texts:
I would like to know if there is an upper bound on the length of the shortest paths between vertices on an undirected and  unweighted graph based on degree of vertices, number of vertices and number of edges. I consider the shortest paths. So path length is smaller than the number of vertices. I want to know if I can get a better bound with the information of degrees of vertices.

Specifically I have a graph where degree of each vertex is either 1, 2 or 3.


texts: Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths

texts:
Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut (extracted from the final residual network) can also be used to determine the minimum vertex cover:

$$(X\cap T)\cup(Y\cap S)$$

If this expression is a correct alternative, I don't have an intuition for why it's true. The best intuition I've been able to come up with is: Select each vertex on the left (X) that has a positive flow leading up to it and select each vertex on the right if there is no flow leading up to it. Why is this set equal to the minimum vertex cover?


texts: Solving a complicated recurrence relation

texts:
How to solve the recurrence relation below?

$$T(n) = \begin{cases}
             2T(\sqrt{n}) + \log n/\log\log n & \text{if } n > 4\\
             1 & \text{if } n \leq 4.
          \end{cases}$$

Preferably by the master theorem; otherwise by any method. I know the Master Theorem fails, but is there any extension for these type of problems?


texts: Number of Solutions for Brute Force Algorithm of Travelling Salesperson Problem

texts:
We are learning about the travelling salesperson problem in my high school class and we are discussing how computers could solve for the problem, even though the problem is intractable, using a brute force algorithm.
I was wondering if the brute force algorithm calculates ALL possibilities for a number, n, or only UNIQUE possibilities.
For example:
If there were 4 locations, labelled A, B, C & D. Starting from A, would you include both A,B,C,D and A,D,C,B even though they are essentially the same?

Thank you for the help :)


texts: Why do we need so many transistors in a chip, and how are they managed?

texts: My knowledge is very vague as all we have are visual diagrams etc, but we have memory address and registers, the ALU being the heart(apparently). Single core CPUs process one instruction at a time AFAIK and multi-core have parallelism to some degree. So where do the millions of transistors come in and how do 32 registers manage everything. We have FPU's I know, how many transistors would these use roughly. Any way to get a fairly simple idea of what the bulk of the transistors do, why more means faster and how the registers 'manage' everything.


texts: Does FOL extended with least-fixed points satisfy the Compactness Theorem?

texts:
I am aware that first-order logics (FOL) satisfies the compactness theorem. That is, if a FOL theory is insatisfiable, a finite subset of the axioms of such theory is insatisfiable too.
Is it the case that FOL extended with least-fixed point (LFP) satisfies the compactness theorem too?


texts: Performing Transitive Reduction via neighbourhood and strongly connected components

texts:
I am trying to learn(self-study, not homework) how to perform transitive reduction according to what what Prof. Leskovec explains in section 10.8.6 in Mining Massive Datasets. The book is free to access online.

The section is actually talking about a way to perform transitive closure for a graph randomly choosing a node and determining it's strongly connected component(SCC). Though there are further steps on what to do next for using the above to calculate transitive closure, I want to focus on the SCC determination and its role in transitive reduction.

SCC is found for a node v with the following formula,
Given a

graph $G$ and it's reverse graph $G'$
$N_G(v,\infty)$ indicates the neighbourhood of a node $v$ with radius $\infty$ i.e. all the nodes in the graph which can be reached by $v$

then the SCC with $v$ in it is given by $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$

Once you find the SCC, collapse it to a single composite node( composite in the sense that information on which original node was collapsed is still retained) and then modify all the previous edges to point in or out to this single composite node. One repeats the above until the graph size is small and then we use that graph(and the SCC info to find transitive closure). That is the context of this question.

What I don't understand is below. It is mentioned that

  We can iterate the above steps a fixed number of times. We can
  alternatively iterate until the graph becomes sufficiently small, or
  we could examine all nodes v in turn and not stop until each node is
  in an SCC by itself; i.e., NG(v, ∞) ∩ NG′ (v, ∞) = {v} for all
  remaining nodes v. If we make the latter choice, the resulting graph
  is called the transitive reduction of the original graph G.

I don't understand, for transitive reduction, how one can reduce to {v} without losing valid paths which can't be reduced.

P.S - My way of reducing the graph , is for every node v, delete $edge(v,a)$ if there exists $edge(n,a)$ for n in $N_G(v,\infty)$. There is 'currently' no need for SCC.

P.P.S - I am trying to implement this in Apache Spark for parallel computing. If you know of a more suitable algorithm, I would be happy if you could leave some pointers

EDIT: EXAMPLE 1
Consider a cycle with 4 nodes a,b,c,d.
For $v=a$, $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$ is ${a,b,c,d}$
According to the text, for transitive reduction, I have to reduce $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$ to ${a}$.
If I take out any of the edges,e.g. from $d$ to $a$ so that  $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$ is  ${a}$ , it won't be a transitive reduction any more as there is no path from $d$ to $a$ as in the original path. Is my interpretation correct?


texts:
My question is simple: does any body know where can I find the proof that MAX CLIQUE is NP-HARD?

Remarks:

MAX CLIQUE is the decision problem defined as follows:Given a graph $G$ and $k>0$. Does the graph $G$ contain a maximum clique of size $k$?

I have been looking for a formal proof that MAX CLIQUE is NP-Hard, still I haven't found one. The book of Computers and Intractability (Michael Garey) in the final chapters mentions briefly that the full proof is on the phd thesis of Ernet Legget: http://dl.acm.org/citation.cfm?id=907661 . I couldn't find the copy of the book on the internet nor any survey whit the proof.


texts:
So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class.  I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to get a comment on what I believe is a valid proof to this problem.  From what I have seen online and in our review I don't think this is the customary answer to this problem so I want to know if I am applying the concepts behind the pumping lemma successfully.  The problem is not a homework problem and can be found on my professor's previous exams here under the fourth problem of his exam given in Fall of 2011, which is...

Let $L = \{0^p \mid \text{\(p\) is a prime number}\}$. Prove that $L$ is not context-free using the pumping lemma for context-free languages.

So here is my proof:

Assume that the pumping length is $m$, where $m+1$ is a prime number.  I shall also assume that there is a string $uvxyz = 0^{(m/2)}00^{m/2} \in L$.  There are two possible positions that do not violate conditions 2 and  3 of the pumping lemma for context languages, being $|vy| > 0$ and $|vxy| \leq m$.  These are:

$u = 0^{(m/2)}, v = 0, x = 0^{m/2}$, pumping by one results in $0^{m/2}000^{m/2}$.  Since m/2 + m/2 is m, which is one less than the prime number m+1, it is an even number.  m+2 is also an even number and since $|0^{m/2}000^{m/2}| = m + 2$, this number of zeroes is also even and thus cannot be prime, resulting in a contradiction.

The other placement is to place the string on the symmetric opposite or $x = 0^{m/2}, y = 0, z = 0^{m/2}$.  This results in the same contraction as in case 1.

The string cannot be placed in the center such that $v = 0^{m/2}, x = 0, y = 0^{m/2}$ as this would violate condition three or $|vxy| \leq m$, since $|vxy| = m + 1 > m$.
So my question is essentially, is this a valid proof and if not what is wrong with it?


texts:
I have been struggling with this question from my problem set. I do not want a solution but some hints on how to proceed.

  You are given a file of numbers which represent the values of associated with
  certain chemical reactions for the past year from a large scale industrial laboratory (reactions
   can happen on the millisecond scale, so this file is very large). Let $n$
  represent the number of values in the file. For some fixed $k$, devise
  a $\mathcal{O}(n \log k)$ time algorithm for finding the highest $k$
  reactions that occur in the file.

$\textbf{My approach:}$ I reasoned that I should build a max-heap and exploit the get-max() queries and save the $k$ highest values to an array. The time complexity to build a heap is $\mathcal{O}(n)$ and here mentions the extract-max query is $\mathcal{O}(\log n)$ so this operation would run in $\mathcal{O}(n\log n)$ time and not $\mathcal{O}(n\log k)$? Also, I'm not sure why extract-max runs in $\mathcal{O}(\log n)$ time?


texts: Find minimum time path between two nodes

texts:
I am trying to write an algorithm for finding best path for an electric vehicle to navigate through network of chargers.

A graph with Vertices representing charges and Edges representing distances among them is provided
Assume that car drives at constant speed (ex. 80 mph) and has a fixed maximum mile Range when its fully charged (ex. 300 miles)
Each charger has a rate associated with it given in miles/minute (how many miles are added for a minute of charging)
Goal is to go from charger A to charger B in minimum amount of time. Assume car is fully charged when you start.
You can stop at multiple chargers on the way and charge the car. You don't have to fully-charge the car at all chargers. You can decide how much time to spend at these chargers
At any point of time remaining range of the car must stay above 0

Output

Find minimum time path between A and B
List of chargers you will visit starting from A and ending at B.
Time spent charging at each of these chargers
Total travel time in minutes

I tried a solution using Dijsktra's shortest path algorithm, but does not fully solve the problem. I don't need help with coding. I don't need help with coding. I want some insights on how to design the algorithm.


texts: This is a question related to a homework assignment so I guess I'm asking for hints, if that's ok? Basically, I'm wondering if there is some way to use Tarjan to compress the nodes in every SCC found into one single node, essentially producing a DAG. The problem I'm faced with is that every SCC is obtained as a set but I can't seem to find a way to preserve the edges leading out of the SCC.


texts:
This is a follow up to a previous Question (Clarification of definition of class $DisNP$)

The class $DisNP$ has a fundamental problem called the (P-separable) Separator Problem. Essentially the question is as follows:

Given any DisNP-pair $(A, B)$. The separator is a Set $S$ such that $A \subseteq S$ and $B \subseteq Complement(S)$. Now, does  $(A, B)$ have a separator belonging to $P$? If yes, then $S$ is P-separable else P-inseparable.

The Doubt: I assume the above is an existence problem with an answer 'yes' or 'no'. Now, Given we have an oracle that answers 'yes', can we in polynomial time with a polynomial amount of queries get the actual separator $S$ (similar to creation of the solution of an $NPC$ problem using an $NP$ oracle, that just answers 'yes' or 'no'?


texts:
I'm trying to represent a directed acyclic graph using a structure similar to an adjacency list. The difference is, for a given vertex v, I need to know precisely which nodes are inwardly adjacent to v, and which nodes are outwardly adjacent to v. To get around this, my idea was to use a list of pairs, where each pair consists of two sets - which correspond directly to the inward and outward adjacency sets of any vertex in the graph.

I understand that the maximum number of edges in a directed acyclic graph of size $n$ is $\frac{n(n-1)}{2}$. In the proposed graph encoding, the existence of a vertex u in vertex v's 'in' set implies the existence of an edge (u, v). The existence of a vertex u in vertex v's 'out' set implies the existence of an edge (v, u). Additionally, $u \in in(v) \iff v \in out(u)$. Therefore, my intuition tells me that this representation of a directed acyclic graph has a space complexity of $\mathcal{O}(2|E|)$, since the existence of each edge $(v, u)$ is implied twice; once by $v \in in(u)$ and once by $u \in out(v)$.

My question is, does my intuition fail me?


texts:
I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

If problem B is in P and A reduces to B, then problem A is in P.
Problem B is NP-complete if B is in NP and for every problem in A in NP, A reduces to B.
Problem C is NP-complete if C is in NP and for some NP-complete problem B, B reduces to C.

My questions are (if I then II then(?) III/I. If III/I and III/II then IV.)

I: Are there a generalized form to reduces NP problem to either P or NP-complete?
II: Are there a certain number of NP-complete problems?
III/I: Are all of the NP-complete problems can be reduces to all other NP-problems?
III/II: If we can reduce B in NP-complete problem to A in P, can we prove that all problem reduces to B is in P?
IV: If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?


texts: A term for a set of vertices with a small set of neighbors

texts:
Given a graph $G(V,E)$ ans a subset $S\subseteq V$, define $N(S) = $ the set of neighbors of $S$.

Is there a standard term for a subset $S\subseteq V$ for which $|N(S)|\leq |S|$? Is there a standard term for $|N(S)|< |S|$?

I remember once seeing the name expander used for a subset $S$ for which $|N(S)|>|S|$, but I do not find the reference now. Then when $|N(S)|\leq |S|$, $S$ can be called a non-expander, and when $|N(S)|<|S|$, $S$ can be called a contractor. But these are all my inventions. What are the standard terms?


texts: What is the precise definition of pseudo-polynomial time (feat. Counting Sort)

texts:
From wikipedia

  In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required to represent it) and the numeric value of the input (the largest integer present in the input). In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length.

From this SO post

  An algorithm runs in pseudo-polynomial time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.

I have some questions about the wiki definition. To my knowledge, the definition provided by the SO post makes more sense. Shouldn't the wiki say pseudo-polynomial time is if the running time is
1) exponential (or something greater than polynomial) in the length of the input, and
2) polynomial in the numeric value of the input (largest number of input)
??

Assuming you have answered the question of definition above,

I am having trouble analyzing the running time of Counting Sort which is $O(N + K)$ with respect to $N, K$, the numeric values of the input.

Assuming we do not have the $k = \Theta(N)$ simplifying condition, the length of the input is $x = \Theta(N\log(k))$ bits.

The Wiki says "In general, the numeric value of the input is exponential in the input length". But $k = 2^{\Theta(\frac{x}{N})}$. With N potentially bringing down the magnitude of the exponent, I don't really see how $k$ is exponential in $x$.

In addition, the SO post I referenced claims counting sort runtime is exponential with respect to the length of the input, $x = \Theta(N\log(k))$ bits. How can $O(N + k)$ be transformed into an expression exponential in $n$ to demonstrate the claim? I got it down to $O(\frac{x}{\log(x)} + k)$ but got stuck there.

If I just think the length of the input is $\Theta(\log k)$ then I can see why the run-time is exponential but this doesn't seem to be consistent with how $x$ should be defined.


texts: How to change the algorithm implication by changing the invariant?

texts:
I have this specification in GCL:

$[Ctx C: n\geqslant 0\ \wedge\ b:[0..n-1]\ \text{of int}$

$\{Q:\text{True}\}$

$sum,i:=0,0;$

$\{\text{Invariant}\ P: 0\leqslant i \leqslant n\ \wedge sum=\sum_{j=0}^{i-1} b[j]\}$

$\{T:n-i\}$

$do\ i\neq n \rightarrow\ sum, i:=sum+b[i],i+1;\ od$

$\{R: sum=\sum_{j=0}^{n-1} b[j]\}$

$]$

But then I have been requested to develop the same summation of the numbers located in $b$ but with the following invariant and dimension function ($T$):

$\{\text{Invariant}\ P: 0\leqslant i \leqslant n\ \wedge sum=\sum_{j=i}^{n-1}
b[j]\}$

and

$\{T:i\}$

But I don't how to proceed. What I firstly supposed is that the summation must be done in reverse order.

Some suggestion, ideas?


texts: Convert finite automata to regular expression

texts:
I am trying find the regular expression that describes the finite automata in the image below.
Given the following finite automata
which of the following regular expressions describes the same language as the automaton.

(ab)+c*d+
a+b+c*d+
a(ba)*bc*dd*
[ab]+c*d+
a(ba)*bc+d?d+
(ab)+c+d*

I tried converting it to a regular expression and I got (ab)*ac*dd*, which is not among any of the options. Could someone help me select the correct answers?


texts:
This is third-hand, so please bear with me.  A collaborator was at a review meeting where he heard another participant make the claim that given an assignment for a SAT problem that satisfies (some high percentage) of clauses, there are polynomial time algorithms that finish the problem.

Is this true?  Can someone point me to some references?


texts: Classification of the Summit supercomputer

texts:
Can we classify a supercomputer in more than one group? For example, Flynn's classification, classification according to topology, classification according to memory access.
For the Summit supercomputer, I have found no sources on these topics, except for Flynn's classification. How can I classify it in other categories, for example by topology?


texts: The min cut capacity in a network based on a bipartite graph (Hall's Theorem)

texts:
Thanks to Yuval Filmus, I got to read these lecture notes by Trevisan. At the bottom half of Page 5,

  The capacity of cut $S$ is the number of edges that go from $S$ to $\overline{S}$, that is $\text{Capacity}(S) = |L_2|+|R_1|+\text{edges}(L_1, R_2)$.

Here, $L_1 = S \cap L$, $L_2 = L \setminus S$, $R_1 = S \cap R$ and $R_2 = R \setminus S$. Furthermore, $L$ are the left edges and $R$ are the right edges.

I don't understand how he arrived at the conclusion that

  number of edges that go from $S$ to $\overline{S} = |L_2|+|R_1|+\text{edges}(L_1, R_2)$

I don't understand the meaning of this expression. I drew it out on paper (highlighting all graph elements of the expression) and I still don't get it. Could somebody please explain to me how this expression is generated in simple and detailed terms?


texts: solving ()=(/3)+(/6)+1 without Akra-bazzi method

texts:
I need to find $g(n)$ so that $()=(/3)+(/6)+1 = \Theta(g(n))$.
I know that the recursion tree height, $h$, is $\lg_6{n}\le h \le \lg_3{n}$ and that every level of the tree has at most $2^d$ nodes each contributes 1 to the final equation. going by that I get $$\sum_{i=0}^{\lg_6{n}}2^i\le T(n)\le \sum_{i=0}^{\lg_3{n}}2^i\le \lg_3{n}\cdot 2^{\lg_3{n}}=\frac{\lg_2{n}}{\lg_2{3}}\cdot n^{\frac{1}{\lg_2{3}}}$$
but by using Akra-bazzi method I get $p\approx 0.4895$ and $T(n) = \Theta(n ^ {0.4895})$ which doesn't have $\lg{n}$.
How can I get $\Theta$ notation for $T(n)$ without using Akra-bazzi method?


texts: How to design a simpler Version of CARDIAC (Cardboard Illustrative Aid to Computers)?

texts:
I'm trying to make a simpler version of CARDIAC for only performing addition. Now, I am encountering several problems in making something similar and looking for some ideas (I'm new to Computer Architecture).

Here's an excerpt of what CARDIAC is (Wikipedia):

  CARDIAC (CARDboard Illustrative Aid to Computation) was a learning aid
  developed by David Hagelbarger and Saul Fingerman for Bell Telephone
  Laboratories in 1968 to teach high school students how computers work.
  The kit consisted of an instruction manual and a die-cut cardboard
  "computer".
           The computer "operated" by means of pencil and sliding cards. Any arithmetic was done in the head of the person operating the
  computer. The computer operated in base 10 and had 100 memory cells
  which could hold signed numbers from 0 to ±999. It had an instruction
  set of 10 instructions which allowed CARDIAC to add, subtract, test,
  shift, input, output and jump.

Basically it's a simple illustration of how a computer works internally to do basic stuff(as explained in the excerpt). I'm only trying to do addition but I am trying to find a way to show what the output is.
Here's how I thought it would be:
I would use a 16-bit register with binary base and 10 memory cells. I  guess this should be more than enough for a basic addition illustration.

Now my problem is, I'm not very sure how to output the values. Let's say for example, I input 10(binary for 2) in register R1 and 1(binary for 1) in register R2. Now this goes to the ALU, which calculates the addition immediately and places it in register R3. This would be represented using arrows and sliding cards(values for R1, R3 and R3) in specific slots on the illustration.

My problem is, now that I have the value in R3, how do I output it using that cardboard illustration? Also, does the ALU work as logic gates to calculate the sum?


texts: Is there such a notion as "effectively computable reductions" or would this be not useful

texts:
Most reductions for NP-hardness proofs I encountered are effective in the sense that  given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by using reductions. All reductions in the 21 classic problems considered by R. Karp work this way. A very simple example might be reduction from INDEPENDENT_SET to CLIQUE, just built the complement graph of your input.

But when considering the proof of the famous Cook-Levin Theorem that SAT is NP-complete, the reduction starts from a non-deterministic TM and some polynomial, that exists by definition. But to me it is not clear how to get this polynomial effectively, meaning given an non-deterministic TM from which I know it runs in polynomial time, it is not clear how to compute this polynomial, and I highly suspect it is not computable at all.

So soley from the encoding of NP-complete problems by the class of non-deterministic polynomial time TMs (the polynomial itself is not encoded as far as I know) I see no way how to give a reduction in an effective way, the aforementioned proof just shows that there exists some, but not how to get it.

Maybe I have understood something wrong, but I have the impression that usually the reductions given are stronger in the sense that they are indeed computable, i.e. given a problem we can compute our reduction, and not merely know its existence.

Has this ever been noted? And if so, is there such a notion as "effectively computable reduction", or would it be impractical to restrict reductions to be itself computable? For me, from a more practical perspective, and also the way I sometimes see reductions introduced ("like we have an algorithm to convert one instance to another") it would be highly desirable to know how to get this algorithm/reduction, so actually  it seems more natural to demand it, but why is it not done?


texts: Proving/Disproving that language L is non-regular/CFL

texts:
Here are three examples of questions I run into. I'm not looking for solutions.

  If $L$ is CFL then $L' = \{ ww^R | w \in L \}$ is non-regular.
  If $L$ is non-regular then $L' = \{ ww^R | w \in L \}$ is non-regular too.
  If $L_2, L_3, L_4$ are regular languages and $L_1 \cup L_2 = L_3$ and $L_1 \cap L_2 = L_4$, then $L_1$ is regular.

The problem I'm facing here is that I'm having hard time to figure out what how to prove such claims.

Lets say I'd like to prove claim 1, I can't seem to understand what exactly should I prove?
If I assume that $L'$ is regular, then what way can I follow that will lead me to contradiction? I would go for the intersection with CFL language, but this won't help me as CFL is closed under intersection with regular languages. So I'm pretty lost here.

Take claim 3 for example, after spending a lot of time trying to find a counter-example, I have strong feeling that this claim is true. (please don't tell me if I'm wrong, this post is not about the answers). Yet I couldn't find out what exactly should I prove? Of course that $L_1$ is regular but in what way may I do that?

I hope you get my situation. What I'm asking from you is to describe how would your proof be written in the above claims? What would you try to archive in your proof?

Thanks a lot for your time.


texts: Proving correctness of search algorithms

texts:
I've seen correctness proofs for other searching algorithms; however, for this particular algorithm: search in a row-wise and column wise sorted matrix, I'm not able to generate a proper proof.

The algorithm is

Let x = element we're trying to search for in the matrix,
    e = current element we're processing in the array.
1) Start with the top right element.
2) Loop: compare this element e with x
...i) if e = x, then return the position of e, since we found x in the given matrix.
...ii) if e > x then move left to check elements smaller than e (if out of binding of the matrix, then break and return false)
...iii) if e < x then move below to check elements greater than e (if out of binding of the matrix, then break and return false)
3) repeat the i), ii) and iii) until you find the element or return false

Essentially, we start from the top right and traverse to the bottom left, key points being if element we're searching for is smaller then we go left if it's bigger we traverse down.

I'd like to use contradiction by saying the following: "If we traversed all the way to the bottom left of the algorithm and we didn't find the element we're searching (assuming it's in the matrix), then ..."

However, I'm not sure how to properly follow up the "then" because whatever I say is just repeating what the algorithm does, not really proving anything.

Is there a proper way to do this? Perhaps induction? (but this seems ever more complicated)


texts: Why there is forward chaining inference engine (reasoner) for description logics only and not for other logics?

texts: Reasoner is forward chaining inference engine (https://en.wikipedia.org/wiki/Semantic_reasoner) as opposite to Prolog backward chaining SAT solver (for queries). Why there is reasoner for description logics and not for other logics?


texts:
What are the consequences of proving some relation ($\subseteq$, $\subset$, $=$, or $\neq$) on one of the following, to the other?

$P$ vs. $BPP$
$P$ vs. $NP$


texts: Completeness of formal definition of 'hardness on the average'

texts:
While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for simplicity.)

Definition : Hard on the average :
$h:\{0,1\}^*\to \{0,1\}^* $ is hard on the average if there exists a probabilistic polynomial-time algorithm $G$ such that
for every probabilistic polynomial-time algorithm $A'$ every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s,  Pr$[A'(X_n)=h(X_n)]<\frac{1}{p(n)}$
where $X_n := G(1^n)$ is a random variable assigned the output of $G$.

My question is why the statement of the existence of qualified algorithm G is sufficient?
In other words, why the above definition gives a formal definition of 'hardness on the average' instead of following definition, which is more intuitive(?) to understand and more strict.
Why is the above definition sufficient?
( Now I'm thinking that problem might occur when $G$ has only polynomial number of possible outputs, but if so, let's replace 'for any $G$' with 'for any $G$ which have exponentially many possible outputs' in following definition.)

(strong?) Def : Hard on the average :
$h:\{0,1\}^*\to \{0,1\}^* $ is hard on the average if for any probabilistic polynomial-time algorithm $G$ and for every probabilistic polynomial-time algorithm $A'$ every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s,  Pr$[A'(X_n)=h(X_n)]<\frac{1}{p(n)}$
where $X_n := G(1^n)$ is a random variable assigned the output of $G$.

Another question is that whether a following simpler definition is equivalent to original definition or not?

(simple) Def : Hard on the average :
$h:\{0,1\}^*\to \{0,1\}^* $ is hard on the average if for every probabilistic polynomial-time algorithm $A'$ every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s,  Pr$[A'(U_n)=h(U_n)]<\frac{1}{p(n)}$
where $U_n$ is a random variable uniformly distributed over $\{0,1\}^n$.


texts:
Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this:

  Suppose $L$ is a language which includes an infinite list $c_1,c_2,\cdots$ of constant symbols. Let $\Gamma$ be a set of sentences $\Gamma = \{c_i \neq c_j \mid i,j\in N, i < j\}$. Let A be a sentence such that $\Gamma \Rightarrow A$. Prove that $A$ has a finite model.

I am not sure whether I would prove this via a contradiction (i.e., assume $A$ has an infinite model, or if I show a finite model that works or some how assume that we can have an infinite model and then use some sort of compactness to show it can be finite. I am a little all over the place with this question, please any help would be great!


texts: Do problems in P only reduce to NP and coNP problems?

texts:
Consider the languages $B,C,D$, such that $B\le_p C$ and $B\le_p D$.
Statement: $B\in P, D\in NP, C\in coNP$.

  Is the statement true for every $B,C,D$?

I know that the answer is no and I have tried to come up with a conunter-example.
I thought about taking $D\in NPC$ or $C \in coNPC$ but that didn't yield anything good.


texts: When to send a message on distributed systems emulating a FIFO network?

texts:
We designed in the lecture of Distributed algorithm an algorithm to emulate a FIFO network as far as an asynchronous network isn't unavoidably FIFO.

Yet I have some difficultes to understand the condition of sending messages. Here is the algorithm:

Facteur_i

Begin
    While(True)
        Wait (buffer_i.test(T,∀k, connaissance_i[k,i]≥T[k,i]);
        Buffer_i.extract(`<j,c,m`>);
        connaissance_i=Max(connaissance_i,c);
        // max by element
        connaissance_i[j,i]++;
        deliver_from(j,m);
    End While
End

I don't understand these two lines:

Wait (buffer_i.test(T,∀k, connaissance_i[k,i]≥T[k,i]);
Buffer_i.extract(`<j,c,m`>);

Here is the description of the algorithm

  Every site maintains an array $connaissance_i[j,k]$ the number of messages emited by $j$ to $k$ which arrive before  a message emited by $i$. The value of the array go along every message sent. When receiving a message $m$, service of site $i$ determines if it has received every message that precedes causally $m$ comparing component by component the column of his own array with the one of message $m$. If this is the case, it delivers it and update his array. taking the maximum of both array (which is the equivalent of fusionning lists). Taking into account this message.

The other functions are

emit_to(j,m)
on_reception_from(j,(c,m))

primitives are

emit_to(j,m)
deliver_from(j,m)

Can you help me understand the condition of sending a message on distributed systems emulating a FIFO network?

I can provide more details if needed!


texts: Is there a standard way to do Debrujin indices for an uncurried language?

texts: With Debrujin indices, variable names are replaced with numbers that indicate which function binds them. This works fine if each function only binds one variable, but what if one's language is not curried? Is there a standard terminology and method of working with such things?


texts: Bridge determination in undirected graphs

texts:
A bridge (critical edge) in an undirected graph is an edge whose removal increases the number of connected components.

I need to determine all critical edges in an undirected graph, in $O(V+E)$ time. From what I found out, I need to use a modified DF search, but all pseudo-code algorithms I found have low[v] and d[v] which I don't understand.

Can someone please explain to me the $O(V+E)$ bridge determination algorithm?


texts: Problem with the motivation of penalized logistic regression

texts:
The following is a motivation for penalized logistic regression in some lecture notes I'm following:

  Although  the  cost-function  for  logistic  regression is lower
  bounded by 0 we get issues if the data is linearly  separable.

That part I can understand it well because the logistic regression cost-function is taken to be minus some probability so that it must be greater than 0

  In  this  case  there  is  no  finite-weight vector w which gives us
  this minimum cost function and if we continue to run the optimization
  the weights will tend to infinity. To  avoid  this  problem,  as  for
  standard  regression problems,  we  can  add  a  penality  term.

Why is that if that is linearly separable there is no minimum of the cost function and that the weights go to infinity?

Please ask for any details you may need on this problem. If it is any help the cost function that is being considered is:

$L(w) = \sum_{i=1}^{N} [\ln(1+\exp(x_{n}^{\top}w) - y_nx_{n}^{\top}w]$

Also the lectures notes can be find here. The issue is on page 13.


texts:
I can not understand the following equality   $$\langle ij|(|0\rangle \langle 0|\otimes I)kl \rangle= \langle i|0\rangle \langle 0|k \rangle \langle j|I|l \rangle?$$

Also to estimate phase $\phi$ in Nielsen & Chuang book, I can not understand why
$(|0 \rangle + e^{2\pi i 2^{t-1}\phi} |1 \rangle)(|0 \rangle + e^{2\pi i2^{t-2}\phi }|1 \rangle)\cdots (|0 \rangle + e^{2\pi i 2^{0}\phi} |1 \rangle)= \displaystyle\sum_{k=0}^{2^t-1}e^{2\pi i \phi^k} |k\rangle$.

Will you kindly help me?


texts: Relational Database to Aggregate Data Model

texts:
Can any application currently using a relational database be rewritten to use an Aggregate Data Model, by Focusing on data modelling aspects only (ignoring other features like salability or transaction handling)?

Why / Why not?


texts: Decision tree complexity of finding parameters of "zigzag" array

texts:
I am currently studying for a test on data structures.
I have to find the lower and upper bounds for the following problem:

An array is called a zigzag array if there are $1 \leq i \leq j \leq n$ so that the array increases from $1$ to $i$, decreases from $i$ to $j$, and increases from $j$ to $n$.
Input: a zigzag array.
Output: the position of $i$ and $j$.

My answer:

Upper bound: just going on the array and finding $i$ and $j$, which takes $O(N)$.
Lower bound: I think that we need to find pairs $i$ and $j$ for which $k$ is bigger than $i$ in $n$ elements, I don't know how to solve it.


texts: Is it decidable whether the language of a given CFG contains a palindrome?

texts:
Given a context-free grammar G. Is it decidable, if the language $L(G)$, which is generated by G, contains a palindrome?

My suggestion is, that it is undecidable, but I do not have an idea for a formal prove. Any hints?


texts: Relation between Hoare Type Theory and pointers

texts:
My understanding is that in Hoare Type Theory every imperative statement has a type of the form {Pre}res:T{Post} where T is the type of the result of the computation and Pre and Post are propositions representing respectively the pre and postconditions of the statement and res is the result of type T which can appear in the postcondition.

Given the following program in pseudo-C:

int i=0;
int*p=&i;
*p=1
return i;

How can Hoare type theory represent the the fact that i must be 1?After all,it's not clear i is modified in the above snippet,and it can be hidden even from the programmer if we begin to add lambdas and partial application


texts: What is a minimal, pseudo-random hash function?

texts:
I want to generate pseudo-random hashes of inputs in a way that is optimally time and space efficient.

I'm not at all concerned about security.  The output should be evenly distributed and appear random in relation to the input, but it doesn't matter if it's possible - even trivially possible - to determine the input that produced a given output.

Most hash functions are designed to be used for cryptographic purposes; they can be used for a task such as this but are not particularly fit for the purpose: they are complex to implement, they are (often intentionally)  slow, and they guarantee many properties that are of no concern, such as non-reversibility.  A smaller, faster algorithm surely exists that does not waste space and time guaranteeing these properties.

Non-cryptographic hash functions such as the Mersenne Twister or WELL are closer to what I'm looking for, but they're state-permuting PRNGs rather than true hash functions - you can't get the MT hash value of 1 and then the MT hash value of 624001 without running 1000 twist operations to advance its state.  Yes, you can use a state-permuting PRNG to emulate a hash function by just running it N times (or N mod period times) for an input of N, but it requires either a huge amount of time or a huge amount of precomputation or both.  And even if you ignore that issue, such functions are... well, they're faster than cryptographic hashes, but they still make gaurantees that the problem doesn't require.

Optimally, what I'm looking for is something like return (seed ** (1.1 + 1/seed)) % 1 - it convolutes the input to produce an output
0..1 and it does it with 4 arithmetic operations and no state.  This particular example isn't a good solution because it appears to skew significantly towards certain results.  Is there something similarly fast and small (or at least, faster and smaller than the other options I'm aware of) that actually works?


texts: Build a context-free grammar for a context-free language

texts:
A context-free language is defined by its description:

$L=(a^{2k} \space  b^n \space c^{2n} \mid k \geq 0, \space n > 0)$

For example:

$bcc, aabcc, aabbcccc, bbcccc$

How to build a context-free grammar for this context-free language?

I suppose that the order for generating any chain in this problem matters: 'b' will always stand after 'a' and 'c' - after 'b'. Is it so?

My attempts leaded to this solution:

$ S \rightarrow aaAbcc \mid bAcc \mid aabAcc $

$ A \rightarrow aa \mid bcc \mid λ $

Please correct me if I'm wrong or better offer your solution to this problem.


texts: Why is the log in the big-O of binary search not base 2?

texts:
I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency.

In a size of $s = 2^n$ elements, it would take, on average, $n$ steps to find a particular element. Taking the base 2 logarithm of both sides yields $\log_2(s) = n$. So wouldn't the average number of steps for the binary search algorithm be $\log_2(s)$?

This Wikipedia article on the binary search algorithm says that the average performance is $O(\log n)$. Why is this so? Why isn't this number $\log_2(n)$?


texts: How can instruction fetch and decode pipeline stages run simultaneously in a CPU with dynamic branch prediction?

texts:
I have recently been investigating CPU pipelining and branch prediction and have a question about how exactly these fit together.

If, for example, instructions are meant to be fetched in one stage of the pipeline and decoded in the next while the next instruction is fetched simultaneously, how is it possible for the pipeline to proceed without a stall when dynamic branch prediction is in operation?

As an instruction must be decoded before branch prediction can occur or be deemed unneeded, and as any prediction must be made before the next instruction can be fetched, how can an instruction be decoded while the next instruction is fetched in the same clock cycle?


texts: Complexity of finding binomial coefficient which equals to a number

texts:
Assume you are getting a number $m$ (using $O(\log m)$ bits in binary encoding).

How fast can you find (or determine such does not exist) $$n,k\in \mathbb N, 1<k\leq\frac{n}{2}:{n \choose k}=m$$
?

For example, given the input $m=8436285$, one may output $n=27, k=10$.

A naive algorithm for the problem would go over all possible values for $n$, and search for a value of $k$ which satisfies the property.

A simple observation is that there no need to check values of $n$ smaller than $\log m$ or larger than $O(\sqrt m)$. However (even if we could check only $O(1)$ possible $k$ values per $n$ value) this ends up in an inefficient algorithm which is exponential in the input size.

An alternative approach would be to go over the possible values of $k$ (it's enough to check $\{2,3,\ldots,2\log m\}$) and for each check for possible $n$ values. We can then use:
$$\left(\frac{n}{k}\right)^k<{n\choose k}< \frac{n^k}{k!}$$

So for a given $k$ we only need to check $n$ values in the range $[\sqrt[\leftroot{-2}\uproot{2}k]{m\cdot k!},\sqrt[\leftroot{-2}\uproot{2}k]{m}\cdot{k}]$, Doing so using binary search (when $k$ is fixed, $n \choose k$ is monotonically increasing in $n$), this gives a polynomial algorithm running in $O(\log^2m)$.

This still seems inefficient to me and I guess that this could be solved in linear time (in the input size).


texts: PDA for a language where the second part is not the reverse of the first part

texts:
I came across an exercise for constructing a PDA for the following language:
$$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$
Where $L \subseteq ({a,b,c})^*$
So $n$ and $m$ are both a combination of any number of $a$'s and $b$'s, but $n$ is not the reverse of $m$.
Does anyone have some tips or advice, would be much appreciated!


texts: Is it "valid" for semantic functions to query outside of the grammar in attribute grammars?

texts:
Is it valid (in the sense of formal grammars or formal language theory) to refer to outside of the grammar in attribute grammars?

What I mean is that since attribute grammars can contain semantic functions e.g.

  E1 → E2+T { E1.val := sum(E2.val, T.val) }

then could there (in the place of the sum function) be a function that does e.g. a SQL query?

Should add that this is technically feasible, but I want to know that if it's reasonable and in accord to the theory of attribute grammars and the practice of semantic analysis.


texts: Is the heap in "Data Structures Algorithms in Java" by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?

texts:
In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an

"Example of a heap storing 13 entries with integer keys. The last position is the one storing entry (13,W)."

I've recreated the a similar image using qtree-tikz with my own depth and height calculations in the box on the left.

According to the book,

A heap T storing n entries has height $h = \lfloor \log n \rfloor$.
Justification: From the fact that T is complete, we know that the number of nodes in levels $0$ through $h-1$ of T is precisely $1+2+4+...+2^{h-1} = 2^{h}-1$, and that the number of nodes in level $h$ is at least 1 and at most $2^h$. Therefore
$n \geq 2^h -1 +1 = 2^h$ and $n \leq 2^h -1 +2^h = 2^{h+1} -1$.

Here is where I see a problem. I added the depths and heights for nodes at each level according to my understanding of trees in the box to the left of the tree. The example tree Figure 9.1 shown above obviously has 7 inner nodes and although depth level 3 would have 8 nodes, it is unfull at 6 nodes.
If I follow the "Justification", I end up with the following

"we know that the number of nodes in levels 0 through $h-1$ of T is $2^h-1$"

$2^2 -1  = 3 \neq 7$.

but my understanding is that the $7$ would match the formula $2^3-1$, which means the $h$ referred to in the text must be $h=4$. But the $h =3$   from my understanding. Herein lies the problem.

I am being forced to conclude that there must be a missing level of sentinels,
$2^3 -1 = 7$ and the only way to get a power of 3 in those formulas is to have a height of 4. But why on earth would the authors, who otherwise explain everything in detail, not make important piece of information explicit? Or, did I miss something? I would appreciate a thorough explanation to help me understand the proof. It also seems that the authors throw around the term "level" loosely, sometimes meaning depth level and sometimes meaning height level.
I should also mention that earlier in the book, on page 286, they provide a definition for the height of a tree without any examples (and it is a bit cryptic).

We next define the height of a tree to be equal to the maximum of the depths of its positions (or zero, if the tree is empty).

If $p$ is a leaf, then the height of $p$ is $0$.
Otherwise, the height of $p$ is one more than the maximum of the heights of $p$'s children.


texts: maximum bound for edges in graph $G$ if we want shortest cycle stay at $k$

texts:
In a simple graph $G$, what is the maximum bound for edges if we want shortest cycle stay at $k$.

How we can find this bound for a graph? Have it any formula or technique to calculate it?

thanks in advance


texts:
HSV colors are composed of a triple of numbers: hue $\in [0, 360)$ (in degrees), saturation $\in [0, 1]$ and value or brightness $\in [0, 1]$. RGB colors instead are more well-known and are also composed of a triple of numbers all of them in the range $[0, 1]$ or in a byte $[0, 255]$.

I was trying to implement an algorithm that converts HSV colors to the corresponding RGB ones, and I managed to do it based on the following algorithm provided by Wikipedia. (I'm reporting the whole related text).

  $C = V \times S$

  \begin{align}
 H^\prime &= \frac{H}{60^\circ} \\
 X    &= C (1 - |H^\prime \;\bmod 2 - 1|)
\end{align}

   ($R_1$, $G_1$, $B_1$) =
    \begin{cases}
   (0, 0, 0) &\mbox{if } H \mbox{ is undefined} \\
   (C, X, 0) &\mbox{if } 0 \leq H^\prime < 1 \\
   (X, C, 0) &\mbox{if } 1 \leq H^\prime < 2 \\
   (0, C, X) &\mbox{if } 2 \leq H^\prime < 3 \\
   (0, X, C) &\mbox{if } 3 \leq H^\prime < 4 \\
   (X, 0, C) &\mbox{if } 4 \leq H^\prime < 5 \\
   (C, 0, X) &\mbox{if } 5 \leq H^\prime < 6
  \end{cases}

  Finally, we can find $R$, $G$, and $B$ by adding the same amount to each component, to match value

  \begin{align}
 &m = V - C \\
 &(R, G, B) = (R_1 + m, G_1 + m, B_1 + m)
\end{align}

where $H$ is the hue, $V$ is the value, $S$ is the saturation, $C$ is what Wikipedia calls the chroma and $R, G, B$ are correspondingly the values of red, green and blue.

Before wanting to find a way to convert HSV colors to RGB Colors, I had already a formula to convert RGB colors to HSV, which I wanted to manipulate to obtain a inverse formula, but I didn't manage to do it.

Here's a picture:

I could show you my attempts, but they are not useful.

Question

How is the formula (provided by Wikipedia) to convert a HSV to RGB colors derived from the formula in the picture above to convert RGB to HSV colors?

I'm asking this question here because I'm looking for a mathematical manipulation of one formula to arrive at another. I'm also asking this question because I think it could be interesting also for others. If you think this question should be moved to another stackexchange's website, feel free to migrate it or just tell me and I will post it where you indicate me.


texts: Divide and conquer problem:sequence of integers (with possible repetitions)

texts:
I was trying to solve this problem.
Let $A[1] . . . , A[n]$ an ordered sequence of integers (with possible repetitions) and let $k$ be any integer. A contiguous subsequence $A[i], A[i + 1], . . . A[j]$ of $A$ is $k$-separated if the difference between every pair of its consecutive elements is at most $k$.
For example, if $A = [1, 3, 3, 4, 4, 4, 5, 7, 8]$, then the contiguous subsequence $3, 3, 4, 4, 4, 5$ is $1$-separated but not $0$-separated.
We would like an algorithm that given $A$ and $k$ as input returns the length of the longest contiguous k-separated subsequence.
Some examples:

Input: $A = [1, 3, 3, \textbf{4, 4, 4}, 5, 7, 8]$, $k = 0$. Output: $3$ (longest contiguous $0$-separated subsequence has been hightligthed)
Input: $A = [1, \textbf{3, 3, 4, 4, 4, 5}, 7, 8]$, $k = 1$. Output: $6$ (longest contiguous $1$-separated subsequence has been hightligthed)

This can be solved in $O(n^2)$ with a nested loop that checks all possible contiguous subsequences but we would like to do
better.
I understand that I need to split my array in 2, but after that I don't know how to find the condition to select first half or second.
How will be the algorithm to find the correct answer? Any help it's welcome.


texts:
What is the complement of $\mathrm{ACFG} = \{ G \mid G \text{ is a CFG and }L(G) = \Sigma^* \}$?

I think it is $\mathrm{ECFG} = \{ G \mid G\text{ is a CFG and }L(G) = \emptyset \}$.

It makes sense to me because the complement of the empty language is the universal language?

Am I correct?


texts: Greedy algorithm to divide objects into the lowest number of groups of a maximum size

texts:
I have n objects of independent size s, and need to group them so that the sum of the sizes of each group is smaller than a given maximum size, and the number of groups is the smallest possible.

I already tried a brute force algorithm that orders the objects in all possible permutations and then, based on their size and the group max size, divides every permutation in groups based on the order. This algorithm is very slow and therefore I want to find a greedy one, but being new to the topic I can't think of a good way to start.

My idea would be to start building the first group from the largest object, and then adding more so that every time I add a new one, the difference between the max size and the size of all the objects in the group is minimized. Is this a good starting point?


texts: Isn't this Commentz-Walter algorithm buggy?

texts:
I've been trying to piece together an implementation of the Commentz-Walter string search algorithm. The idea is to construct a state machine from a trie, working backwards from the earliest feasible position.
The paper is available here, though it is a scanned printout from 40 years ago. I have also found a better quality pseudocode for the core search loop (image below). But it seems that neither description of the algorithm provides a way to 'back out' of a dead end: The current trie node v is only ever assigned to its own child. It seems that there is a missing step: once the inner loop has exhausted the possibility of a match, the current node should be changed.
An example of an input that fails my implementation tests is to find the string bb in abb: The search begins on the first b, finds that ab is invalid, and fails
Can anyone put me right?

Pseudocode of search algorithm:


texts: Building automaton from regular expression

texts:
Let $L=a(a+b)^*b$, a regular expression. I will try to build the automaton by the $a^{-1}L$, $b^{-1}L$ rule

$a^{-1}L = \{a,b\}^* b=M$.
$b^{-1}L=\emptyset$.
$a^{-1}M=b\cup\{a,b\}^*b=N$.
$b^{-1}M=\{\varepsilon\} \cup \{b\}\cup \{a,b\}^*b = P$

But why are the result of 3 and 4 when doing $a^{-1}M$ and $b^{-1}M$ as given?


texts: Hashing algorithm which minimizes distribution

texts:
Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets B1, B2 ... BN where each property needs to be mapped. We have the following constraints -

total number of properties >> number of applications

total number of properties >> number of buckets

number of buckets ~= number of applications

Is there a hash algorithm which minimizes the number of distinct application each bucket is mapped to while still guaranteeing even distribution of properties? In other words, if one of the buckets were to be hidden temporarily, the number of distinct applications affected should be minimal.


texts:
Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$.

I am interested in polynomial-time invertability of Karp reductions between natural NP-complete problems.

  Is it true that every Karp reduction $f$ is also polynomial-time invertible (i.e. $f^{-1}$ is polynomial-time computable)?

To clarify, Is there a Karp reduction $f$ between two natural NP-complete problems where its inverse $f^{-1}$ is not known to be polynomial-time computable?

Natural problem means that the problem is not an artificially made up problem to answer the question (or similar ones) and people are interested in the problem independently (defined by Kaveh).

P.S. It is known that all known Karp reductions between natural NP-complete problems are injective (or can easily made injective).


texts: How many decidable decision problems are there?

texts: Is there a "intuitive" way of understanding how many possible decidable problems there are, given some formal language to describe them?


texts: Relativization results in class separation

texts:
We know that $P\neq NP$ problem cannot be demonstrated by relativization because there exists oracle relative to which they are equal.

Is there natural complexity classes that has been shown to be equal but are separate under some oracle?


texts: Why gap preserving reduction is weaker than L-reduction?

texts:
In Vizirani's textbook says in page 332,

  Gap preserving reductions are weaker than their L-reductions [...] one of the motivations for the PCP theorem was that establishing an inapproximability result for MAXSAT would directly yield inapproximability results for all Max-SNP-hard problem.

Now my question is: Why Gap preserving reduction is weaker than L-reduction? as a person to prove a reduction, then Gap reduction is better than L-reduction to give lower bound. Moreover, Gap reduction gives you better result than L-reduction (e.g. vertex cover is inapproximable with number close to $1.3 - \epsilon$ using Gap-reduction while using L-reduction there is no known "as far as I know" reduction that gives inapproximable even less than 2. So, it seems for me that Gap-reduction is better, and thus it is stronger than L-reduction in terms of given lower bounds. Now, why he says "Gap preserving reduction is weaker than L-reduction?" or may be he means something else, then could you explain to me.

Or does he mean the following:
suppose we have two reductions: Reduction A, B. Then, A is better than B if B in included in the A as subset (so A is big class and B is small and subset of A). In this case, A will give better bound (;because it is bigger while B gives not better than A because it is smaller). Is this what he means?! [in this case A=gap reduction, B=L-reduction].


texts: Halting problem reduction to Halting for all inputs

texts:
I was going through my book of revision and I would like someone hints on this.

The Halt for All Input problem (HAI) takes a machine and tell if this machine halts or not for any input
We prove it is unsolvable by proving it reduces to the halting problem

The book says:

Build a $M'$ that does the follwoing
$M'$ erases its input (?)
$M'$ writes I on its tape (did we not just erased this?)
$M'$ simulates $M$

Can someone explain this reduction?


texts: Does an algorithm with complexity $\Theta(2^\sqrt{n})$ to solve any NP problem count as "good" and practical as any other polynomial algorithm?

texts:
If the complexity of an arbitrary algorithm to solve any NP problem after analysis is $\Theta(2^\sqrt{n})$ then is this algorithm considered as "good" and practical algorithm?

I know that in algorithm analysis and computational complexity theory every algorithm with any polynomial complexity is considered as "good" and practical algorithm, although in mathematics and calculus $2^\sqrt{n}$ isn't polynomial by definition, but so $n\log n$, but $\Theta(n\log n)$ counts as "good" and practical algorithm to solve any NP problem.

I have already graphed the functions: $x, x\log_2x, x^2, 2^\sqrt{x}$ and $x^3$ by using some online function plotter, and for some large $x$, it appears that $ x^3>2^\sqrt{x}>x^2>x\log_2x>x$

So I think that $\Theta(2^\sqrt{n})$ is practical and "good" as $\Theta(n\log n)$ is, although both of them are not polynomial by definition.

Am I right?


texts: Reference on relating Post systems to string rewriting systems and formal grammars?

texts:
wikipedia states:

Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...]
It has been proved that any Post canonical system is reducible to such a substitution system, which, as a formal grammar, is also called a phrase-structure grammar, or a type-0 grammar in the Chomsky hierarchy.

And on a different page it says:

A semi-Thue system is also a special type of Post canonical system, but every Post canonical system can also be reduced to an SRS.

I have not been able to find a good explanation of these statements.
Is there a good reference that shows how to do conversions between these notions?


texts: Finding a minimum weight path with certain restrictions

texts:
I have a directed weighted multigraph whose vertices are sets of URLs.

We add to this multigraph all edges of the form $i\to j$ where $i\subset j$ (such edges are of zero weight), where $i$, $j$ are vertices of the graph.

Now having a set of source vertices and destination vertices, I need to find the minimum weight path (or several paths, if there are several such paths of the same weight) from a source to a destination of nonzero length and having at least one edge not of the form $i\to j$ where $i\subset j$.

Also it is desirable that the paths do not have adjanced edges of the form $i\to j$ where $i\subset j$.

I am currently working with Python and NetworkX.

I think (but not sure), that we can assume that the set of source vertices is disjoint with the set of destination vertices.


texts: Decidable non time constructible function

texts:
Can anyone help me find an example of a function $f:\mathbb{N}\rightarrow\mathbb{N}$ which satisfies $\forall n\in\mathbb{N}: f(n)\ge n$ and is decidable, i.e. there exists some Turing machine $M_f$ such that $M_f(x)=f(x)$, but is not time constructible, meaning that any machine $M_f$ deciding $f$ runs in time greater than $f$.

Thanks!


texts: Validate that a threaded binary tree works as intended

texts:
I am attempting to validate that my threaded binary tree’s insertion and deletion works as intended.

Would it be safe to assume that the following procedure would have tested all corner cases at least once?

I have an array of integer S = {1, 2, …, n-1, n} for n = 1’000’000.
I then randomize the order of S to obtain S’ and S*.
S’ is then used to insert its elements sequentially, into the tree.
After all elements are inserted, I create an in order list of the tree, say A, and confirm that A = S.
This concludes the insert test.

For deletion, I pass elements of S* sequentially as argument to be removed from the tree, testing that each call was successful. After all elements was removed I confirm that the tree is empty.


texts:
What is the goal of the SAT Problem?

Check if it is possible to have output '1'?
Above + find the right combination of inputs for that?

Witch one?

Cheers


texts: "not provable", what does this to do with unification?

texts:
I found one interesting point in nominal unification. Just after proposition 2.16 of Nominal Unification by Urban, Pitts, and Gabbay, it said the following, which I found confusing:

  For non-ground terms, the relation $=_{\alpha}$ and $\approx$ differ! For example, $a.\!X=_{\alpha} b.\!X$ always holds, whereas $\emptyset\vdash a.\!X \approx b.\!X$ is not provable unless $a = b$.

The $=_{\alpha}$ is the standard $\alpha$-equivalence and $\approx$ is defined in the paper.

It seems to me that $\vdash a.\!X \approx b.\!X$ has a unifier which is
${a \# x},[X:=(a \, b)X]$ no matter what $a$ and $b$ are according to the unification algorithm in the same paper.

So, I am trying to understand why the paper said the above lines? what is the relationship between something is "not provable " but has a unifier? or I am misunderstanding something?

Hoping someone could clarify this point for me, thanks in advance!


texts: Find the smallest element greater than current element

texts:
my question is that given a list of integers (lets say A), for each element A[i], find the smallest element A[j] which could satisfy A[i] < A[j] and i < j. Return -1 if there is no such element.

For example, given [4,2,1,9,3], return [9,3,3,-1,-1]

I have come up with a brute force solution which costs $O(n^2)$, but I'm wondering if there could be a more efficient solution.


texts: What is $Prop$ in the calculus of constructions?

texts:
I'm looking at the Calculus of Constructions and its place in the Lambda Cube.

If I understand correctly, each axis of the cube can be thought of as adding another operation involving types to the simply-typed calculus, $\lambda_\to$. The first axis adds type-to-term operators, the second type-to-type operators, and the third dependent typing, or term-to-type operators. The CoC has all three.

However, the CoC introduces a term $Prop$, and states that $Prop : Type$ by the inference rules,
but is otherwise not used.
I understand that it is for the eponymous propositions, but the logical propositions are not defined in terms of it.

Could you explain to me what $Prop$ is for, where/when it appears, and explain it in terms of the cube's axes (if indeed it is possible to do so)?


texts: Generate a random graph with geometrical degree distribution

texts:
I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper.

We are talking about generating an undirected graph in a slightly different way than what the Watts-Strogatz model does.

One of the very first steps of the algorithm is

  instead of selecting links to connect most immediate $\langle k \rangle / 2$ neighbors to form a regular lattice, our model selects a
  number $k$ of links at random from a local neighborhood $N_{d_0}$ with
  the distance threshold of $d_0$, where $k$ comes from a geometric
  distribution. The local neighborhood is defined as the group of
  close-by nodes with mutual node number difference less than the
  threshold $d_0$, that is $N^{(i)}_{d_0} = \{j; |j-i| < d_0\}$, for
  node $i$. It is worth noting that our model adopts a geometric
  distribution with the expectation $\langle k \rangle$ of for the
  initial node degree settings (i.e, for the link selection).

In other words, each node with index $i$ should have a (possibly different) random degree $k$, obtained by linking it with nodes with an index-distance $d_0$.

First of all, I need to choose the parameter $p$ to generate the geometric distribution. If the average is $\langle k \rangle$, I choose $p = 1/\langle k \rangle$.

However, picking $n$ node degrees from a geometric distribution may not result in a feasible graph of $n$ nodes.

Moreover, Since this is an undirected graph we are talking about, going through each node and creating a random number $k$ of links will most likely not produce the desire average degree. E.g. during the ith iteration, the node i may already have more than $k$ links, created by the previous iterations of nodes randomly linking to it.

I tried to implement my own algorithm to distribute the node degrees as close as possible to the distribution outcome. Pseudocode

k_values = n values from the geometric distribution with p = 1/<k>
for each node in [0, n)
    if degree(node) < k_values[node]
        for each neighbor closer than d_0
            if degree(neighbor) < k_values[neighbor]
                if not link_exist(node, neighbor)
                    create_link(node, neighbor)

The problem is, this approach tends to consistently result in nodes having lower degrees than the output of the geometric distribution.

I know there are ways to generate an undirected graph with a given degree distribution. The biggest problem here seems to be the additional constraint on the potential neighborhood of each node (i.e. nodes within index-distance $d_0$). Any ideas on how to solve that?

I would be happy getting a graph that is within a certain threshold from the outcome of the geometric distribution, and still quite close to the intended average degree $\langle k \rangle$.


texts:
let S and Q to be initialized to 1

process p0:          process p1:

wait(S);             wait(Q);
wait(Q);             wait(S);

..                    ..
..                    ..
Signal(S);           Signal(Q);
Signal(Q);           Signal(S);

I know there is a deadlock , where both the process will be going into the sleep , so what about starvation and bounded waiting?

My approach:

as only p0 can be executed any number of times i think there will be starvation and no bounded waiting.But answer is given that there is No Starvation.


texts: Does Edmonds Karp take back-edges into account?

texts:
I amb doubting with the implementation of the Edmonds-Karp implementation of the Ford-Fulkerson algorithm.

This is a problem with flow networks.

As I understand the algorithm, it consists on taking a path from s to t (randomly in Ford-Fulkerson, and a shortest path in Edmonds-Karp) and saturate the bottleneck for that path. That adds back-edges that allow to "reconduct" the flow. The bottleneck for that path is added to the maximum flow and the algorithm runs until there is no such "augmenting" path.

I'm doubtful, though, with the back-edges role in all this.

Should I take back edges into consideration when finding such shortest path? Most implementations I've found don't take that into account.

If so, how would I treat them, because as I understand it, taking a back edge means reconducting the flow, and thus I should subtract some quantity from the maximum flow shouldn't I?


texts: Meaning of "uniformly computably enumerable in m"

texts:
Nies, in Computability and Randomness, p. 6, defines "uniformly computably enumerable":

  A sequence of sets $(S_e)_{e\in\mathbb{N}}$ such that $\{\langle e,x \rangle : x \in S_e \}$ is c.e. is called uniformly computably
  enumerable.

I think this means that both the sequence of sets and the members of the sets are jointly c.e., i.e. that even if the sequence of sets is infinite, and/or the sets are infinite in size, one can, step by step, construct the sets in a c.e. manner.

Is that correct?

If that is correct, my further question is what Nies means by his repeated use of "uniformly in" some variable.  For example, on page 108 (the one that's puzzling me at the moment), Nies writes:

  By the representation of c.e. open sets in 1.8.26 we may uniformly in
  $m$ obtain an effective antichain $(x^m_i)_{i<N_m}, N_m \in
\mathbb{N}\cup\{\infty\}$, ....

If my previous understanding is correct, "uniformly" here means that we construct the antichain (prefix-free set of strings) in a computably enumerable way with respect to both indexes $i$ and $m$ simultaneously.

What does "in $m$" indicate, though?


texts: Prove correctess of recurrence result by mathematical induction

texts:
I have the following recurrence relation which I already solved using repeated substitution.

$T(n) = \begin{Bmatrix}
1 & if & n = 1\\
4T(\frac{n}2) + n & if & n >= 2
\end{Bmatrix} where$ $n=2^k$

The result I get is $T(n) = 2n^2 - n$
Let´s suppose my result is correct. Now, I am asked to prove the correctness of the result using mathematical induction.

Base case is easy:
For $n = 1$ we have $T(1) = 2(1^2) - 1 = 2 - 1 = 1$
This result agrees with initial formulation of the problem above.

Now, comes the $Inductive$ $Hypothesis$ which I guess is as follows:
Assume this holds for $2 <= k <= n$
$4T(\frac{k+1}2) + (k+1) = 2(k+1)^2 - (k+1)$

Am I doing things correctly?
How would the $Induction$ $Step$ would be?
I will very much appreciate your feedback.


texts: Clustering a set of images using keypoint descriptors

texts: I'm trying to cluster around 16000 images into ~200 clusters, using kmeans with metric as euclidean distance or cosine distance. I understand that i need to extract keypoint descriptors to compute features for each image. I'm looking at SIFT as an option but, SIFT outputs different number of keypoints for each image that i have. How can i use these keypoint descriptors generated by SIFT to make a uniform sized feature vector for every image, so that i can feed these vectors to kmeans. Or should i use any other feature descriptor apart from SIFT?


texts: How to apply path compression to Multi-Bit Trie

texts:
Reading a bit about the subject of Multi-Bit tries and IP matching in:

  High Performance Switches and Routers H. Jonathan Chao, Bin Liu. Page 33

  Network Routing: Algorithms, Protocols, and Architectures (The Morgan Kaufmann Series in Networking) April 12, 2007
  by Deepankar Medhi. Page 507.

And they both mention path compression but they do not explain how to apply path compression to Multi-Bit tries (they only mention that this could be done).

I would like to understand how one would path compress (not level compress) a $k$-Bit trie? What would be the the asymptotic number of nodes given $N$ entries and $w$ width addresses?


texts: Why is CNOT the only non-trivial reversible gate for two input bits?

texts:
The Wikipedia page on the Toffoli gate mentions that CNOT is the only non-trivial reversible gate on two input bits. The CNOT gate computes the following function:
$$
00 \to 00 \\ 01 \to 01 \\ 10 \to 11 \\ 11 \to 10
$$
I think I found a different non-trivial gate on two input bits:
$$
00 \to 01 \\
01 \to 00 \\
10 \to 10 \\
11 \to 11
$$
I think the matrix corresponding to this gate is
$$
\begin{bmatrix}
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
\end{bmatrix}
$$
which is different from
$$
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0\\
\end{bmatrix}
$$
and is also unitary.


texts:
S-> AAB|ABA|BAA|epsilon

A->aS

B->bS

this is a grammar of the language L4 = {w ∈ Σ*: #a(w) = 2#b(w)} over Σ = {a, b}

Does the following examples shows that the L4 is ambiguous?

S->AAB->aSAB->aAB->aaSbS->aab

S->AAB->aSaSbS->aab

I'm not sure if these derivations are the same,
if they are not, what are the derivations that shows the ambiguity of L4?


texts: Initial temperature in simulated annealing algorithm

texts:
I've done some testing of different initial temperatures in my simulating annealing algorithm and noticed the starting temperature has an affect on the performance of the algorithm.

Is there any way of calculating a good initial temperature?


texts: How do algebraic datatypes relate to free structures?

texts:
I know that:

Binary leaf trees are free magmas.
Non-empty lists are free semigroups.
Lists are free monoids.
The generalized algebraic datatype data FM a where {Return::a->FM a; Bind::FM b -> (b->FM a) -> FM a} is a free monad.

I know also that various abstract datatypes also correspond to free structures—bags are free commutative monoids and finite sets are free commutative idempotent monoids.

Do other algebraic datatypes (e.g., Maybe, or 2-3 trees, or binomial trees) also correspond to free algebraic structures? If so, how might those be characterized?


texts:
I'm currently working on a problem that I came across:

  You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have to Suggest an $O(n^{3})$ time algorithm for determining if there is a perfect matching between them, with the constraint that each point in $R$ is matched to a point in $B$ point whose distance is at most 1 unit away.

I have tried solving using the minimum distance using bipartite algorithm but could not arrive at a solution. Can anyone provide me with any ideas?


texts: Can a solvable problem be encoded in a recursively enumerable language?

texts:
Imagine I have a turing machine that can decide on a specific problem using a language. My question is that that problem (that can be decided by a TM M, with language L) can be encoded in a new language that is recursive enumerable.

If yes, this would mean that every solvable problem can encoded in recursive language; if not, a problem can be encoded in a recursive and/or recursive enumerable L and the problem could become semi-decidable for a different language.

Any clarification on this?


texts: Tool for generating all the consequences of the logical theory (general logic programming framework)?

texts:
I am reading article https://arxiv.org/pdf/cs/0511055v1.pdf (about defeasible deontic logic) and it mentions on page 10 the operator T that constructs extension (set of immediate consequences) from the theory D (set of statements). Such extensions form s.c. Kleene sequence and the fixed point exists for the operator T - this fixed point is the complete set of consequences of the set D of statements.

Such construction is known for many logics and I guess that it is the basis of the logic programming using forward chaining approach. This approach is known in business software as well and is called business rules (e.g. JBoss Rules Drolls of IBM ILOG). Such construction has very wide practical applications, e.g. if norms are encoded as logical statements then the set of consequences consist of all the obligations and permissions. More practical applications can be found as well - e.g. application of complex discounting rules in retail trade.

My theory question is:

Do I understand correctly that generation of set of consequences is the essence of logic programming and such logic programming can be devised for almost any logic?

My systems questions are:

Are there general framework (system) which receives 1) syntax of logic; 2) operator T and which generates program that can find set of consequences for any set D? I.e. should I construct logical programming tool for my logic from scratch (only parser can be generated automatically) of can I use some framework?
How such logic programming framework is connected with proof assistant and theorem prover frameworks (like Isabells of Coq)? As far as I understand then there is no connection - theorem provers use backward reasoning approach and logic programming uses forward reasoning approach? However - maybe any connections exists and maybe proof assistant/theorem prover frameworks can still be used for logic programming?


texts: Whether there exists a probabilistic automaton satisfying $\Pr \{ x \in L\}=\frac{\Pr \{ x \in L_1\}}{\Pr \{ x \in L_1\}+\Pr \{ x \in L_2\}}$

texts:
Suppose that there are two probabilistic automata $A_1$ and $A_2$ with a same finite alphabet $\Sigma$. The languages of them are $\mathcal{L}_{1} \subseteq \Sigma^*$ and $\mathcal{L}_{2} \subseteq \Sigma^*$ respectively.
For every input $x \in \Sigma^*$, $\Pr \{ x \in \mathcal{L}_{1}\}=p_1(x)$ and $\Pr \{ x \in \mathcal{L}_{2}\}=p_2(x)$. Whether there exists a probabilistic automaton $A$ satisfying $$\Pr \{ x \in \mathcal{L}\}=\frac{p_1(x)}{p_1(x)+p_2(x)}$$ where $\mathcal{L} \subseteq \Sigma^*$ is the language of $A$?


texts: In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular

texts:
In what cases is solving Binary Linear Program easy (i.e. P complexity)?
The reason I'm asking is to understand if I can reformulate a scheduling problem I'm currently working on in such a way to guarantee finding the global optimum within reasonable time, so any advice in that direction is most welcome.
I was under the impression that when solving a scheduling problem, where a variable value of 1 represents that a particular (timeslot x person) pair is part of the schedule, if the result contains non-integers, that means that there exist multiple valid schedules, and the result is a linear combination of such schedules; to obtain a valid integer solution, one simply needs to re-run the algorithm from the current solution, with an additional constraint for one of the real-valued variables equal to either 0 or 1.
Am I mistaken in this understanding? Is there a particular subset of (scheduling) problems where this would be a valid strategy? Any papers / textbook chapter suggestions are most welcome also.


texts: Finding infinitely many Myhill–Nerode equivalence classes

texts:
I need to prove the following languages are not regular and I'm having a
tough time identifying the equivalence class that can have an infinite
index.
How would I go about doing these? I know how to prove it after finding
the equivalence class but any tips on how to identify the one that has
the infinite index?
I know I should find the equivalence class where there are distinct
extensions for each string belonging to $L$, but could anyone help me
out on these 2:

$0^m  1^n$ where $m$ is even or $m$ is greater than $n$

$0^m  1^n$ where $\text{gcd}(m,n)=1$.


texts: Please explain "decidability" and "verifiability"

texts:
I am trying to (intuitively) understand the two terms "decidability" and "verifiability".

I have done a reasonable amount of searching and going through the various texts I can put my hands on. However, their intuitive understanding seems to escape me, specially for the second one.

Out of the many definitions found, the following one found in this page, clearly explained decidability to me.

  A language is called decidable if there exists a method - any method
  at all - to determine whether a given word belongs to that language or
  not.

However, I fail to find a parallel definition for verifiability.

In the Theory of Computation book by Sipser, we find,

  P = the class of languages for which membership can be decided
  quickly.

  NP = the class of languages for which membership can be
  verified quickly.

In light of the above, I want to understand verifiability.

Please provide as many examples as you can, at one moment, I try catch the meaning, in the next one, I get confused again.


texts:
Suppose you receive a list of $n$ instructions on $k$ boolean variables where each instruction has the form
$$x_i \leftarrow x_i \oplus x_j,$$
(where $\oplus$ is the binary XOR) can we efficiently find a minimal series of instructions (of the same form) that computes the same result, using up to $m$ initially zero extra temporaries?


texts: Is converting an ambiguous grammar to an unambiguous grammar computable?

texts: Is the problem of converting ambiguous grammar into unambiguous grammar computable? (Consider Domain as all context free languages).


texts: Meaning of Steve Wozniak's epiphany on register addition/subtraction in 1975?

texts:
I just finished reading Walter Isaacson's Innovators and on page 350 there is a quote from Steve Wozniak recalling things he learned from the March 1975 Homebrew Computer Club meeting:

  A person at the meeting passed around the specification sheet for the new Intel microprocessor. "That night, I checked out the microprocessor data sheet and I saw it had an instruction for adding a location in memory to the A register," he recalled. "I thought, Wait a minute. Then it had another instruction you could use for subtracting memory from the A register. Whoa. Well, maybe this doesn't mean anything to you, but I knew exactly what these instructions meant, and it was the most exciting thing to discover ever."

Referencing the book, Intel started selling the 4004 microprocessor in 1971. By definition, I thought a microprocessor has to have registers, so did they just add functionality to the new 1975 microprocessor? Do you believe he was referencing the Intel 4040 microprocessor that came out in 1974? Also, does adding and subtracting memory allow arrays in RAM to be indexed in O(c) / constant time? Is that the significance or are there even more layers to this tale?

Thanks!