All Questions

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

If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$

I have the problem If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$ To solve this I am using a result $BP\cdot NP\subset NP/poly$ which I can prove (not doing here). I have two solutions but ...
1 vote
2 answers
15 views

Deterministic infinite automaton equals a normal DFA?

Assume we have a deterministic infinite automaton. $DIA = (Q, δ, q_0, F)$. Meaning there is no limit to the number of states. I want to prove or disprove that this module equals a normal DFA. Attempt ...
1 vote
1 answer
18 views

Algorithm to find a set of nodes with a smaller set of neighbours in a bipartite graph

Given a bipartite graph, find a set of nodes on one side that has greater cardinality than the set of its neighbours on the other side. This is a conceptually simple problem, but I suspect it is ...
0 votes
0 answers
20 views

Desgining NFA under certain constraints

I've got homework to design NFA to accept a set of strings over {a,b,c} in which each string of the language satisfies: "cac" is a substring and "cc" is not a substring and the ...
  • 129
0 votes
0 answers
18 views

How fixed point Decimal to Binary conversion algorithm works?

I'm reading a book which says that to transform a number from decimal to binary with fixed point representation you have to follow these steps: Take the integer part (the one before the point) of the ...
  • 293
0 votes
0 answers
13 views

Ford-Fulkerson algorithm running in pseudo-polynomial time

Consider a graph with $n$ nodes and $m = \mathcal{O}(n²)$ edges. The maximum capacity among all edges is denoted by $C$. The running time is given by: $\mathcal{O}(nmC)$ If I consider the input size ...
  • 1
0 votes
1 answer
40 views

What recurrence describes the time complexity of this algorithm?

The problem is as follows: The input is an array $A$ of $n$ natural numbers such that: (1) if the maximum occurs in $A[p]$ for an index $p$, then $$A[1] \leq \ldots \leq A[p-1] \leq A[p]$$ and $$A[p] ...
1 vote
0 answers
17 views

Is Dijkstra's algorithm used in cheapest airfare calculators?

Is Dijkstra's shortest-path graph algorithm used in cheapest airfare calculators like Expedia or CheapAir?
  • 155
0 votes
1 answer
24 views

64-bit Xorshift with 2^96 or 2^128 period

Can we create Xorshift generator, as Marsaglia in "Xorshift RNGs" does, using 64-bit numbers, but with period 2^96 or 2^128? He proposed PRNG with period 2^96: ...
  • 133
1 vote
0 answers
7 views

Difference between Hadlock's algorithm and A* search

I recently read about pathfinding algorithms on grids. It seems two of the most popular are Lee's algorithm and Hadlock's algorithm. Other than the space optimizations that these algorithms employ, it ...
0 votes
0 answers
19 views

Finding the Optimal Palette for a Set of Images

Motivation I want to draw pictures using indexed colors. As I have limited space for colors per-palette, I want to choose palettes in an intelligent fashion, based on the pictures I want to draw. The ...
0 votes
0 answers
14 views

What are the similarities and differences between dependent function application and ML functor application?

