The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
27 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
97 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
103 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
299 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
21 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
54 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
130 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
616 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
331 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 ...