Algorithmics Correction Final Exam (P2)

Algorithmics Correction Final Exam #2 (P2) – Undergraduate 1st year S2 Epita Solution 3 (List→ AVL– 5 points) Speciﬁcations: The function list2avl(L) returns an A -V L (class AVL) built from the list L sorted in stricly

Algorithmics Correction Midterm Exam (Version profs)

Algorithmics Correction Midterm Exam #1 23 avril 2019 - 13:30 Undergraduate 1 st year S1# Epita (a) There is no precondition It is an internal operation de ned on the bounds of the vector

Recursive Algorithm Correctness (Continued)

CSC236H1F Lecture Summary for Week 7 Fall 2015 Recursive Algorithm Correctness (Continued) Example 1 (Binary search algorithm) Consider the following recursive implementation of binary search algo-

An Atmospheric Correction Algorithm for Remote Sensing of

improved atmospheric correction algorithms must be developed for the remote sensing of Case 2 waters Previously, we developed an atmospheric correction algo-rithm for hyperspectral remote sensing of ocean color [9] In this paper, we describe modiﬁcations to this algorithm for multichannel remote sensing of coastal waters using MODIS

CAAS: an atmospheric correction algorithm for the remote

infrared (NIR) correction scheme (originally with assump-tions of zero water-leaving radiance for the NIR bands) and several ancillary parameters to remove atmospheric effects in remote sensing of ocean colour The failure of this algo-rithm over complex waters has been reported by many recent investigations, and can be attributed to the

An algebraic algorithm for nonuniformity correction in focal

effective bias correction with relatively few frames This will be demonstrated with both simulated and real infra-red data Because of its highly localized nature in time and space, the algorithm is easily implemented and com-putationally efﬁcient, permitting quick computation of the correction matrix that is needed to compensate con-

Digital algorithm for dispersion correction in optical

Digital algorithm for dispersion correction in optical coherence tomography for homogeneous and stratified media Daniel L Marks, Amy L Oldenburg, J Joshua Reynolds, and Stephen A Boppart The resolution of optical coherence tomography OCT often suffers from blurring caused by material dispersion

See Something, Say Something: Correction of Global Health

Our previous work considering algo-rithmic correction speculated that part of its effectiveness in reducing misinformation resulted from trust in the unbiased nature of algorithms People tend to

Brahim BESSAA

Les Structures de Contrôle (Conditionnelles – Itératives) Exercices Corrigés d’Algorithmique – 1ére Année MI 5 EXERCICE 1 Ecrire un algorithme qui demande un nombre à l’utilisateur, puis calcule et affiche le carré de ce nombre

[PDF] Exemples de fonctions en Python - Lirmm

[PDF] Récursivité (1/3)

[PDF] Corrigé Série d 'exercices n°4 : Les fonctions et procédures

[PDF] Bases d 'algorithmique

[PDF] COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE

[PDF] FICHE n°6 : PROGRAMMER DES BOUCLES - Maths-et-tiques

[PDF] Correction TD1 algorithme

[PDF] Correction TD1 algorithme

[PDF] Algorithmique au lycée

[PDF] fiche maternelle algorithme imprimer- pdf documents

[PDF] Fiche enseignant ALGORITHMES NIVEAU : GRANDE SECTION

[PDF] Algorithme et numération - Académie de Nancy-Metz

[PDF] L 'atelier des petites chenilles en PS Etape 1 - académie de Caen

[PDF] reproduire une suite algorithmique - Accueil DSDEN 22

[PDF] Rappels : Tableaux et Matrices

Algorithmics

Correction Final Exam #2 (P2)

Undergraduate 1

styear S2 - Epita

30 May 2018 -14 : 00

Solution 1(AVL -3 points)

Final AVL from th list[25,60,35,10,20,5,70,65,45].?

Final AVL:Rotations:

rlr(25) rdg(25) lrr(25) rgd(25) rr(35) rd(35) rlr(60) rdg(60) rlr(35) rdg(35)

