# All Questions

32,152 questions
Filter by
Sorted by
Tagged with
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?
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?
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'.
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 ...
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. ...
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 ...
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 ...
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. ...
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 ...
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: ...
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). ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
27 views

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 ...
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 ...
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
22 views

### How to calculate the time and space complexity of this scheduling algorithm? [duplicate]

How to time and space complexity of the following algorithm? ...
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 ...
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 ...
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> ::= &...
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.
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 ...