All Questions

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

Formal semantics of this “paradox” subroutine?

In Section "Routines as Parameters: An Example" of the book "Algorithmics: The Spirit of Computing (3rd Edition; Page 53-54)" by David Harel and Yishai Feldman, the authors describe the routines which ...
0
votes
1answer
5 views

HashTable open-addressing is used for main array or buckets

I am trying to understand the HashTable open-addressing technique. I see there are three approaches: linear, quadratic and double hashing. I'm wondering are these techniques used: to find an index of ...
0
votes
0answers
8 views

How are Complex Numbers and Complex Analysis used in CS?

The world is 3D and data of it is usually (as far as I know) represented and processed with real numbers. I've seen very few cases where complex numbers are used in programming and none when it comes ...
0
votes
1answer
8 views

The minimum depth of the boolean circuits for addition and multiplication by using binary gates

Let $\mathrm{\mathbf{a}},\mathrm{\mathbf{b}} \in \{\,0,1\,\}^{n}$ and $\mathrm{\mathbf{v}} = (2^{n-1}, 2^{n-2}, \ldots, 2^1, 1)$. $a,b$ can be used to represent then elemments $\mathrm{\mathbf{a}} \...
0
votes
0answers
5 views

How are vector spaces and subsets used in CS?

I'm CS and still can't grasp these concepts after reading many posts in math.SE and other pages written by maths people so I'd like to hear this from CS people. I'm learning Linear Algebra and ...
0
votes
0answers
7 views

Pandemic board game - find all possible next 4 actions

I hope I am asking this on the right community. I am building an Artificial Intelligence to play the board game Pandemic. The AI uses a Monte Carlo algorithm. After implementing the game rules and ...
0
votes
1answer
13 views

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

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 ...
1
vote
0answers
7 views

Simulating extensible sums with dependent types?

ML-style languages have a concept of "extensible" or "open" sum types, where variants can be declared at any point, and there's not a fixed number of constructors for the type. They're usually used to ...
1
vote
1answer
24 views

Prove that $\texttt{prefix}(L)$ is regular

Given that $L = \lbrace 0^n1^n : n \geq 0\rbrace$ is a non-regular context-free language, prove that $\texttt{prefix}(L)$ is regular. So far I have provided that the grammar to produce this language ...
0
votes
0answers
10 views

Why does such reductions work

In class we saw examples of reductions like from Independent Set(IS) to Longest common subsequence( arbitraary number of sequences) (LCS) $V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$ The ...
0
votes
0answers
10 views

Searching for points near given point in a multidimensional space

I want to search many times, not identical elements but similar, for something a similar image or fingerprint without having to search the whole space. When I have a 1D case I sort it first. For 2D I ...
0
votes
1answer
17 views

Trading Auction - Need help with calculating price / quantity of restricted underlying securities for matching

I'm having some difficulty with implementing a non-brute force algorithm for solving the following Problem. If I can get something even close to O(N^3) i'd be happy at this point. Auction: https://...
0
votes
1answer
15 views

O(n) external intersection points?

I have a doubt. For a given n (axis-parallel) squares in a plane, where there are Ω(n²) intersection points between the edges of the square, is it possible to have O(n) external intersection points? (...
0
votes
0answers
5 views

Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?

I was trying to do the following: Consider the set of all strings over the alphabet { 0,1,2,9,.}{ 0,1,2,9,.} that are decimal numbers beginning with 1 and ending with 9 and having exactly one ...
0
votes
0answers
17 views

You're walking in a maze,you must visit all reachable squares of distance k. The performance of the algorithm is measured by the total distance walked

The maze is a 2D Grid of known width and height. it's composed of squares: a Wall or a room. You cannot walk into walls. from each room you can only get to adjacent rooms. ( you can't teleport) You ...
2
votes
1answer
23 views

Data structure to report all axis aligned bounding boxes intersecting an axis aligned query line

