algorithms.md

KYT/CAT - Algorithms

Q.1 What common thing represents an algorithm?:

• A cooking recipe

Q.2 Which action is based on NP-problems?:

• Encryption of data

Q.3 What are 2 advantages of a greedy algorithm?:

• It has a reasonable complexity
• It is easy to implement

Q.4 Which statement is correct?:

• dynamic programming is less efficient than divide and conquer
• dynamic programming is recursive
• dynamic programming uses the answers of previous sub problems
• dynamic programming solves each subproblems independently

Q.5 What is the major inconvenient of a greedy algorithm?:

• it doesn’t always provide the globally optimum solution

Q.6 How could we consider heuristics?

• as shortcuts

Q.7 Which problem is not a NP-one?:

• Rubik’s cube

Q.8 When inputs are almost sorted, which statement is correct about sorting algorithms?:

• Some algorithms are slower than usual
• Some algorithms are more efficient than usual

Q.9 What is the complexity of an algorithm containing one loop in one loop?:

• O(N2)

Q.10 Which sorting algorithm uses a “divide and conquer” technique?:

• merge sort

Q.11 Which class contains the sudoku problem?:

• np

Q.12 How many ways can we sort data?:

• a lot

Q.13 When inputs are reversed, which statement is correct about sorting algorithms?:

• Some algorithms are slower than usual

Q.14 Which statement is correct?:

• All sorting algorithm generally give the same output
• All sorting algorithm have exactly the same complexity
• All sorting algorithm have exactly the same efficiency
• All sorting algorithm need the same time to terminate

Q.15 When is it wise to use the Dijkstra’s algorithm?:

• While traveling

Q.16 Which application uses a greedy algorithm?:

• Huffman’s lossless data compression

Q.17 What is the complexity of an algorithm containing two loop in one loop?:

• O(N2)

Q.18 Which basic actions are performed on the data structures?:

• Insertion, deletion, sorting and searching

Q.19 Which statement is correct?:

• A solution of a NP-problem cannot be checked
• A solution of a NP-problem can be found relatively fast
• A solution of a NP-problem can be checked relatively fast
• A solution of a NP-problem cannot be found

Q.20 What is the objective of a heuristic algorithm?:

• find quickly a solution that is good enough

Q.21 Which statement is correct?:

• algorithm producing the same result are the same
• two different algorithms will produce two different results
• some algorithms are better than others even if they produce equal results
• the outputs of an algorithm is independent from the input

Q.22 Which statement could define the “dynamic programming” paradigm ?:

• Using some shortcuts to obtain the solution of the main problem
• recursively combining results of independent subproblems to obtain the solution of the main problem
• using the results of overlapping subproblems to obtain the optimum solution of the main problem
• replacing original input by a smaller one, find a solution, then transform it to obtain the solution of the main problem

Q.23 Which statement could define an algorithm ?:

• set of instruction to accomplish a task

Q.24 Which statement is correct ?:

• the efficiency of one sorting algorithm depends on the inputs
• the fastest sorting algorithm is always the same, regardless of the inputs
• the correctness of one sorting algorithm depends on the inputs
• the complexity of one sorting algorithm depends on the inputs

Q.25 What allows the big-O notation ?:

• it simplifies the analysis of algorithm efficiency

Q.26 Which statement could define the “divide and conquer” paradigm ?:

• recursively combining results of independent subproblems to obtain the solution of the main problem
• replacing original input by a smaller one, find a solution, then transform it to obtain the solution of the main problem
• using some shortcuts to obtain the solution of the main problem
• using the results of overlapping subproblems to obtain the option solution of the main problem

Q.27 Which data structure follows the rule “First-In-First-Out” ?:

• a queue

Q.28 What generally allows merge sort compared to selection sort ?:

• it sorts faster

Q.29 What tool allows to “observe” the possibilities of events ?:

• a tree

Q.30 Where is it that heuristic can’t be found ?:

• in brute-force algorithms

Q.31 What does contain the NP-complete class ?:

• the hardest NP-problems

Q.32 What choice makes a greedy algorithm at each stage ?:

• optimal choice