Self-assessment quiz

# What is algorithmic complexity? - [ ] A measure of the execution time of an algorithm > ❌ L'algorithmique de complexité mesure non seulement le temps d'exécution, mais aussi l'espace mémoire utilisé par un algorithme. - [ ] A measure of the memory space used by an algorithm > ❌ L'algorithmique de complexité prend en compte à la fois l'espace mémoire et le temps d'exécution de l'algorithme. - [x] A measure of the execution time and memory used by an algorithm > ✅ La complexité algorithmique mesure à la fois le temps d'exécution et l'espace mémoire nécessaire à un algorithme. - [ ] A measure of how complex an algorithm is > ❌ La complexité algorithmique ne mesure pas la difficulté de compréhension de l'algorithme, mais bien les ressources qu'il consomme. # What are we generally interested in when we study algorithmic complexity? - [ ] Average analysis > ❌ L'analyse moyenne peut être utile, mais on se concentre souvent sur le pire des cas pour garantir la performance de l'algorithme dans toutes les situations. - [ ] Pessimistic analysis > ❌ Bien que proche, le terme correct est "worst-case analysis" en anglais pour désigner l'analyse du pire des cas. - [x] Worst-case analysis > ✅ L'analyse du pire des cas est utilisée pour s'assurer qu'un algorithme fonctionnera dans des délais raisonnables, même dans les situations les plus défavorables. # Which of the following is the notation for linear and logarithmic algorithms? 1. [ ] $O(N)$ > ❌ O(N) représente une complexité linéaire, sans le composant logarithmique. 1. [x] $O(N \cdot log(N))$ > ✅ O(N \cdot log(N)) représente une complexité linéaire logarithmique, souvent rencontrée dans des algorithmes comme le tri rapide. 1. [ ] $O(N^2)$ > ❌ O(N^2) représente une complexité quadratique, où le temps d'exécution augmente en fonction du carré de N. # Which type of algorithm has complexity of the form $O(N^p)$? 1. [ ] Logarithmic algorithms > ❌ Les algorithmes logarithmiques ont une complexité de type O(log(N)). 1. [ ] Linear algorithms > ❌ Les algorithmes linéaires ont une complexité de type O(N). 1. [x] Polynomial algorithms > ✅ Les algorithmes de type polynomial ont une complexité de la forme O(N^p), où p est une constante. # What causes the large number of calculations in an algorithm? - [x] The number of loops > ✅ Les boucles augmentent le nombre de calculs en répétant des opérations, ce qui impacte directement la complexité de l'algorithme. - [ ] The number of variables > ❌ Le nombre de variables n'affecte pas directement le nombre de calculs d'un algorithme, sauf si ces variables sont utilisées dans des opérations coûteuses. - [ ] The number of functions > ❌ Le nombre de fonctions n'affecte pas le nombre de calculs, bien que certaines fonctions puissent inclure des boucles ou des appels récursifs. # Looking for the existence of a specific element in a list is an example of which type of complexity? - [ ] Logarithmic complexity > ❌ Une recherche dans une liste non triée nécessite de parcourir chaque élément, ce qui est linéaire, et non logarithmique. - [x] Linear complexity > ✅ Une recherche dans une liste non triée a une complexité linéaire O(N) car il faut potentiellement examiner chaque élément. - [ ] Constant complexity > ❌ Une recherche avec complexité constante O(1) n'est possible que dans des structures permettant un accès direct, comme un tableau indexé. - [ ] Quadratic complexity > ❌ La recherche linéaire n'implique pas de double boucle, donc elle n'a pas une complexité quadratique.

