All Questions

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

How can any non-primitive-recursive function like the Ackermann function be implemented on hardware?

If for-loops and function calls both boil down to jump instructions when implemented on a real machine, then how is "The Ackermann function isn't implementable with for-loops" a meaningful phrase?
-1
votes
0answers
9 views

Turing Machines,Robots and Artificial General Intelligence [on hold]

Are Turing machines the only process and/or method to creating true artificial intelligence?
0
votes
0answers
9 views

boolean algebra (proof with identities) X=X.Y+X.Y' [on hold]

Having trouble figuring out which boolean identities will be useful in proving x = xy + xy'.
0
votes
0answers
7 views

Traverse tree collecting nodes combinations

Summary: I have a tree, containing car parts, from which I need to build all valid combinations of these parts. Parts can be required - every build must contain them. Parts can be optional. Parts ...
0
votes
1answer
9 views

How do we determine whether a heuristic is better than another in A* search Algorithm?

I am trying to solve a Maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristics. Currently, I explored Manhattan and Euclidean distances. ...
0
votes
0answers
4 views

Dual boot from two separate physical storage devices [migrated]

I have a new laptop that has a 256GB NVMe SSD drive with Windows 10 currently installed. The laptop has 2 NVMe SSD slots, so I plan to move the 256GB SSD to the second slot, and insert a new 1TB SSD ...
0
votes
0answers
11 views

NFA that accepts 0* or 1*

Problem statement: Produce an NFA that accepts the strings 0* and 1*. So 000 and 11 would be accepted, while 101 would not be. I'm a bit concerned about my idea because not all combinations of the ...
4
votes
1answer
58 views

Random restarts for unsatisfiable problems

In the worst case, Boolean satisfiability (assuming P!=NP) takes exponential time. Nonetheless, modern SAT solvers using variants of DPLL, are able to solve enough instances to be useful in practice. ...
1
vote
1answer
11 views

Maximum-cardinality matching in unbalanced bipartite graphs

Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$. The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So ...
0
votes
1answer
10 views

Busy-Beaver-like question for WHILE-Programs (Theoretical CS)

So this is exam-task is called "Busy WHILE-Programs" In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following: ...
0
votes
0answers
18 views

Minimise the maximum degree of a vertex in a connected graph

Given $N$ vertices and $M$ edges, how to create a connected graph so that I can minimize the maximum degree of every vertex. A vertex can have at most degree $N$ (self loop and other $N-1$ edges). ...
2
votes
0answers
19 views

Proving with co-induction principles

I'm going through Adam Chlipala's "Certified Programming with Dependent Types" (available here for convenience), and I'm a bit stuck at internalizing the introduction of co-induction principle for the ...
0
votes
1answer
15 views

How is the right, root, left order traversal called in a binary search tree?

In a Binary Search Tree you have the following orders for traversal: Left, Root, Right is called Inorder (or ascending order). Root, Left, Right is called Preorder. Left, Right, Root is called ...
1
vote
0answers
14 views

Creating N using commands of the form A=2A-B [on hold]

You are given two integers L and R. Their values are initially set to L=0 and R=1. You can change their values by performing the following Commands: The command ...
1
vote
0answers
20 views

Algorithm for out-of-area point classification

I have a device that sends its coordinates every 30 seconds. When I receive the coordinates, I classify the point as either belonging to (ie being inside) one of a number of predefined areas (so I ...
0
votes
0answers
15 views

C++ finding the shortest path, reducing time complexity, dijkstra v Floyd Warshall Algorithm?

I have an algorithm that I am performing on a graph and I am looking to do an analysis of how to speed it up and would appreciate any comments. The algorithm iterates over every edge in the graph. ...
0
votes
0answers
13 views

A* algorithm example explained

I am trying to understand A star algorithm. I am aware that it follows the sum of the current cost and heuristic, therefore f(n) = c(n) + h(n) in order to expand a ...
0
votes
0answers
22 views

Impossible recurrence relation help with masters theorem, plus evaluation of complexity

I had an exercise to solve a recurrence relation in my exam, I think it was a tricky question but I am not 100% sure. The recurrence was $ T(n) = 2*T(n) + \sqrt{n} +42 $, it was specifically asked to ...
1
vote
0answers
26 views

Minimum path cover in a DAG

Given a directed acyclic graph $G=(V,A)$ and a set $A'$ of $A$. It is well known that searching for a minimum number of vertex-disjoint paths that cover all the vertices of $G$ can be solved in ...
0
votes
0answers
13 views

solve T (n) = 2nT (n/2) + nn b) 2T (n/4) + n0.51 by master theorem in design and analysis of algorithm [on hold]

T (n) = 2nT (n/2) + nn b) 2T (n/4) + n0.51 apply master theorem in design and analysis of algorithms
0
votes
0answers
14 views

How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))

We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki "This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n ...
0
votes
0answers
13 views

Turing Machine, Robots and Artificial General Intelligence [on hold]

Are Turing machines the only process and/or method to creating true artificial intelligence?
0
votes
0answers
19 views

AVL Tree confusion

I have some confusion with regards to AVL trees and the heights of various subtrees. When initially reading the overview of the algorithms purpose(to keep the tree balanced) I thought it put limits ...
0
votes
1answer
31 views

Is JavaScript a homoiconic language?

I can't help but notice the uncanny resemblence JavaScript has to LISP. JSON (JavaScript Object Notation), for instance, is a data structure that can be reconstituted into an object by subjecting it ...
0
votes
0answers
13 views

Declaring multi-dimensional array using CFG

I am still juveline to compilers and formal languages. I've tried to write context-free grammar (CFG) for a multi-dimensional array, but I am not sure of my solution, so could you suggest your CFG for ...
0
votes
0answers
13 views

