# All Questions

48,811 questions
Filter by
Sorted by
Tagged with
10 views

### How do you remember the algorithm for rotating a square matrix?

The algorithm for rotating a square matrix 90 degrees is neat, and it is documented here and here. However, it is difficult to remember, and requires one to look it up first in order to implement it. ...
• 173
11 views

### Quickly converting a regex into a minimized DFA

Is there some sort of algorithmic way to quickly convert a regex into a minimized DFA? I am able to somehow "guess" the DFA by playing around with the regex (as shown in the image, where the ...
13 views

### How to create a tree of height $lg(n)$ using Union-Find data structure

I'm wondering given a set $A$ of $n$ numbers, is there any procedure that can create a tree of height $lg(n)$ that contain all the elements of $A$ by applying consecutive Union by rank operation in a ...
• 71
8 views

### Find, in linear time, a line that intersects all the segments and has the largest possible slope, or determine that there is no such line

I'm wondering how to approach this question. Let e1, . . ., en be n horizontal segments in the plane. Find, in linear time, a line that intersects all the segments and has the largest possible slope, ...
19 views

30 views

### Can a binary tree be generated from Union-Find using union-by-rank?

I'm trying to determine if the following claims are true or false: Claim 1 When disjoint Union-Find is implemented using up-trees and union-by-rank, and initially  there was a set of 5 single nodes. ...
• 71
13 views

### Checking if two subgroups are equal in sage/python [closed]

I’ve defined two subgroups (E and F) as subgroups of a finite group B. B is a finite group which I defined as a quotient of a free group. My general goal is to determine if E is a subgroup of F. But ...
• 1
140 views

### Approximation algorithm for binary (linear) programs

I am interested in solving the following problem: $$\max c^\top x \qquad\text{s.t.}\\ Ax \le b\\ x \in \{0,1\}^n$$ One can assume that $c$, $A$ and $b$ have integer entries if that simplifies things....
• 540
1 vote
36 views

### What happens if CRC fails and errors are not detected?

Suppose you want to send a message M and let R be the CRC obtained using a generating polynomial ...
• 113
1 vote
1k views

### Arrays. Find row with most 1's, in O(n)

Suppose that each row of an $n \times n$ array $A$ consists of 1's and 0's such that, in any row of $A$, all the 1's comes before any 0's in that row. Assume $A$ is already in memory, describe a ...
19 views

### What formula was used here to calculate the average search time of the binary tree?

My teacher showed me the following slide on the PowerPoint with two binary search trees and their corresponding "average search times". The PPT did not mention what formula was used to ...
• 119
22 views

### In Lafont's interaction net, how to prevent undesirable annihilation?

Here is a simple case, given function f and input x, compute y = f(f(x)): this can be ...
• 103
1 vote
27 views

### Sparse bit string pattern matching

Suppose there are two strings of bits. Let's call them the needle (n) and the haystack (h). We'll say that the needle matches ...
• 111
649 views

• 173
29 views

### Minimal k-way comparison sorting algorithm?

I've watched 600 TV shows, and I want to sort them in order of how much I liked them. I'm bad at assigning absolute scores, but good at comparing relative enjoyment, so it has to be a comparison sort. ...
• 21
20 views

### Limited constant degree HamCycle

Let $G=(V,E)$ be a directed graph. I am interested in a "relaxed" version of the HamCycle problem. In my first case, the degree of each vertex is exactly 6, such that: 3 are outgoing edges ...
• 465
51 views

### Math major looking to learn some CS

I'm currently in school doing a pure math major, and I want to learn some computer science (potentially for jobs in finance requiring it but also just because I think it will be useful for the future),...
39 views

### How to write a Y-combinator implementation in javascript that does not exceed maximum stack size

TL;DR: Why applying a javascript implementation of a factorial function with a lazy Y combinator fails with "Maximum call stack size exceeded"? Here is the code: ...
943 views

### What is the difference between NP=EXP and ETH, and what does the community believe about their truth?

We know that $NP\subseteq EXP$ but not whether it is strict. The Exponential Time Hypothesis (ETH) states that SAT cannot be solved in subexponential time. My understanding is that most computer ...
• 3,982
14 views

### What to learn for Java after AP CSA

I finished my AP CSA class this year where we learned the structural basics of Java. Mainly the different variables, using methods, different loops, arrays, and array lists etc. What should I learn ...
• 101
1 vote
31 views

### Chromatic Polynomial of Hamming Graphs

I'm trying to calculate the chromatic polynomial of different Hamming Graphs , especially $H(3, 3) = K_3 \times K_3 \times K_3$, so the Graph Cartesian product of the complete graph with three ...
• 61