GoConqr has a new look! Let us know what you think.

Sign up free

Quiz

Backtracking

Vicente García D 12 questions

Take the quiz

This quiz has question types that open in the usual player.

Questions in this quiz (12)

  1. 1If you need to solve a problem and you know how to solve it using a dynamic programming algorithm, but you also know how to solve it using a bakctracking-based algorithm, which one you should usually use?
    1. ANeither
    2. BDynamic programming
    3. CBacktracking
  2. 2For the Magic Square problem, with a size of n=3, how many ways to arrange the n^2 numbers are there using brute force?
    1. A3
    2. B9
    3. C362880
    4. D81
    5. E27
    6. Fabout 1000
  3. 3Many problems can be represented as abstract graphs. Nodes usually represent valid changes and edges usually represent the state of the problem. Thus, to solve the problem we must find a node or a path in the associated graph

    1. ATrue
    2. BFalse
  4. 4The implicit graph used for backtracking is usually depicted as a tree, called [blank_start]tree of states[blank_end].
    With the technique of backtracking we perform a [blank_start]depth-first[blank_end] search of the tree.
    The objective is to find the nodes (states) that are [blank_start]solutions[blank_end] to the problem.
    To that end, a exhaustive and systematic [blank_start]search[blank_end] in the solution space of the problem is performed
    1. Atree of states
    2. Bdepth-first
    3. Csolutions
    4. Dsearch
  5. 5There are usually two versions of backtracking algorithms. There can be:
    - "first solution" if we only need a solution to the problem
    - "all the solutions" if we need all the solutions, the best or the worst solution
    1. ATrue
    2. BFalse
  6. 6Indicate which ones can be usually complexities when working with backatracking
    1. AO(2^n)
    2. BO(4^n)
    3. CO(n^2)
    4. DO(n)
    5. EO(nlogn)
    6. FO(n!)
  7. 7Which complexity is the worst?
    1. AO(n!)
    2. BO(n^n)
    3. CO(10^n)
  8. 8The memory consumption with backtracking depends on the height of the tree of calls and the waste of stack for each recursive call
    1. ATrue
    2. BFalse
  9. 9With backtracking, the height of the tree of states is usually [blank_start]O(logn)[blank_end] when we have a behaviour by division and [blank_start]O(n)[blank_end] when we have a behaviour by substraction
    1. AO(logn)
    2. BO(n!)
    3. CO(n^n)
    4. DO(2^n)
    5. EO(nlogn)
    6. FO(n^2)
    7. GO(n)
    8. HO(1)
  10. 10Permutations using backtrackingImage for question 10
    1. Asol[k]
    2. Bsol[i]
    3. Ck
    4. Di
    5. E(int j=0; j<n; j++)
    6. F(int i=0; i<n; i++)
    7. G(int j=0; j<level; j++)
    8. Hsol[level] = v[j];
    9. Isol[level] = v[i];
    10. Jsol[level+1] = v[j];
    11. Ksol[j] = v[level];
    12. Lmark[j] = false;
    13. Mmark[j] = true;
    14. Nmark[level] = false;
    15. Omark[level] = true;

Information

Description
Bachelor of Software Engineering - Algorithmics course - University of Oviedo
Language
English
Views
40
Rating
No ratings yet
Rate this quiz
Rate this quiz

Feedback

What is it about?

What do you think of the new look?

How do you like it?