Advanced Topics in Types and Programming Languages gives this rule section 2.2 gives this rule for dependent function application: $$\frac{\Gamma \vdash t_1 : (\Pi x : S.T) \quad \Gamma \vdash t_2 : ...
0 votes
3 answers
33 views

How do you stop an algorithm at a specific run time?

so I'm trying to write an algorithm in C to play the game of Reversi. I've already written in basic minimax algorithm yet I am not very satisfied with it. I want to implement alpha-beta pruning to my ...
  • 101
2 votes
2 answers
28 views

Is there a common notation for describing this operation $coNP\; ? \; NP = DP$?

While working with complexity classes, I've come along the definition of $DP$ (or $D^p$): $$DP = \{L_1 \cap L_2 \mid L_1 \in NP \text{ and } L_2 \in coNP\}$$ I am interested in a different (and much ...
  • 301
1 vote
0 answers
17 views

Finding an approximate double-zero using binary search

Let $f$ be a continuous real function on $[-1,1]$. The function is accessible via queries: for any $x$, the value of $f(x)$ can be computed in constant time. If $f(-1)<0$ and $f(1)>0$, then by ...
-1 votes
0 answers
11 views

What is encryption and how is it used in protecting files?

What is encryption? How does it work to protect files? Please explain. Oh and how can I do that by myself???
  • 1
1 vote
0 answers
10 views

Simplified Memory Bounded A*

I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
0 votes
1 answer
28 views

Designing a DFA with nth character condition for any integer n

Let n be an integer. How can I write finite automata for the language L? L = {W∈{$0,1,2$}*| The $n_{th}$ from last letter in w is $0$}. (Please suggest answers; not hints.) Attempt Using Regex, I ...
0 votes
1 answer
14 views

Uses of Hex and Octal numbers in programming

Where are these number patterns, Octal and Hex, being used? I read this but I want to know where they are used in programming.
  • 1
0 votes
1 answer
24 views

Workers with certain strength carrying boxes. (Greedy)

I just had an algorithms exam and had the following problem: Supposed there are $n$ workers and $n$ objects. Each worker has a strength, $s_i$ and each object has a weight $w_i$. Each worker needs to ...
  • 1
1 vote
1 answer
52 views

As far as we know, what does GPT-4's training data look like?

I was asking ChatGPT local history questions, because I knew many of the answers and could test the robot. But lots of details were wrong and while it can write citations, it won't disclose its ...
0 votes
1 answer
19 views

Prove that the problem MATCH is NP-complete

The problem MATCHED is defined as follows: given an infinite set S of strings of arbitrary length over the alphabet {0, 1}, determine if there exists a character of length n over the alphabet {0, 1} ...
0 votes
0 answers
31 views

How do you deal with Skolem functions which escape their scope in elimination rules?

If you have an elimination rule for tuples which introduce the left and right pair into the type checking context, what do you do if the type of one of the elements is quantified and has been ...
0 votes
0 answers
28 views

How to calculate the upper bound of the gredient of a multi layer ReLu neural network

Layers: We shall denote in the following the layer number by the upper script $\ell$. We have $\ell=0$ for the input layer, $\ell=1$ for the first hidden layer, and $\ell=L$ for the output layer. The ...
0 votes
3 answers
38 views

How do you write a logic function to determine if one 2s complement binary number is less than another?

Working on logic design in class, and I'm trying to figure out how to write a specific logic function [and by write, I mean something along the lines of (x NOR y) OR (a NOR b), for example] It asks to ...
  • 1
0 votes
1 answer
35 views

Is there a maximal set of programs that terminate?

It seems useful to characterize terminating programs. While trying to formulate that as a well-defined question I was wondering about the following problem: Is there a maximal decidable set of ...
  • 1
1 vote
2 answers
37 views

Explanation of Cook-Levin Suitable for First Years

TLDR; Looking for Explanation of Cook-Levin theorem palatable to CS first years who are theory averse I'm a prof. teaching first year algorithms+programming and want to give my students a taste of ...
0 votes
1 answer
32 views

Parsing algorithms

I have experimented with a grammar that I could turn into a strict left-to-right finite state automaton driven algorithm (bottom up, table driven). The FSA could be complex, that's not a problem. It ...
1 vote
0 answers
17 views

Does adding a polynomial-time function impact APX-hardness?

I have two optimization problems $A$ and $B$, and I recently managed to show that there exist functions $f$ and $g$ that are computable in polynomial time, such that for any instance $x$ of $A$ there ...
  • 11
-1 votes
0 answers
24 views

What is a practical example of a Context-Free Grammar?

I've been looking into Abstract Syntax Trees and came across the idea of a Context-Free Grammar which is described in the following way: In formal language theory, a context-free grammar (CFG) is a ...
  • 99
1 vote
0 answers
24 views

Did Jon von Neumann know about Claude Shannon's work when he wrote the "First Draft of a Report on the EDVAC?"

In the "First Draft" JvN described an adder circuit to do binary addition, which was a much faster way of doing computer addition than using decimal lookup tables as the ENIAC had done. JvN'...
  • 111
0 votes
0 answers
22 views

Why $rank(C|_V)\geq rank(C)$ for $r$-rank preserving subspace for depth 3 circuits

I was reading Deterministic Black Box PIT Testing for Generalized Depth 3 Arithmetic Circuits - Karnin and Shpilka In the Theorem 3.4 they told $rank(C|_V)\geq rank(C)$ We have $C|_V$ which is ...
-2 votes
1 answer
38 views

Find Number of subsequences such that bitwise OR is same as sum

Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
  • 7
0 votes
0 answers
25 views

Upper bound of traveling salesman problem via dynamic programming

For a set of $n$ cities, the total time to compute OPT (see Fomin & Kratsch, Chapter 1) is given to be \begin{equation} \sum_{k=1}^{n-1} O\left(\left(\begin{...
  • 101
0 votes
0 answers
30 views

Function types in Computer Science Metanotation

See Guy Steele's slides for what I refer to by "Computer Science Metanotation", specifically the bits about BNF. I often make use of the BNF syntax observed there, as a substitute for ...
0 votes
0 answers
15 views

Is proof based calculus more useful to become an AI researcher and an advanced specialist?

I don't know which single variable calculus course to choose: mit 18.01 or mit 18.014( proof-based calculus). I want to become an advanced specialist
0 votes
1 answer
48 views

Knapsack with no capacity

Given a set $S$, a value function $v(s)$ and a cost function $c(s)$ for all $s \in S$, and integers $B$ and $K$, the classic formulation of the Knapsack problem asks if there is a subset $S' \subseteq ...
0 votes
0 answers
18 views

How to prove (L+M)* = M*.(L.M*)*

Question is to simplify (LM*)* and I couldn't figure out a way to simplify it. Since (L+M)* = M*.(L.M*)*, I guess we can say that it cannot be simplified more. So how do we prove that they are the ...
0 votes
0 answers
23 views

Is the existence of multiple algorithms for one problem the example of application of homotopy type theory?

There are problems which can be solved by multiple different algorithms, like shortest-path in graph: https://en.wikipedia.org/wiki/Shortest_path_problem. By Curry-Howard isomorphishm, each problem is ...
  • 1,381
1 vote
0 answers
22 views

Efficient generalized suffix array/tree construction for prefix trees

Is there any algorithm that can efficiently construct a generalized suffix tree or array (or something similar) for a set of strings represented by a prefix tree (trie)? In particular, I'm wondering: ...
  • 1,217
0 votes
1 answer
67 views

Optimization of algorithm

Question: There are N soldiers standing in a straight line with ID 1 to N: [1,2,3,4,5] You are given array of IDs of length K in the order they are called : [3,1,2,1] When a ID is called the soldiers ...
3 votes
2 answers
100 views

An algorithm that is $O(n^{\log(n)})$

After having searched for a while, and after having read this https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities I was just wondering: is ...
  • 131
0 votes
0 answers
21 views

I'm having trouble storing the value in R0 into the correct memory location (LC-3 Assembly)

Here is my LC-3 Assembly code. It is designed to add up the 10 values in x3100 through x3109 and store them in x310A. It correctly adds the values, storing the total in R0, however I cannot seem to ...
  • 1
0 votes
0 answers
14 views

Zero Knowledge Protocol for Search Problem

Does anyone know any zero-knowledge protocol that addresses the search problem, i.e. finding the output to a query without revealing the query or any other output?
-1 votes
2 answers
60 views

A new algorithm for determining if a number is prime or not

This approach has been on my mind for quite some time. I did come up with it myself, I searched some methods for determining prime numbers but never came across anything similar to this. ...
-2 votes
1 answer
87 views

Is DNA computation Turing complete?

I have heard DNA being referred to as "code", this is because it is an instruction set which dictates the bodies' properties. However, DNA (as far as I have learned), has no conditional ...
1 vote
0 answers
26 views

prove the correctness of greedy algorithm on interger optimize

Let $n$ and $r$ be positive integers. For i = 1,2,...,n, let $f_i$ be a univariate real-valued function defined in the integer domain and let $f_i(x_i)$ be $-\infty$ for negative integer $x_i$. Any ...
0 votes
0 answers
7 views

Role of State Dynamics Target Network in DDPG

I am trying to create a variant of DDPG in MATLAB that has no action-value $\langle Q \rangle$ net, but that instead works with networks $\langle V \rangle, \langle f \rangle, \langle r \rangle$, and ...
0 votes
1 answer
23 views

Time complexity to convert a truth table to a boolean circuit

The SAT problem is often explained in terms of truth tables. Given some random boolean circuit, calculate its truth table; does there exist an output of $1$ in the truth table? But how about going the ...
0 votes
1 answer
11 views

Confusion with Execution of NDFA

I do not understand the "execution graph" (I think that's what it's called) of the following Non-Deterministic Finite Automata, given on pg 48-49 of Sipser's Intro to TCS (3rd edition): And ...

15 30 50 per page
1
2 3 4 5
928