# What is a binary search tree (BST)? - [x] A tree structure that places smaller values on the left and larger values on the right > ✅ In a BST, each node's left subtree contains values less than the node, while the right subtree contains values greater. - [ ] A tree where each node has exactly two children > ❌ In a BST, nodes can have zero, one, or two children; the tree's structure depends on the inserted values. - [x] A data structure that maintains order among nodes > ✅ BSTs maintain an ordered structure, which makes operations like search and insertion efficient. - [ ] A tree used only for storing numbers > ❌ A BST can store any data that can be ordered, not just numbers. - [ ] A structure without any cycles or connections between nodes > ❌ While BSTs are acyclic, they are connected through parent-child relationships. # What are the main advantages of using a BST? - [x] Efficient searching due to its ordered structure > ✅ A BST's ordered structure enables efficient searching, with time complexity of O(h), where h is the height. - [ ] Constant time access to elements > ❌ Access time in a BST depends on the tree's height, not constant like in an array. - [x] Efficient insertion while maintaining order > ✅ Insertion in a BST is efficient and preserves the tree's ordered structure. - [ ] Guaranteed balanced structure > ❌ BSTs are not necessarily balanced; without balancing, they can degrade to linear structures. - [x] Supports operations like finding the minimum and maximum values efficiently > ✅ Due to its structure, a BST allows quick access to the minimum and maximum values by traversing left or right. # How do you find the minimum value in a BST? - [x] By following the left children from the root > ✅ In a BST, the minimum value is found by moving left until reaching a node with no left child. - [ ] By following the right children from the root > ❌ Following the right children finds the maximum value, not the minimum. - [ ] By checking every node in the tree > ❌ The ordered structure allows finding the minimum without checking all nodes. - [x] It has a time complexity of O(h), where h is the tree height > ✅ Finding the minimum takes O(h) time since it only requires traversing one side of the tree. - [ ] By balancing the tree first > ❌ Balancing is not needed to find the minimum in a BST. # How is the height of a BST significant to its performance? - [x] The height affects the efficiency of search, insertion, and deletion operations > ✅ The height of a BST determines the time complexity of operations like search, insert, and delete, making a balanced height crucial. - [ ] The height should always be equal to the number of nodes > ❌ A BST's height is not always equal to the number of nodes; it depends on the insertion order and balance of the tree. - [x] A smaller height makes the tree more efficient > ✅ A lower height means fewer nodes need to be traversed, improving the efficiency of operations. - [ ] The height does not impact performance > ❌ The height significantly impacts performance; a taller tree means longer search and insertion paths. - [ ] A BST with height 0 is ideal for all operations > ❌ A BST with height 0 would contain only the root node and offer no meaningful structure for larger data. # What is tree rotation in the context of BSTs? - [x] A method to balance the tree and reduce its height > ✅ Tree rotations adjust the structure of a BST to maintain balance and reduce its height. - [ ] A process to remove nodes from the tree > ❌ Tree rotation does not remove nodes; it rearranges them to maintain balance. - [x] A way to keep the BST property intact after restructuring > ✅ Tree rotations adjust the structure while preserving the BST property. - [ ] A technique used only in unbalanced binary trees > ❌ Tree rotation is also applied in balanced BSTs to maintain height consistency after insertions and deletions. - [ ] A replacement for rebalancing the tree > ❌ Tree rotation is a step within the rebalancing process, not a replacement for it. # What is a balanced BST? - [x] A tree where the left and right subtrees of every node differ in height by no more than 1 > ✅ A balanced BST ensures that no subtree is significantly taller than the other, optimizing performance. - [ ] A tree where all elements are on one side > ❌ A tree with all elements on one side is unbalanced, resembling a linked list. - [x] A tree that maintains efficient search, insert, and delete times > ✅ A balanced BST provides efficient operation times due to its optimal height. - [ ] A tree with only one node > ❌ A single-node tree is trivially balanced but does not represent the concept of balance in larger trees. - [x] A tree that may use rotations to maintain structure > ✅ Balanced BSTs, such as AVL or Red-Black trees, often use rotations to maintain balance after insertions or deletions.

# What is a randomized algorithm? - [x] An algorithm that uses randomness to make decisions > ✅ Randomized algorithms use random choices in their logic, which can lead to varying results or performance on the same input. - [ ] An algorithm that guarantees the same result each time it runs > ❌ Randomized algorithms may produce different outcomes on each run due to their use of randomness. - [ ] An algorithm with a fixed execution time > ❌ The execution time of a randomized algorithm can vary depending on its random choices. - [x] An algorithm that can sometimes give approximate solutions > ✅ Randomized algorithms may offer probabilistic guarantees rather than exact solutions. - [ ] An algorithm that only works with numerical data > ❌ Randomized algorithms can be applied to various data types, not just numerical data. # What is the main characteristic of a Monte-Carlo algorithm? - [x] It provides correct results with high probability but not always > ✅ Monte-Carlo algorithms have a high probability of producing correct results but may sometimes yield incorrect results. - [ ] It always produces a correct result > ❌ Monte-Carlo algorithms do not guarantee correctness on every run; they only achieve it with high probability. - [x] It has a predictable runtime > ✅ Monte-Carlo algorithms generally have predictable runtimes as they are optimized for speed over accuracy. - [ ] It stops running as soon as it encounters an error > ❌ Monte-Carlo algorithms are designed to continue running, even with potential variations in accuracy. - [ ] It does not use randomness > ❌ Monte-Carlo algorithms rely on randomness to make decisions in their process. # What is the main benefit of using a Las-Vegas algorithm? - [x] It always produces the correct result > ✅ Las-Vegas algorithms guarantee the correct result, but their performance may vary. - [ ] It provides approximate results to save time > ❌ Las-Vegas algorithms prioritize correctness and do not compromise by providing approximate results. - [x] It can run in expected polynomial time > ✅ Las-Vegas algorithms typically run in expected polynomial time, though the exact runtime can vary. - [ ] It runs without the need for random numbers > ❌ Las-Vegas algorithms use randomness to potentially enhance their performance while ensuring correctness. - [ ] It guarantees a fixed runtime > ❌ The runtime of Las-Vegas algorithms can vary due to their random nature, but they always produce the correct result. # Why are pseudo-random numbers commonly used in randomized algorithms? - [x] True random numbers are difficult to generate > ✅ Generating true randomness is challenging, so pseudo-random numbers are commonly used instead. - [ ] Pseudo-random numbers are always uniformly distributed > ❌ Pseudo-random numbers may not be perfectly uniform, but they are sufficient for most applications. - [x] They offer a balance between speed and portability > ✅ Pseudo-random number generators are designed to be efficient and compatible across different systems. - [ ] They are continuous rather than discrete > ❌ Pseudo-random numbers are typically discrete; generating continuous values requires additional processing. - [x] They allow replicable sequences for testing > ✅ Pseudo-random number generators produce repeatable sequences, which are helpful for testing and debugging. # What are two key properties of a good random number generator? - [x] Uniformity > ✅ Uniformity ensures that each possible value has an equal chance of being generated. - [ ] Predictability > ❌ A good random number generator should be unpredictable, not predictable. - [x] Independence > ✅ Independence means that the generated numbers do not depend on each other, maintaining randomness in the sequence. - [ ] Complexity > ❌ Complexity is not a desirable trait for random number generators, as simplicity improves efficiency and portability. - [ ] Determinism > ❌ Determinism is not a trait of ideal randomness; pseudo-random generators are deterministic, but true randomness is not.