I would like to build a Data structure that uses subquadratic space to quickly report a set of AABBs (axis aligned bounding boxes) in 3 dimensional space when it intersects a query line? I am only ...
0
votes
1answer
24 views

How to prove NP-completeness of this variant of the set cover problem?

The problem exactly: Suppose you're helping to organize a summer sports camp, and the following problem comes up. For each of the n sports offered at this camp, the camp is supposed to have at least ...
0
votes
0answers
11 views

Expression to right to left associativity

I have an expression: a*b+c/d I have to convert this expression where there are no precedence rules and the statement is given right to left associativity. I have two options as an answer: (((d/c)+...
1
vote
1answer
8 views

Summation of asymptotic notation

How can we solve summation of asymptotic notations like given below: Summation (BigO(n)) over k for 0 < k < n.
0
votes
0answers
5 views

time complexity turing machine equal to “n + 1”

I have not clear why the time complexity is n+1 and not n+2. Consider a TM with a single tape and alphabet {0,1} and the string | * | 0 | 1 | 1 | 0 | 1 | 0 | * | ...
1
vote
0answers
10 views

What does it mean this relation: $BQP^{BQP} = BQP$

I am reading this paper by Fortnow, titled: One Complexity Theorist's View of Quantum Computing. In section 4, he states the following: Bernstein and Vazirani [BV97] show that BQP can simulate any ...
0
votes
1answer
19 views

Given an array arr[] of N integers. Do the following operation n-1 times

For every Kth operation: Right rotate the array clockwise by 1. Delete the (n-k+1)th last element. eg: A = {1, 2, 3, 4, 5, 6}. Rotate the array clockwise i.e. after rotation the array A = {6, 1, 2, ...
-1
votes
0answers
20 views

What is a Regular BNF Grammar and a Regular Expression for (simple) Resource Identifiers?

I was trying to make a regular grammar for resource identifier described as follows: Consider the set of all strings over the alphabet $\{ a, b, / , . \}$ that represent an RI (resource ...
1
vote
1answer
10 views

How to find maximum matching edges in undirected tree

Let $B$ be an undirected tree with $|V|$ nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime $\mathcal{O}(|V|)$. My approach: ...
0
votes
1answer
11 views

Injective burrows wheeler

We know that the Burrows-Wheeler Transform is reversible, in the sense that, given s=BWT(w) and an index I, it is possible to recover w by an algorithm. But how to prove that w is unique? In other way ...
0
votes
0answers
12 views

Does exec cause a context switch?

If we start a new process with exec('process-2') Does this cause an immediate context switch in order to halt the current process and then start the new '...
0
votes
0answers
10 views

Efficient Way to Apply Business Logic Rules Back To Dataset

Hi I'm new to computer science and programming I want to match rules that contain business logic to a data set e.g Example Table IF(Column 1 Contains Cat AND DOG) Update count for rows where ...
0
votes
0answers
10 views

Why are there two World Congresses on Services?

Since 2018 the World Congress on Services seems to have forked. Most of the associated conferences (ICWS, CLOUD, SCC, ...) now exist twice, e.g. the International Conference on Web Services (ICWS): ...
2
votes
1answer
28 views

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

So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
-1
votes
1answer
14 views

A good book on “Parallel Computing” for beginners?

I hope here is related site to bring up this question. If not, please propose suitable stack exchange site. I found several books about "Parallel Computing" in Amazon; however, I am looking for a ...
4
votes
2answers
492 views

Are there any proofs of exponential lower bound time complexity

I'm trying to understand what are the techniques to prove an exponential time lower bound. For some problems, we can prove that the size of the output is exponential is the size of the input, thus it ...
0
votes
0answers
14 views

Syntax Directed Translation Scheme for Postfix to Infix Notation

I'm reading Compilers Principles, Techniques and Tools textbook and I encountered a problem from exercise 2.3 We have to construct a syntax-directed translation scheme that translates arithmetic ...
1
vote
1answer
24 views

Shortest paths from a source in weighted graph with only one negative weighted edge

Of course assuming there aren't any negative cycles. I saw this question somewhere. And i saw a complicated solution which says to build three such graphs and connect between them in a very ...
1
vote
5answers
41 views

Why is finding the closest pair of points by brute force search O(n^2)?

If I have n points A, B, C, D it seems like finding the closest pair via brute force search would go like: Compare A to every item (n-1) Compare B to every item (...
1
vote
0answers
27 views

How to build a set of closed chains with a sequence of different vertices?

I have a set of many bi-directional links like A-B, A-C, B-C, A-D, C-D, D-E, etc. I need to find a set of many closed chains with a sequence of different vertices (...
3
votes
1answer
40 views

Evaluating predicate on binary strings

Consider two unknown binary strings $$X = x_{1} x_{2} \dots x_{n^{2}}, \quad Y = y_{1} y_{2} \dots y_{n^{2}}, \quad x_{i}, y_{i} \in \{0, 1\} .$$ We may request a string $Z = z_{1} z_{2} \dots z_{n^{2}...
4
votes
0answers
40 views

Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to ...
3
votes
1answer
34 views

How many “compressible” strings are there?

Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this. It is easy to see that almost all ...
-1
votes
0answers
16 views

Array manipulation and number theory

How do I rearrange a given array such that the GCD of all the adjacent elements is always 1?
3
votes
0answers
28 views

Rules for consistency with mutual inductive families?

I'm trying to use a proof assistant to define a type and a relation that are mutually dependent on each other: ...
0
votes
0answers
33 views

General types of output of a computer

I am trying to understand what are the general types of output of a computer. I assume the following described general types of output are the only ones in the cosmos, but I might be wrong: Screened ...
0
votes
0answers
10 views

TCP Networking Protocol: Why no SYN_ACK packet received in “netstat -an”? What is connected? [on hold]

I used: sudo sysctl -w net.ipv4.tcp_syncookies=0 The above should disable SYN Cookies mechanism. This would enable complete 3-way handshake. But the following ...
1
vote
1answer
34 views

Meaning of $a\lor b \to b' \lor c'$

So I have done part a) but I have no clue what I am supposed to do for part b), I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know ...
1
vote
1answer
21 views

Simplification of a multi-index Boolean expression towards computation in fewer steps

Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following ...
1
vote
0answers
24 views

Relation between CPU cycle and Addressing modes

Professor has given this question in exam. I am not able to find relevant reference for this question Which Addressing Modes (for x86 architecture) consumes more CPU cycle?(Consider all are special ...
0
votes
0answers
19 views

Use ML to create a graph

I'm currently looking for literature/papers on machine learning techniques to create structures. In detail, I want to generate finite automata (NFA, DFA), which are useful for student-exercises. So I ...
2
votes
1answer
53 views

Oracle separation P and BPP

I'm reading (with much pleasure) the book Quantum Computing Since Democritus by Scott Aaronson. At some point the author claims that, while most most people believe that $\mathbf{P} = \mathbf{BPP}$ in ...
0
votes
0answers
10 views

What happen if the L1 cache has the address entry with write_back attribute. Will that address be available in L2 cache?

I have the TLB entry for a particular address. This address has write-back attributes in both L1 cache and L2 cache. My queries are: 1> if L1 cache entry has write-back, can it be write-back in L2? 2> ...
2
votes
1answer
28 views

Interactive proof system for graph nonisomorphism

$\mathit{GNI} \in \mathrm{PCP}(\mathit{poly}(n),1)$ GNI is the language of nonisomorphic graphs. Given two grapsh $G_0$ and $G_1$ with $n$ vertices, a verifier expects $\pi$ to contain, for each ...
0
votes
0answers
32 views

Did anyone successfully implemented Gödel machine? Is it practically possible to implement?

For reference - Gödel machine is a hypothetical self-improving computer program that solves problems. It uses a recursive self-improvement protocol in which it rewrites its own code when it can prove ...

15 30 50 per page