# All Questions

33,166 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
8 views

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