[SOLVED] Linear Data Structures & Algorithms Assignment 2-ALGORITHMS

ASSIGNMENT 2: ALGORITHMS

IMPORTANT NOTE: The exercises proposed in this assignment are related to the exercises studied in the lectures. I strongly recommended you download, get to understand, run and debug the code examples of the lectures before starting to attempt the exercises in the assignment.

BACKGROUND.

In this assignment we are going to implement divide&conquer (mandatory to use recursion) and greedy-based algorithms for solving different problems.

ASSIGNMENT 2 – PART 1 (Week 8)

Divide and Conquer: First set of exercises

BACKGROUND.

The unit on Canvas contains the following files:

• –  MyMain.java: This class tests the functionality of the divide&conquer implementation.
• –  MyList.java, MyStaticList.java, MyNode.java, MyDynamicList.java: These classes define for the package MyList<T> which we have seen previously in the lectures of the Block II: Data

  Structures.

• –  DivideAndConquerAlgorithms.java: This class contains the proposed divide&Conquer functions

  you have to implement.

  EXERCISE.

  Implement the following functions of the class DivideAndConquerAlgorithms.java.

  1. public int maxInt(MyList<Integer> m);

     This function returns the maximum item of m (-1 if m is empty).

  2. public boolean isReverse(MyList<Integer> m);

     This function returns whether m is sorted in decreasing order or not.

  3. public int getNumAppearances(MyList<Integer> m, int n);

     This function returns the amount of times that the integer n appears in m.

  4. public int power(int n, int m);

     The function returns n^m.

  5. public int lucas(int n);

     Mathematically, the Lucas series is defined as:

     Thus, the Lucas series is as follows:
     2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123 …………..

     The function returns the n-est item of the lucas series. Examples: lucas(0) ->2, lucas(4) ->7

  6. public void drawImage(int n);

     This function prints a pattern of ‘*’ for a given length.

ASSIGNMENT 2 – PART 2 (Week 9)

Divide and Conquer: Second set of exercises

BACKGROUND.

The unit on Canvas contains the following files:

• –  MyMain.java: This class tests the functionality of the divide&conquer implementation.
• –  MyList.java, MyStaticList.java, MyNode.java, MyDynamicList.java: These classes define for the package MyList<T> which we have seen previously in the lectures of the Block II: Data

  Structures.

• –  DivideAndConquerAlgorithms.java: This class contains the proposed divide&Conquer functions

  you have to implement.

  EXERCISE.

  Implement the following functions of the class DivideAndConquerAlgorithms.java.

1. public void recursiveDisplayElements(MyList<Integer> m);
Given a MyList, this recursive algorithm displays its elements by screen (if any).

2. public MyList<Integer> smallerMyList(MyList<Integer> m, int e);

The function filters all elements of MyList being smaller than ‘e’.

3. public MyList<Integer> biggerEqualMyList(MyList<Integer> m, int e);

The function filters all elements of MyList being bigger or equal than ‘e’.

4. public MyList<Integer> concatenate(MyList<Integer> m1, MyList<Integer> m2);

The function computes a new lists whose content is the concatenation of m1 and m2.

ASSIGNMENT 2 – PART 3 (Week 10)

Greedy algorithms.

BACKGROUND.

The change-making problem addresses the question of finding the minimum number of coins that add up to a given amount of money. It is a knapsack type problem and has applications wider than just currency.
Greedy algorithms determine minimum number of coins to give while making change. Note that there is no limit on how many coins can be returned from each type of coin. These are the steps a human would take to emulate a greedy algorithm to represent 36 cents using only coins with values {1, 5, 10, 20}:

The unit on Canvas contains the following files:

• –  MyMain.java: This class tests the functionality of the greedy changemaking implementation.
• –  MyList.java, MyStaticList.java, MyNode.java, MyDynamicList.java: These classes define for the package MyList<T> which we have seen previously in the lectures of the Block II: Data

  Structures.

• –  ChangeMaking.java: This class contains the proposed Greedy algorithm that you have to

  implement. The algorithm solves the problem of change making described above.

  EXERCISE.

  Implement the functions of the class ChangeMakingJava.java according to the schema of greedy algorithms studied in the lectures.

  1. selectionFunctionFirstCandidate:

  Basic policy: Just pick the first non-discarded type of coin.

  2. selectionFunctionBestCandidate:
  More elaborated policy: Pick the biggest non-discarded type of coin.

3. feasibilityTest

Given a current solution and a selected candidate, this function states whether the candidate

must be added to the solution or discarded

4. solutionTest

Given a current solution, this function states whether it is a final solution or it can still be

improved

5. objectiveFunction

This function computes how many coins are used in the solution
6. solve: This function calls to the above functions in order to solve the problem. The selection

function executed is selectionFunctionFirstCandidate if typeSelectFunc=1. Instead, if typeSelectFunc=2, selectionFunctionBestCandidate is the selected function.

This function is responsible for printing on the screen the output of the problem (see Figure above as example of output) and must include the:

• Accuracy, which is the difference of amount of change provided minus the target amount of money (input of the function).
• Coins that are provided as change.
• Number of coins provided as change.