Ass1

CSI323 Algorithms

Assignment #1

Tuesday 13 October 2015 Due: Friday 23 October 2015: 7am

Question 1 Implement the following class. The class has two instance variables num for the fraction numerator and den for the fraction denominator.

eepublic class Fraction implements Comparable public public public public

Fraction(int num, int den) // initialize instance variables int den() // returns the denominator int num() // returns the numerator Fraction mediant(Fraction that, int n) // returns the median fraction of // this and that fraction public boolean equals(Object that) // overrides the equals method public String toString() // returns the fraction as a string “num/den”

𝑎

𝑐

𝑎+𝑐

The mediant of two fractions 𝑏 and 𝑑, given an integer 𝑛 is the fraction 𝑏+𝑑 only if 𝑏 + 𝑑 ≤ 𝑛.

Question 2 0 1

Farey fractions of level 1 are defined as the sequence 𝐹1 = (1 , 1). The level 2 Farey fractions are 𝐹2 = 0 1 1

0 1 1 2 1

(1 , 2 , 1). The level 3 Farey fractions are 𝐹3 = (1 , 3 , 2 , 3 , 1). The level 4 Farey fractions are 𝐹4 = 0 1 1 1 2 3 1

(1 , 4 , 3 , 2 , 3 , 4 1). To create a level 𝑛 Farey sequence, we add a mediant fraction between every two fractions in level 𝑛 − 1 using the new level as the integer 𝑛. Your task is to implement a doubly linked list to represent a Farey sequence of fractions at a specified level. The skeleton of the Java program is given below.

public class Farey { private Node first; private int level; public Farey() {

// initialize to level 1 and add the two fractions of // level 1 to the list pointed to by first } public void increaseLevel() {

// increase level by 1 and add the necessary fractions to // list pointed to by head as per the operation; update level } public void changeLevel(int newLevel) {

// if newLevel is less than the current level do nothing // if newLevel is equal to current level do nothing // if newLevel is greater than current level, change to // that level after adding all necessary fractions } public String toString() {

// return a string with all the fractions in the list as // follows: // level: a/b, c/d, e/f, ... // for example, for level 1, you will return the string // "1: 0/1, 1/1" } public int size() {

// return the number of fractions in the list }

// we use a private Node class private class Node { private Fraction data; private Node next; ` private Node prev; } }

Question 3 Use your program from Question 2 to print to a file the following information for as large 𝑛 as you can. Level

Number of Fractions

1 2 ...

2 3

𝟑𝒏𝟐 𝝅𝟐

0.304 1.216

Plot the results on a single graph. What can be said about the relation between the number of fractions at level 𝑛 and

3𝑛2 𝜋2

?

Question 4 𝑁−1 𝑁−1 a) Evaluate ∑𝑁−1 𝑖=0 ∑𝑗=𝑖+1 ∑𝑘=𝑗+1 1. b) How much memory (altogether) does a Farey object use if it contains Farey fractions for level 𝑛 ? Assume the number of fractions at level 𝑛 is 𝐹𝑛 . Show how you worked it out. c) Exercise 1.4.6 (b) d) Exercise 1.4.8.

What to submit: a) Eclipse project for the first two questions and another for Question 4 (d) b) Typed solutions for the other questions including the graph from Question 3.