All Questions

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 ...

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 ...

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 ...

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}} \...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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://...

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? (...

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 ...

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 ...

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 ...

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 ...

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)+...

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

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 | * | ...

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 ...

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, ...

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 ...

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: ...

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 ...

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 '...

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 ...

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): ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 (...

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 (...

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}...

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 ...

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 ...

How do I rearrange a given array such that the GCD of all the adjacent elements is always 1?

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

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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> ...

$\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 ...

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 ...