In the right-rotation case for red-black trees, there is a less efficient way to recolor it, why is it not O(log(n)) anymore?

So the first time I tried to recolor this insertion case from memory, I ended up with the right-hand side recoloring; of course the left recoloring is more efficient as the loop ends at this point. If ...
2
votes
1answer
23 views

Finding partition with maximum number of edges between sets

Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible? For ...
2
votes
1answer
27 views

Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar)

I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer): Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}...
2
votes
1answer
12 views

DP for Weighted Interval Scheduling: why is sorting by finish time necessary?

Problem In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ has ...
0
votes
0answers
11 views

Given a DFA M, formally define an NFA N such that L(N) = {x in L(M) | x = reverse(x)}

The english description of the question is (from my understanding) N accepts all strings that are both palindromic (the same forwards as it is backwards) and accepted by M. After a lot of toil and ...
0
votes
0answers
8 views

Is Decimal (correctly-rounded arbitrary precision decimal floating point arithmetic) fixed-point, floating-point or something else?

The Decimal data type I am referring to is GNU MPFR(https://en.wikipedia.org/wiki/GNU_MPFR), or libmpdec (http://www.bytereef.org/mpdecimal/doc/libmpdec/index.html). I have been searching for ...
0
votes
0answers
11 views

Generate all combinations of values that are less than array's elements and have a sum = target

I want to find a way to generate sets that contain elements that sum to a certain target. Initially, I have an array that contains elements representing the maximum value that can be stored in that ...
1
vote
1answer
19 views

Proving that $S_1+S_2 \leq f^{-\omega(1)}$

I am trying to show for every c, there exists $M\text{ such that }(x,y,z)\geq M$ then $S_1(x,y,z) + S_2(x,y,z) \leq ( f (x,y,z))^{-c} $ . For a particular $S_1,S_2,f$. Does it suffice to prove there ...
0
votes
0answers
6 views

Algorithm for Autonomously Culling Swarm

I'm trying to find an algorithm that would be able to cull a swarm of unknown size to around a known number with no overarching controller or dynamic registry (Each node should be able to decide ...
0
votes
0answers
5 views

Error in setting up gstreamer pipeline in OpenCV Capture function

I am using Ubuntu 14.04. The cmake version being used is 2.4 and gstreamer-1.0 is used. When this command is run through command line, gst-launch-1.0 autovideosrc ! autovideosink The video is ...
2
votes
1answer
27 views

Why does Bellman-Ford algorithm use < rather than ≤?

The Bellman-Ford Algorithm uses a less-than symbol rather than a less-than-or-equal-to symbol. How does this identify that there is a negative cycle? For instance, say I have the below example going ...
-1
votes
1answer
21 views
0
votes
1answer
23 views

What is the relation between the formal definition of strictness and its intuitive notion

I am currently reading Functional Programming in Scala and have encountered a statement in the book I cannot quite make sense of. On page 67, we are told the formal definition of strictness: "If the ...
4
votes
0answers
95 views

Is this equivalent to any famous NP-complete problem?

Given the following problem. Given an $n\times n$ matrix $A := \{a_{ij}\}$. Find an $n\times n$ matrix $X := \{x_{ij}\}$, where $x_{ij} \in \{-1, 1\}$ for $i, j \in [n]$, that minimizes the ...
2
votes
1answer
35 views

Smallest integer i stored as a float such that i+1=i

So I had an assignment which asked me to find the smallest integer $i$ which when represented as a float is such that $i+1=i$ My approach- By making a simple C++ program , we get $i=16777216$ or $i=2^...
3
votes
1answer
52 views

Algorithm to find a simple path with maximum weight less than a constant in DAG

Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should ...
0
votes
0answers
13 views

Why is BFS “vertex based” and DFS “edge based”?

I am trying to understand the various differences between Breadth-first and Depth-first search on graphs. Two sources state that BFS is "vertex based" and DFS is "edge based" even though in ...
-4
votes
1answer
19 views

DFA detterministic finite automata [on hold]

construct a DFA which accepts a divisible by 3 and b should also be divisible by 3
-1
votes
0answers
22 views
1
vote
1answer
27 views

Is following grammar has language which is inherently ambiguous?

Grammar is as follow: $S \rightarrow aaAb | aab | A$ $A \rightarrow aaAb | aAb | \epsilon$ I think that this grammar has equivalent unambiguous grammar as follow. Let’s first rewrite the grammar ...
1
vote
2answers
39 views

What are some decidable problems which cannot be solved in real life(due to time and memory constraints)?

The first line of Sipser book for the Chapter- 'Time complexity', says that: Even when a problem is decidable and thus computationally solvable in principle, it may not be solvable in practice if the ...
0
votes
0answers
16 views

Converting Lambda Calculus functionality to predicate logic syntax

I am trying to validate the simplest possibly notion of a formal system as relations between finite strings. I know that Lambda Calculus has the expressive power of a Turing Machine: <λexp> ::= &...
-2
votes
0answers
18 views

Please can someone help me with this assignment on flowchart and pseudo code? [on hold]

The question is: Draw the flowchart and a pseudo code for calculating the gross monthly salary of 50 employees of any company.
0
votes
0answers
29 views

L1 Cache Missing Timing Attack

I'm trying to understand Section 3: L1 Cache Missing in the paper Cache Missing for Fun and Profit. I'm stuck on trying to figure out how the covert channel is ...
4
votes
1answer
31 views

Language containing all unambiguous grammars

Suppose $L$ is the language of the unambiguous grammars. That is, a sentence $w\in{}L$ if it is a string that describes an unambiguous context-free grammar. Considering that deciding whether a ...

15 30 50 per page