Problem 3

Please write code in OCAML

Starter Code:

let rec sum_top_k (k : int) (xs : int list) : int =

let fib_k_step (k : int) (n : int) : int =

Problem 3. The Fibonacci k-step numbers are a generalization of the Fibonacci and Tetranacci sequences, where Fi = 0 for i 3: F; = F:-1 +F;-2 +...+ Fi-k, i.e. F; is the sum of the k previous numbers in the sequence. You will implement an OCaml function fib_k_step : int -> int -> int for computing these numbers efficiently. (a) Implement an OCaml function sum_top_k: int -> int list -> int, which ac- cepts an integer k along with a list of integers, and sums up the first k elements of the list. If the list has length less than k, simply sum all the elements in the list (assume that an empty list evaluates to a sum of 0). (b) Implement an OCaml function fib_k_step : int -> int -> int, which accepts two integers n and k and, for a fixed k, computes in time linear in n the nth Fibonacci k-step number. 2 Problem 3. The Fibonacci k-step numbers are a generalization of the Fibonacci and Tetranacci sequences, where Fi = 0 for i 3: F; = F:-1 +F;-2 +...+ Fi-k, i.e. F; is the sum of the k previous numbers in the sequence. You will implement an OCaml function fib_k_step : int -> int -> int for computing these numbers efficiently. (a) Implement an OCaml function sum_top_k: int -> int list -> int, which ac- cepts an integer k along with a list of integers, and sums up the first k elements of the list. If the list has length less than k, simply sum all the elements in the list (assume that an empty list evaluates to a sum of 0). (b) Implement an OCaml function fib_k_step : int -> int -> int, which accepts two integers n and k and, for a fixed k, computes in time linear in n the nth Fibonacci k-step number. 2