All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
6 views

Is there a corpus of “general” C programs?

I am studying the properties of control flow graphs (CFGs) in general. The tool that I use to statically extract CFGs and label them is based on LLVM. Now, I am looking for a large corpus of C/C++ ...
1
vote
1answer
11 views

Time complexity of rotation array m times using temporary array

I am new to asymptotic analysis, on solving the array rotation problem on geeksforgeeks the first solution provided was using a temporary array, I tried implementing this logic and found that the ...
0
votes
0answers
11 views

Algorithm for detecting overlaps

This is a real-world application, not a student assignment. Suppose a list of events of that have startTime and endTime, and ...
0
votes
0answers
7 views

Genetic algorithm pool selection with fitness multiples

Say I have an array of fitnesses like so: let array = [3,2,2,2]; Although the players with a fitness of 2 had a worse score, they are more likely to pass their ...
0
votes
0answers
10 views

map 64-bit values into 32-bit range

I am working on a graph partitioning algorithm and i have the following problem i am trying to solve. There is a 32-bit value c computed for each state of the ...
0
votes
0answers
19 views

Converting DFA to RE [duplicate]

I have been trying to solve this problem. Convert the DFA to a regular expression. I extracted these following equation. $q_1 = q_2a$ $q_2 = q_1a + (a+b)q_3$ $q_3 = q_1b + q_2a $ Also,the ...
0
votes
2answers
19 views

Karatsuba Multiplication Rule in dividing a Number in two parts

In Karatsuba algorithm for multiplying two numbers, we divide each number into two. For example: x= 1234 y= 2456 Then a = 12, b = 34, c = 24 , d = 56 What if ...
1
vote
1answer
17 views

Algorithm Analysis of Insertion Sort

Why is the recurrence formula for insertion sort is T(n-1) + n? I understand the T(n-1) part but the why does the cost for ...
3
votes
1answer
27 views

Basic complexity theory (in Oracle Separation of BQP and PH)

I have some basic questions about complexity theory that came up when I tried to understand the result by Raz and Tal that BQP$^O\nsubseteq$ PH$^O$. Aaronsons paper was helpful, but I still have some ...
-2
votes
0answers
13 views

Updating to macOS Mojave [on hold]

Will updating to a new OS replace and system files that I may have accidental tampered with that has since cause the system to run unstable. For example,I’m currently running OS X Sierra I’m now ...
-3
votes
0answers
32 views

Is it Turing recognizable/decidable?

Imagine we have a program which does an infinite loop: while(true){loop} We run the program on a linux machine(assume the compilation is ok), then this linux ...
2
votes
1answer
31 views

Probabilistic halting problem

I'm a physics and math student working through Nielsen & Chuang's text on quantum computation and information. I don't have much experience in CS theory, so some of these exercises are confusing ...
0
votes
0answers
15 views

Where can I download a dictionary of computer technology terms for natural language processing? [on hold]

I am doing some natural language processing in R of a moderately sized corpus. I am cleaning up the corpus to remove nonsensical terms (e.g. escape/typesetting characters, URLs, HTML code). Part of ...
0
votes
0answers
23 views

When should I refine my code? [on hold]

I'm fairly new to coding. I have done some for loops, conditionals, and def or functions. I have a project to construct some sort of algorithm let's call it A. Now within A, there are some primary ...
1
vote
0answers
23 views

How can we find number of triangles in a given undirected graph? [on hold]

If we assume we have n triangles in a given graph. How can we find the n triangles in O(n) time? And we also have to add and remove edges in O(log k) when k=|v|
0
votes
0answers
24 views

Graph with weighted edges question [on hold]

Is my solution considered right? It was in my test.
1
vote
0answers
11 views

Are Linux kernel modules a sort of Linux system paged pool? [migrated]

I always read that Linux kernel isn't pageable. If I'm not mistaken Windows, instead, divedes system virtual memory in a paged part (paged pool) and non-paged part (non-paged pool). The non-paged part ...
1
vote
1answer
44 views

How to find an algorithm's complexity from actual running times

I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of ...
0
votes
0answers
22 views

Contradict or Proof the following statement

My following proof is correct about the big theta statement?
1
vote
1answer
24 views

Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal

Given a positive n-digit integer, such as 1214532 (n=7), remove k digits (for example k=4) such that the resulting integer is the smallest one. A greedy algorithm for this would keep removing digits ...
0
votes
0answers
33 views

Gosper's Glider Gun

I was going through some text on Conway's Game of Life and it had a question that kinda got me confused. For a 5-cell configuration for Conway’s Game of Life that has been produced by Gosper’s ...
3
votes
1answer
143 views

Langton's Ant Periodic Behavior

I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?
0
votes
0answers
28 views

Testing if a state is in final state

Please excuse my language, I am new to the topic. I am trying to classify/find a class of game that describes games such as chess, tic-tac-toe as a finite state machine. For those games, final ...
0
votes
0answers
14 views

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

Let say I have time series of disk usage of last 30 days.. Given this information and with the assumption that the disk usage 'pattern' isn't changing dramatically over time, what would be a naive/...
1
vote
0answers
17 views

Problem of making entities agree on some wavelength

I remember seeing this problem somewhere before, but don't remember what it's called and can't find it again. It was presented as two guys having $n$ phones each that don't ring when called. Each ...
5
votes
2answers
1k views

is FIND WORDS in P?

