O GoConqr está de visual novo! Conte para nós o que você achou.

Registre-se grátis

Quiz

Backtracking

Vicente García D 12 perguntas

Fazer o quiz

Este quiz tem tipos de pergunta que abrem no player de sempre.

Perguntas do 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. AVerdadeiro
    2. BFalso
  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. AVerdadeiro
    2. BFalso
  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. AVerdadeiro
    2. BFalso
  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 backtrackingImagem da pergunta 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;

Informações

Descrição
Bachelor of Software Engineering - Algorithmics course - University of Oviedo
Idioma
English
Visualizações
40
Avaliação
Ainda sem avaliações
Avalie este quiz
Avalie este quiz

Fale Conosco

Sobre o que é sua mensagem?

O que você acha do novo visual?

Você gostou?