# All Questions

5 views

26 views

### Lamport's Byzantine Generals Algorithm

I've stumbled at the first OralMessage algorithm in Lamport, et al's paper. I've searched the web and there are dozens of sites, restating in exactly the same terms and examples, which isn't helping ...
50 views

### Every language that is reducible to a language in $\Sigma_i^p$ is also in $\Sigma_i^p$ . How?

The complexity class $\Sigma_{k}^{p}$ is recursively defined as follows: \begin{align} \Sigma_{0}^{p} & := P, \\ \Sigma_{k+1}^{p} & := P^{\Sigma_{k}^{p}}. \end{align} Why is every language ...
34 views

### How to reformulate my problem as a mixed-integer quadratic problem

I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the ...
41 views

### Binary Palindrome

Let an integer n be given. Write the integers from 1 to n in binary notation successively from left to right. In the resulting string consisting of zeros and ones, choose a palindrome substring of ...
30 views

### Power method to calculate eigenvectors

I've implemented a program for computing eigenvectors of some random, symmetric, $N$x$N$ matrix using the power method. I have found difficulty in calculating all $N$ eigenvectors consistently, ...
27 views

include include using namespace std; int main() { ...
19 views

### How to Convert Row Major Order to Column Major Order? [on hold]

If M is an n×n array stored in contiguous memory in row major order, how would one write pseudocode converting M to be stored in column major order taking constant space?
130 views

### Does there exist a data compression algorithm that uses a large dataset distributed with the encoder/decoder?

If my goal were to compress say 10,000 images and I could include a dictionary or some sort of common database that the compressed data for each image would reference, could I use a large dictionary ...
136 views

### Suboptimal Solution for a combinatorial problem

I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2}$. This matrix $X$ is ...
46 views

### Good beginner source to learn about how computers work [duplicate]

I am a senior year high school student. I love programming and my chosen language is Java. I'm very much into high-level programming and Object Oriented design. Recently, I started to show first ...
42 views

### Regarding the Turing Machine

I am a high school student in the twelfth grade. I study high-level programming, and a little bit of basic computer science. I have recently started to understand what a Turing Machine is. I wanted ...
34 views

### The membership problem for Type 0 grammars

I have trouble solving the following problem: (i) Prove that for all finite sets $S$ of context free grammars, there exists a Turing machine $M$ such that for all grammars $G_1,G_2\in S$, we have ...
29 views

### Understanding decidability

Sorry this is a basic question to understand decidability. It is the first time I see it in my undergrad course. 1) I am reading why the language AFDA is decidable ...
38 views

### How to represent a 0-valid boolean formula?

I read in these two papers http://www.ccs.neu.edu/home/lieber/courses/csg260/f06/materials/papers/max-sat/p216-schaefer.pdf and http://people.csail.mit.edu/madhu/papers/noneed/fullbook.ps that if we ...
41 views

### How can I have constant time initialization for multi-dimensional arrays?

For a regular array, I understand that if we have the tradeoff of space vs time, and we use more space to implement a Which, Data, and When pointers to the actual array, we can initialize the array in ...
11 views

### What's a good design pattern for bidirectional signals/events? [migrated]

This problem feels rather basic, yet I've never known a great solution. I'm looking for a way for components in an application to notify each other while being as decoupled as possible (both at ...
26 views

### Solving for the matrix $W$ in an equation involving $W \cdot W^{T}$

Having large matrices, $W$ (the unknown) and $M$ (known), is it possible to solve for $W$ in this equation $$W \cdot W^{T} = M,$$ where $M$ can have negative entries.
15 views

### What would be a good sized project for a student to show to an employer to get a first job / co-op job [on hold]

I'm a computer Science student interested in programming and software engineering who is looking for a co-op position through my school. I was wondering if anyone has gotten a Job as a student or ...
20 views

### Time Complexity Problem [duplicate]

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta ( n)$$ I have been trying to solve this question but I could not find anything. I tried to build recursion tree but I can not find the sum. Do you ...
21 views

### parallelizing $k$-means

I'm having trouble thinking about the following. If we have two machines 1 and 2 that evenly split a set of data points, does $k$-means separately, then averages the result, does this agree with just ...
8 views

### Library for Custom trees in java or c++ [on hold]

Is there any library for building custom trees in java or c++. Essentially i want to construct a tree where each node could have an arbitrary number of children. Also if an iterator over the children ...
16 views

### Finding prime factors of non-random key generator

I have been working on a challenge i found on the internet. It is as follows: You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the ...
52 views

### Language Recognition Devices and Language Generators

I have few CS textbooks with me which discuss languages, well actually 2 plus old course notes supplied a few years ago. I have been searching the web too any only seem to come up with vague responses ...
13 views

### Automata Theory countably and uncountably infinite [duplicate]

I'm going over some of the pre-requisite math regarding Automata theory, and finite representations. I read the following: If ∑ is a finite alphabet the set of all strings over the alphabet (∑*) is ...
87 views

### Why choose D* over Dijkstra?

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
41 views

### Finite representations and programming languages Countably inifite

I'm going over some of the pre-requisite math regarding Automata theory, and finite representations. I read the following: If ∑ is a finite alphabet the set of all strings over the alphabet (∑*) is ...
11 views

### Modelling 2 object situation with Propositional Logic

I'm reading up on propositional logic, and I'm completely stuck on this example - spent the past few hours trying to figure it out! Any pointers would be appreciated. There's 2 trees, each with signs ...