The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
54 views

DPLL time complexity analysis

Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $\phi$ when all the $n$ variables have values assigned. Let $m$ be the size of $\phi$. ...
3
votes
1answer
271 views

Is there a more efficient algorithm than backtracking/dynamic programming?

Consider the following game: One day a castle is attacked at sunrise (by surprise) by n soldiers. Each soldier carries a canon and a rifle. The castle has strength s. On the first day each ...
6
votes
1answer
41 views

Conflict Driven Clause Learning backtracking clarification

On the wikipedia page here it describes pretty well the CDCL algorithm (and it seems the pictures were taken from slides created by Sharad Malik at Princeton). However when describing how to backtrack ...
2
votes
1answer
44 views

Basic question about backjumping in SAT solvers

I am reading "Formalization and Implementation of Modern SAT Solvers", by Filip Marić. My question is about how backjumping is defined. In an example [1], there is a conflict clause C equal to ...
4
votes
2answers
150 views

How does one formulate a backtracking algorithm

I am new to learning algorithms. I was reading backtracking algorithm for generating all strings for n bits. If I dry run the program I know the program is giving right result. But I didn't understood ...
1
vote
2answers
110 views

Maximum non-intersecting subset of circles

We are given a set of circles, stored by their center points in an array $A$. In particular, the center of the $i$th circle is at coordinates $(A[i].x, A[i].y)$. All the circles have radius of $k$. ...
1
vote
2answers
451 views

Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
0
votes
1answer
34 views

Devise a backtracking algorithm to allocate $p$ projects to $s$ students

There are $p$ projects and $s$ students where $p \le s$. Multiple students can work on the same project but the same student cannot work on multiple projects. All projects must be allocated and all ...
1
vote
1answer
58 views

Generating hard puzzles for a backtracking snake

Let $M$ be a matrix of height $h$ and width $w$. Each entry of $M$ is an integer. There is a snake that starts from the "left side" of $M$, and its goal is to reach the "right side" of $M$. To get ...
0
votes
1answer
153 views

Find all non-decreasing sequences given lenght and size [closed]

I'm trying to find a solution for this exercise: Give the pseudocode of an algorithm which takes two positive integers n and k and prints all the non-decreasing sequences of length k ...
1
vote
1answer
653 views

Backtracking for listing k elements

Can someone give me a hand here, I am new to backtracking, and preparing for an interview. I couldn't even attempt this question, please help. Describe a back tracking algorithm for efficiently ...
1
vote
1answer
360 views

Why does backtracking work the way it does?

I just recently started learning in a CS context (as opposed to a programming context) about simple recursive functions, along with the combinatorial applications, and techniques such as Backtracking ...