Solution 2(Leonardo trees -3 points)

1. The Fibonacci treeA5is the one in figure 1 with each node containing its balance factor value.

Figure 1: The Fibonacci treeA5

2. (a)hn=n-1

(b)A0is a leaf,A1has a single node at its left, nothing at its right : these trees are height- balanced. Withn≥2,Anheight isn-1. Its subtrees areAn-1of heightn-2andAn-2of height n-3. Thus, the balance factor of the root ofAnis 1 (n-2-(n-3)). All internal nodes of a Fibonacci tree have a balance factor of 1 : it is an height-balanced tree. 1 AlgorithmicsCorrection Final Exam#2 (P2) -Undergraduate 1 styear S2 Epita

Solution 3(List→AVL-5 points)

Specifications:

The functionlist2avl(L)returns an A.-V.L. (classAVL) built from the listLsorted in stricly increasing order.

First version :

•Works on[left,right](as in lecture) •Recursive function returns the height: to compute balance factors in each node

1def__sortedList2AVL(L, left, right):

2"""

3L[ left , right ]-> AVL

4"""

5ifleft > right:

6return(None, -1)

7else:

8mid = left + (right -left) // 2# or ( l e f t + right ) // 2

9B = avl.AVL(L[mid], None, None, 0)

10(B.left, hl) = __sortedList2AVL(L, left, mid - 1)

11(B.right , hr) = __sortedList2AVL(L, mid + 1, right)

12B.bal = hl - hr

13return(B, 1 +max(hl, hr))

15defsortedList2AVL(L):

16(A, _) = __sortedList2AVL(L, 0,len(L)-1)

17returnA

2 AlgorithmicsCorrection Final Exam#2 (P2) -Undergraduate 1 styear S2 Epita

Solution 4(AVL - Minimum deletion -6 points)

1. Rotations and height changes after minimum deletion:

bal(root)bal(right child)rotationΔh -1lr1 -200 1rlr1

2.Specifications:The functiondel_min_avl (A)deletes the node containing the minimum value

of the non-empty AVLA. It returns a pair: the new tree and a boolean that indicates whether the tree height has changed.

1defdel_min_avl(A):

2ifA.left == None:

3return(A.right , True)

4else:

5(A.left, dh) = del_min_avl(A.left)

6ifdh:

7A.bal -= 1

8ifA.bal == -2:

9ifA.right.bal == +1:

10A = rlr(A)# rdg (A)

11else:

12A = lr(A)# rg (A)

13return(A, A.bal == 0)

14else:

15return(A, False)

17# long version

18defdel_min_avl2(A):

19ifA.left == None:

20return(A.right , True)

21else:

22(A.left, dh) = del_min_avl2(A.left)

23if notdh:

24return(A, False)

25else:

26A.bal -= 1

27ifA.bal == 0:

28return(A, True)

29elifA.bal == -1:

30return(A, False)

31else:# A. bal ==-2

32ifA.right.bal == -1:

33A = lr(A)# rg (A)

34return(A, True)

35elifA.right.bal == 0:

36A = lr(A)# rg (A)

37return(A, False)

38else:

39A = rlr(A)# rdg (A)

40return(A, True)

3 AlgorithmicsCorrection Final Exam#2 (P2) -Undergraduate 1 styear S2 Epita

Solution 5(BST and mystery -4 points)

1.Returned results?

(a)call(25,B): None (b)call(21,B): 26 (c)call(20,B): 21 (d)call(9,B): 15 (e)call(53,B): None

2.bst_mystery(x, B)(Bany BST, with distinct elements).

At the end of part 1:

(a)Bis the tree that containsxin its root, None ifxis not in the tree. (b) On the search path,Pis the tree which root is the last encounter node before descending on the left (it stays None if we never go to the left).

3.call(x, B): ifxis found inBand is not the greatest value, the function returns the value just

afterxinB. Otherwise it returnsNone. 4quotesdbs_dbs5.pdfusesText_9

[PDF] Algorithmics Correction Final Exam (P2)