FIND WORDS is the following decision problem: Given a list of words L and a Matrix M, are all words in L also in M? The words in M can be written up to down, down to up, left to right, right to left,...
2
votes
1answer
33 views

If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case?

According to this source, If A is reduced to B and A ∈ class X, then B cannot be easier than X. This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to ...
6
votes
1answer
739 views

Computational complexity of calculating mean vs median?

Suppose we have a list $L$ consisting of $N$ numbers (may include repetitions). I am curious which is more computationally intensive to calculate, the mean or the median? Naively, I would suppose ...
0
votes
0answers
5 views

Oracle separation between AWPP and QMA

Are there any known oracle separations between AWPP (defined in http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf) and QMA (the quantum analogue of MA)?
0
votes
0answers
41 views

Traversing a Graph polynomial time

Given a directed graph $G = (V, E)$ and a starting vertex $v_1$. The graphs edges is this $\{(v_1, v_2), (v_2, v_3), (v_3, v_4)\}$ basically below $(v_1) \to (v_2) \to (v_3) \to (v_4)$ Can we ...
1
vote
1answer
26 views

graph theory conventions, difference between a PATH and a GRAPH?

Consider this example, I did my pseudocode in python findCycle(G): for each edge e in E(G): if isThereCycle(G-e): G = G - e return G ...
0
votes
0answers
17 views

What does W1 and W2-hardness imply?

Is there any simple definition to understand W1-hardness $\&$ W2- hardness in complexity theory? What I understood, that is the following: Let $\Pi$ be a decision problem with parameter $k$, then $...
0
votes
2answers
54 views

Assuming an infinite amount of computing resources, would the minmax algorithm always win in chess?

The minmax algorithm is a popular strategy used to design chess engines. Usually, since the state-space of chess is huge, we choose a fixed depth and evaluate the game tree down to that level, and ...
0
votes
0answers
8 views

Channel Capacity to transmit data

If the size of transmitted data is 24kbit, what it is the optimum channel rate to deliver this data?
1
vote
1answer
15 views

Polysize bounded depth circuit for modified MAJORITY problem

I am trying to show the existence of a polynomial size, bounded depth monotone circuit on the inputs $(x_1,\ldots, x_n)$ that gives $1$ if $\sum x_i \geq n/2 + n/\log n$ and $0$ if $\sum x_i \leq n/2 -...
2
votes
0answers
34 views

A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

It is known that a PDA with two stacks is equivalent to a TM. On the other hand a PDA with one stack is capable to recognise only context-free languages. Hence there is a kind of a gap between the ...
-1
votes
1answer
44 views

Is the following a AVL tree?

I have a tree as Is it an AVL tree? it seems to balanced for me.
0
votes
0answers
28 views

How can I solve this deadlock related problem mathematically?

I came across following problem: A system has n resources R0,…,Rn-1,and k processes P0,….Pk-1.The implementation of the resource request logic of each process Pi is as follows: ...
3
votes
0answers
20 views

For proof automation in Coq, when is it appropriate to use canonical structures or Equations instead of Ltac?

There are a few possible approaches to proof automation in modern Coq. Writing proof scripts with Ltac. This is the approach described in http://adam.chlipala.net/cpdt/, which the author uses to ...
0
votes
0answers
12 views

Relationship between IP, IPS, IPP and NP

I read these notes which mention IPS (Interactive proof system) https://people.csail.mit.edu/ronitt/COURSE/S12/handouts/lec6.pdf I then saw IPP being mentioned in complexity zoo: https://...
0
votes
0answers
15 views

What is the meaning of realistic SNR? [on hold]

I know the meaning of SNR(signal noise ratio), but in an article, I saw a realistic SNR and I want to know its meaning.
3
votes
1answer
69 views

What types are propositions?

In the propositions-as-types paradigm, we are still faced with the question : what types are propositions ? I currently know 3 different answers : Coq's sort Prop ...
3
votes
1answer
30 views

Algorithm for decomposing a complex (self-intersecting) polygon into simple polygons

I've been attempting to write a Bentley-Ottmann sweepline algorithm to transform a self-intersecting (complex) into a set of simple polygons. There are some instructions on this page (see the heading ...
0
votes
1answer
26 views

Minimum Bounding Quadrilateral

In an image processing project (using opencv with python), I am trying to detect as precisely as possible the location of a rectangular object in a photograph. My final goal is to output the 4 corners ...
0
votes
0answers
16 views

Maximising Success of candy distribution: Maximising the absolute difference

N people attend a gathering and will be given candies at the end. Each person gets at least one candy Maximum number of candies any ith person can be given, is given in an array A[ ] of length N ...
0
votes
1answer
14 views

Calculate minimum and maximum Ethernet (IEEE 802.3) frame size from frame format

According the frame format of Ethernet Minimum Frame Size should be : 7Bytes + 1Bytes + 6Bytes + 6Bytes + 2Bytes + 46Bytes +4Bytes = 72Bytes Maximum Frame Size ...
1
vote
2answers
22 views

Run time for a specific loop confusion

I have a loop: for(int i = 1; i < N; i*=5) {...} where {...} is some statement. I'm trying to understand its run time. So, ...
-1
votes
2answers
256 views

One-way Trapdoor Function

Do the functions of the collatz conjecture and their inverses model a Trapdoor Function? That is, given f(n) = n/2 or 3n+1 and the inverse g(n)=2n and (n-1)/3 it is easy to go from n to 1 by ...

15 30 50 per page