------------ Definitions --------------
(Graded for correctness) Calculate the following function applications. Include all intermediate steps, with justifications. 1 Sample response that can be used as reference for the detail expected in your answer for this part: Calculating append( (1, 2, [])) ,3), we have append( (1,(2, [])) ,3) = (1, append( (2, []) ,3)) By recursive step of append: n=1, 1 = (2, []), m = 3 = (1, (2, append( [] ,3))) By recursive step of append: n = 2, 1 = [], m=3 = (1, (2, (3, []))) By basis step of append: m = 3 2 = (a) Calculate removeTail( append( (2, (3, [])),1)) (b) Calculate prepend( remove( (1,(2, (2, (3, [])))), 2),3) 2 2 RNA related definitions Consider the following definitions related to RNA strands: Definition Set of bases B = {A, C, U, G}. The set of RNA strands S is defined (recursively) by: Basis Step: A ESC ESUES,GES Recursive Step: If s ES and be B, then sb ES where sb is string concatenation. Definition The function malen that computes the length of RNA strands in S is defined recursively by rnalen: S+Z+ Basis Step: If be B, then rnalen(b) = 1 Recursive Step: If s ES and b E B, then rnalen(sb) = 1 + rnalen(s) Definition The function basecount that computes the number of a given base b appearing in a RNA strand s is defined recursively by basecount: Sx B+N -- i when b = b2 Basis step: If by E B, by E B, basecount(61, 62) when bu + b2 1+ basecounts, bu) when b = b2 Recursive Step: If s S, b1 B, by B, basecount(sb1, 62) basecount(s, 12) when bi #b2 Definition The function mutate: S x BS is defined recursively as: by when bu = A Basis step: If b, E B and by e B, mutate(61, 62) 161 when b17 A Smutate(s, & s, b2b2 when b = A Recursive Step: If s ES, b E B, b2 B, mutate(sb1,b2) mutate(s, 62)when b + A Linked list related definitions Definition The set of linked lists of natural numbers L is defined by: Basis Step: Recursive Step: If 1 L and n N, then (n,1) EL l] EL Definition The function remove Tail: L + L that removes the last node of a linked list (if it exists) is defined by: remove Tail: LL Basis Step: remove Tail(l) = 11 Recursive Step: Ifle L and n N, then remove Taill (1, 1)) = {l), when I = [] (n, removeTail(l) ), when I [] : Definition The function remove : L XN L that removes a single node containing a given value (if present) from a linked list is defined by: remove: L XN + L Basis Step: If me N then remove([], m) = 0 11 Recursive Step: If I EL,NEN, m N, then remove((n, l), m) when n=m (n, remove(l, m)) when n #m Definition: The function prepend : L x NL that adds an element at the front of a linked list is defined by: prepend(1, n) = (n,1) Definition The function append : L x NL that adds an element at the end of a linked list is defined by: append: L XN L Basis Step: If m E N then append(), m) = (m, (1) Recursive Step: Ifle L and n e N and m N, then append(n,1), m) (n, append(1, m)) (Graded for correctness) Calculate the following function applications. Include all intermediate steps, with justifications. 1 Sample response that can be used as reference for the detail expected in your answer for this part: Calculating append( (1, 2, [])) ,3), we have append( (1,(2, [])) ,3) = (1, append( (2, []) ,3)) By recursive step of append: n=1, 1 = (2, []), m = 3 = (1, (2, append( [] ,3))) By recursive step of append: n = 2, 1 = [], m=3 = (1, (2, (3, []))) By basis step of append: m = 3 2 = (a) Calculate removeTail( append( (2, (3, [])),1)) (b) Calculate prepend( remove( (1,(2, (2, (3, [])))), 2),3) 2 2 RNA related definitions Consider the following definitions related to RNA strands: Definition Set of bases B = {A, C, U, G}. The set of RNA strands S is defined (recursively) by: Basis Step: A ESC ESUES,GES Recursive Step: If s ES and be B, then sb ES where sb is string concatenation. Definition The function malen that computes the length of RNA strands in S is defined recursively by rnalen: S+Z+ Basis Step: If be B, then rnalen(b) = 1 Recursive Step: If s ES and b E B, then rnalen(sb) = 1 + rnalen(s) Definition The function basecount that computes the number of a given base b appearing in a RNA strand s is defined recursively by basecount: Sx B+N -- i when b = b2 Basis step: If by E B, by E B, basecount(61, 62) when bu + b2 1+ basecounts, bu) when b = b2 Recursive Step: If s S, b1 B, by B, basecount(sb1, 62) basecount(s, 12) when bi #b2 Definition The function mutate: S x BS is defined recursively as: by when bu = A Basis step: If b, E B and by e B, mutate(61, 62) 161 when b17 A Smutate(s, & s, b2b2 when b = A Recursive Step: If s ES, b E B, b2 B, mutate(sb1,b2) mutate(s, 62)when b + A Linked list related definitions Definition The set of linked lists of natural numbers L is defined by: Basis Step: Recursive Step: If 1 L and n N, then (n,1) EL l] EL Definition The function remove Tail: L + L that removes the last node of a linked list (if it exists) is defined by: remove Tail: LL Basis Step: remove Tail(l) = 11 Recursive Step: Ifle L and n N, then remove Taill (1, 1)) = {l), when I = [] (n, removeTail(l) ), when I [] : Definition The function remove : L XN L that removes a single node containing a given value (if present) from a linked list is defined by: remove: L XN + L Basis Step: If me N then remove([], m) = 0 11 Recursive Step: If I EL,NEN, m N, then remove((n, l), m) when n=m (n, remove(l, m)) when n #m Definition: The function prepend : L x NL that adds an element at the front of a linked list is defined by: prepend(1, n) = (n,1) Definition The function append : L x NL that adds an element at the end of a linked list is defined by: append: L XN L Basis Step: If m E N then append(), m) = (m, (1) Recursive Step: Ifle L and n e N and m N, then append(n,1), m) (n, append(1, m))
