write an iterator class (FibonnaciNumberIterator) which allows to iterate over the Fibonnacci numbers (possibly infinitely many …). Fibonacci numbers fib(n) for n=1,2

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Task 1: Iterators & Generators – Fibonacci Numbers (20 Points)

First, write an iterator class (FibonnaciNumberIterator) which allows to iterate over the Fibonnacci numbers (possibly infinitely many …). Fibonacci numbers fib(n) for n=1,2, … are defined as follows: fib(1)=fib(2)=1, fib(n)=fib(n-1)+fib(n-2), for n greater or equal to 3.

Second, write a generator class (FibonacciNumberGenerator) which generates (also possibly infinitely many) Fibonnaci numbers.

Write unit tests for both the iterator and the generator implementations, testing the Fibonnacci numbers for n=1,2,…,10. The tests should, of course, finish in finite time. The tests should assess all methods of the two classes, and should of course test for the correctness of the implementation.

 

Task 2: Recursion & Decorators (20 Points)

First provide a recursive implementation of a function which returns the nth fibonnacci number. This function should be named fib, then fib(1) should return 1, fib(2) should return 1, fib(3) should return 2, and so on (see the definition of the Fibonnaci numbers in Task 1).

Then, implement a decorator function trace (hint: a “higher order function”) which takes a function fun as an argument, calls the function, and both prints the arguments the function fun is called with as well as the value that function fun returns. To make the output more readable, add indentation levels to (recursive) function calls, such that an indented “|-- “ is printed for each recursive call, while increasing the “indentation depth” level by level of the recursion. As a test, use your decorator function, for tracing the function fib.

Then, as an example, fib(5) would result in something like the following output:

|--  fib  5

|     |-- fib 4

|     |     |--  fib  3

|     |     |    |--  fib  2

|     |     |    |    |--  return  1

|     |     |    |--  fib  1

|     |     |    |    |--  return  1

|     |     |    |--  return  2

|     |     |--  fib  2

|     |     |    |--  return  1

|     |     |--  return  3

|     |-- fib 3

|     |     |--  fib  2

|     |     |    |--  return  1

|     |     |--  fib  1

|     |     |    |--  return  1

|     |     |--  return  2

|     |--  return  5 5

In the file that you submit, provide some example output, calling the decorated function fib with exemplary input, e.g. using fib(5) for producing output similar to that shown above.

 

Task 3: OOP Design: Graphs and a simple Graph Generator (20 Points)

A graph generator is a program for generating random graphs (also known as random networks, or social networks) according to some models. A graph consists of nodes and edges. Edges can be undirected and directed. Implement the specific classes in good object-oriented fashion.

A simple strategy for generating graphs is the Erdos-Renyi model. In the Erdos-Renyi model, the number of nodes n is specified, in addition to an edge probability p. Then, in the graph generation, each of all possible edges in the graph are chosen with probability p. Implement a Erdos-Renyi generation strategy using the Strategy Pattern for directed and undirected graphs (each), with a generate method. Provide unit tests for the classes (instantiation), and graph generation, where you test for typical cases and difficult border cases.

For the implementation, you are not allowed to use any graph-/network-specific packages like NetworkX, etc. Numpy and SciPy are allowed.

 

 

Task 4: Optimization – Graph Generation (20 Points)

Another model for graph generation is the Barabasi-Albert model: Here, the network begins with an initial connected network of m’ nodes (initially 1). Then, new nodes are added to the network one at a time, until a maximum number of nodes max_nodes is reached. Each new node is connected to m <= m’ nodes with a probability proportional to the number of links that the existing nodes already have, i.e.

for each node i with a probability p_i as follows:

where k_i is the degree of node i, and the denominator sums over all the pre-existing nodes j. The degree of a node is the number of connections (edges) it has so far.

 

Implement a Graph-Generator according to the model above which returns the generated graph using the generate method, i.e. implement this in an OOP design using the Strategy Pattern. Optimize your graph generator in at least two different methodological ways (e.g. using functional programming and Numba), and test the impact (using the timeit function). Document that in your IPython Notebook. Provide unit tests for the graph generation, where you test for typical cases and difficult border cases.

For the implementation, you are not allowed to use any graph-/network-specific packages like NetworkX, etc. Numpy and SciPy are allowed.

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of