Programming Languages and Paradigms Assignment

Please answer all questions:

Question 1: This is a classic example of a higher-order function in action. Newton's method can be used to generate approximate solutions to the equation f(x) = 0 where f is a differentiable real-valued function of the real variable x. The idea can be summarized as follows:

Suppose that x₀ is some point which we suspect is near a solution. We can form the linear approximation l at x₀ and solve the linear equation for a new approximate solution. Let x₁ be the solution to the linear approximation l(x) = f(x₀) + f'(x₀)(x - x₀) = 0. In other words,

f(x₀) + f'(x₀)(x₁ - x₀) = 0

x₁ - x₀ =   - (f(x₀)/f'(x₀))

x₁ = x₀ - (f(x₀)- f'(x₀))

If our first guess x₀ was a good one, then the approximate solution x₁ should be an even better approximation to the solution of f(x) = 0. Once we have x₁, we can repeat the process to obtain x₂, etc. In fact, we can repeat this process indefinitely: if, after n steps, we have an approximate solution x_n, then the next step is

x_n+1 = x_n - (f(x_n)/f'(x_n)).

This will produce approximate solutions to any degree of accuracy provided we have started with a good guess x₀. If we have reached a x_n such that |f(x_n)| < t, where t is some real number representing the tolerance, we will stop.

Implement a function called Newton with the type shown below

val newton : f:(float -> float) * guess:float * tol:float * dx:float -> float

Question 2: In this question you will implement one-variable polynomials as lists. Use the following type definitions and exception declaration

type term = Term of float * int

type poly = Poly of (float * int) list

exception EmptyList

Question 3: In this exercise you will work with expression trees very similar to the ones discussed in class and you will implement a little interpreter for them. The main difference is that you will implement your own lookup and insert functions to keep track of bindings and you will return option values. This could be done easily with the Map collection type but I want you to get the idea of how one handles situations where the item you are looking for is not present. Thus we will use lists and raw pattern matching and explicit insertions of Some and None.

Define a function lookup, to lookup values in the binding list. If the name occurs more than once it must find the latest value inserted. We never remove values from the binding list. The binding list must be kept sorted by the name of the variable. You can use the < operator on strings but you need to give a type annotation to tell the system that you are using it on strings. Your lookup function should use options to deal with values that are not present.

Define a function insert to insert a new binding in the right place in the binding list.

Define a function eval which evaluates expressions and returns options.

Question 4: This question involves the Map collection library. Please read documentation on this collection from the web. We are going to model a couple of weeks of the English Premier League Football Season.

Question 5: In this question we will implement some (very) simple graph algorithms: we will be given a road map and we will look for paths between cities. We are given the map as a list of pairs. The first item in each pair is the name of a city and the second item is a set of cities; these are the cities directly connected to the first city.

We use the following type definitions and raw data

Write the code for the function make RoadMap.

Finally, write a function that takes the number of steps as a parameter and finds which cities are up to that number of steps away.

Question 6: Annoying question; it will teach you patience and attention to detail. Write a program to display a polynomial on the screen in the manner that we are used to. This means that if the coefficient is 1:0 we don't write it, if the exponent is 0 we omit it, the terms are ordered by decreasing degree and zero terms are not displayed except in the special case of the zero polynomial.

Question 7: This one is for ambitious students interested in the theory of algorithms. It is hard; I was not able to do it, but in the past 26 years that I have taught at McGill 3 people have done it. Come up with the best (i.e. fewest comparisons) algorithm that you can to find the largest and the second largest numbers in a set of n numbers. There is an algorithm that can do it with n+log2 n 2 comparisons. The real challenge: prove that this is the best possible.

Attachment:- Assignment Files.rar