NUIMCrest CS210 - Algorithms and Data Structures I
Department of Computer Science, NUIM
Self-help Exercises (Basic Programming)

T Naughton, NUIM
Back to CS210 home


Self-help Exercises

These 90 or so exercises are designed to help students improve their basic Java programming skills. They are designed for those students taking my CS210 course who feel they need some more practice at introductory-level programming problems. They range from very easy (Exercise 1) to a little challenging (last few questions of each section). The increase in difficulty from one question to the next is sufficiently small that you should (I hope) not get stuck on any question if you can answer all those that come before. Solutions are provided for selected exercises.

If these exercises pose no great problems for you, you are ready to commence CS210.

Many thanks to those who have helped me with this project: Alison Shortt, Leo Mulhare.


Exercises:
Section I: Branching and functions [I.1]  [I.2]  [I.3]  [I.4]  [I.6]  [I.7]  [I.8]LM  [I.9]AS  [I.11]AS  [I.12]AS  [I.13]AS  [I.14]AS  [I.16]LM  [I.17]LM 
Section II: Iteration and arrays [II.1]  [II.2]AS  [II.3]AS  [II.4]LM  [II.6]  [II.7]  [II.8]AS  [II.9]AS  [II.11]  [II.12]  [II.13]  [II.14]  [II.16]  [II.17]  [II.18]  [II.19]  [II.21]  [II.22]  [II.23]  [II.24]  [II.26]LM  [II.27]  [II.28]  [II.29]  [II.31]LM  [II.32]LM 
Section III: Nested loops [III.1]  [III.2]  [III.3]  [III.4]  [III.6]  [III.7]  [III.8]  [III.9]  [III.11]  [III.12]  [III.13]  [III.14] 
Section IV: Dynamically allocating static arrays [IV.1]  [IV.2]  [IV.3]  [IV.4]  [IV.6]  [IV.7]  [IV.8]  [IV.9]  [IV.11] 
Section V: Stepwise refinement [V.1]  [V.2]  [V.3]  [V.4]  [V.6]  [V.7] 
Section VI: More arrays and iteration [VI.1]  [VI.2]  [VI.3]  [VI.4]  [VI.6]  [VI.7]  [VI.8]  [VI.9]AS  [VI.11]AS  [VI.12]  [VI.13]  [VI.14]  [VI.16]  [VI.17]  [VI.18]LM 
Section VII: Recursion [VII.1]  [VII.2]  [VII.3]  [VII.6]LM 
Section VIII: Objects [VIII.1]  [VIII.2]  [VIII.4]LM  [VIII.6]  [VIII.7]  [VIII.8]LM  [VIII.11] 


Section I: Branching and functions

Exercise I.1. Write a program that prints "Hello world" to the screen. [Java solution]

Exercise I.2. Write a program that declares two integers, adds them together, and prints out the result. [Java solution]

Exercise I.3. Write a program that declares two doubles, calls a user-defined method called add() to add them together, and prints out the result. Method add() will be a function that takes two doubles as arguments and returns the sum. [Java solution]

Exercise I.4. Write a program that declares two ints, calls a user-defined function called larger() to return the larger of the two, and prints out the result. [Java solution]

Exercise I.6. Write a program that declares three doubles, calls a user-defined function called smallest() to return the smallest of the three, and prints out the result.

Exercise I.7. Write a program that initialises two integer variables a and b to values 5 and 6, repectively, and prints them out. The program then swaps the values in the variables and prints the variables out again.

Exercise I.8. Write a function that takes an integer as an argument and, using a switch statement, prints the appropriate string of "one", "two", ... ,"ten", or "greater than ten".

Exercise I.9. During a special sale at a store, a 10% discount is taken on purchases over £10.00. Write a function that takes the amount of purchases as an argument and calculates the discounted price. The purchase amount will be specified in pence (as an integer). Use integer arithmetic throughout the function.

Exercise I.11. Write a function that takes two arguments: a birth year encoded as two digits (such as "62") and the current year, also encoded as two digits (such as "99"). The function must correctly print out the users age in years. Two sample runs of the function are shown below.

Year of Birth: 62
Current year: 99
Your age: 37

... and...

Year of Birth: 62
Current year: 00
Your age: 38

Exercise I.12. A petrol station sits on Route 190 on the edge of Death Valley. There is no other petrol station for 200 miles. You are to write a function to help drivers decide if they need petrol. The function takes as arguments:

  • The capacity of the petrol tank, in gallons
  • The indication of the petrol gauge in percent (full = 100, three quarters full = 75, and so on)
  • The miles per gallon of the car.
    The function then prints out "Get Petrol" or "Safe to Proceed" depending on whether or not the car can cross the 200 miles with the gas currently in the tank. A sample run of the function is shown.

    Tank capacity: 12
    Gage reading: 50
    Miles per gallon: 30
    Get Petrol!

    Exercise I.13. Different packages of ground beef have different percentages of fat and different costs per pound. Write a function that takes as arguments:

  • The price per pound of package "A"
  • The percent lean in package "A"
  • The price per pound of package "B"
  • The percent lean in package "B"
    The function then calculates the cost per pound of lean (non-fat) beef for each package and prints out which (if either) is the better value. A sample run of the function is shown.

    Price per pound package A: 2.89
    Percent lean package A: 85
    Price per pound package B: 3.49
    Percent lean package B: 93

    Package A cost per pound of lean: 3.4
    Package B cost per pound of lean: 3.752688
    Package A is the better value

    Exercise I.14. Bob's Discount Bolts charges the following prices:

  • 5 pence per bolt
  • 3 pence per nut
  • 1 pence per washer
    Write a function that takes as arguments the number of bolts, nuts, and washers in a customer's purchase and then calculates and prints out the total. As an added feature, the function checks the order. It is usually a mistake if there are more bolts than nuts. In this case the function prints out "Check the Order." Otherwise the function prints out "Order is OK." In either case the total price is written out. Use constants (final ints) for the unit cost of each item. A sample run of the function is shown.

    Number of bolts: 12
    Number of nuts: 8
    Number of washers: 24

    Check the Order
    Total cost: 108

    Exercise I.16. Write a function that takes an integer as an argument and prints out whether or not its square root is also an integer.

    Exercise I.17. Write a function that performs simple calculations that are specified by the user. The function will take two real numbers and a character as arguments. The character will be one of the following operators: '+', '-', '*', '/'. The function should calculate and return the appropriate result of applying the operator to the two reals.


    Section II: Iteration and arrays

    Exercise II.1. Write a function that takes a number n as an argument and writes out n rows of asterisks to the screen as shown below. This sample output of the function occurs when n has the value 4.

    *
    *
    *
    *

    Exercise II.2. Write a function that adds up the squares and adds up the cubes of integers from 1 to n, where upper limit n is passed as an argument. Your function should only contain one loop only. A sample run is shown.

    Upper Limit: 5
    The sum of Squares is: 55
    The sum of Cubes is: 225

    Exercise II.3. Write a function that computes xn where x is a floating point number and n is a positive integer. The function should check that n is positive. A loop must be used (recall, for example, x3 = x * x * x) as opposed to Math functions. Two sample runs are shown.

    x is 1.3, n is 5
    1.3 raised to the power 5 is: 3.71293

    ... and...

    x is 5.6, n is -3
    n must be a positive integer

    Exercise II.4. Write a function that returns the factorial of its integer argument. The function should use a loop for the calculation.

    Exercise II.6. Write a function that takes an array of integers as an argument and prints out the contents of the array. Your function should have the following format. [Java solution]

    public static void example(int list[]) {
      /* This function prints out the contents of list[].
     */

      // Your code here
    }

    Exercise II.7. Write a function that takes an array of integers as an argument and prints out the contents of the array in reverse.

    Exercise II.8. Write a function that takes a word stored in a character array (an array of type char) as an argument and repeatedly prints the word as many times as it has characters. Assume that the array has the same length as the length of the word. A sample run is shown.

    Word is "Hello"

    Hello
    Hello
    Hello
    Hello
    Hello

    Exercise II.9. As part of a program to print an index for a book, a function is required to print each line. The function takes two words stored in character arrays and the width of a page n as arguments and prints out both words on a single line. The words will be separated by enough dots (`.' characters) such that the total line length is n. A sample output is shown.

    First word: turtle
    Second word: 153
    Page width: 30

    turtle.....................153

    Exercise II.11. Write a function that takes an array of doubles as an argument and prints out every second element, starting with element 0.

    Exercise II.12. Write a function that takes an array of integers list[] and a positive integer n as arguments and prints out the last n elements of the array. Assume that n is always less than list.length. Your function should have the following format.

    public static void example(int list[], int n) {
      /* This function prints out the final n elements of list[].
     */

      // Your code here
    }

    Exercise II.13. Write a function that takes an array of ints as an argument and returns the largest value found in the list. If the list is empty, then return -1. Your function should have the following format.

    public static int example(int list[]) {
      /* This function returns the largest int found in list[].
      ** If the list has no elements, return -1.
      */

      // Your code here
    }

    Exercise II.14. Write a function that takes an array of integers and a positive integer n as arguments and prints out the element at index n. If index n does not exist (i.e. if the array is too small) then print an error message.

    Exercise II.16. Write a function that takes an array of integers and an integer n as arguments and returns the lowest index in the array with value n. If n is not in the list return -1.

    Exercise II.17. Write a function that takes an array of integers and an integer x as arguments and returns the highest index in the array with value x. If x is not in the list return -1.

    Exercise II.18. Write a function that takes an array of ints as an argument and returns the index of the largest value in the list. If two or more indexes have this property, return the largest index. If the list is empty, return -1. [Java solution]

    Exercise II.19. Write a function that takes an array of doubles as an argument and returns the index of the smallest value in the list. If two or more indexes have this property, return the largest index. If the list is empty, return -1.

    Exercise II.21. Write a function that takes an array of ints as an argument and returns the index of the largest value found in the list. If two or more indexes have this property, return the smallest index. If the list is empty, return -1. [Java solution]

    Exercise II.22. Write a function that takes an array of integers as an argument and prints out returns the sum of all the odd valued elements in the list.

    Exercise II.23. Write a function that takes an array of integers as an argument and returns the number of odd valued elements that are in the list.

    Exercise II.24. Write a function that takes an array of characters as an argument and returns true if there are as many `a' characters as `b' characters in the array, otherwise returns false. Ignore all other characters. Your function should have the following format.

    public static boolean example(char list[]) {
      /* This function checks if the numbers of occurances of
      ** `a's and `b's are equal. Ignore all other characters.
      */

      // Your code here
    }

    Exercise II.26. Write a function that takes an integer as an argument and returns the sum of its digits.

    Exercise II.27. Write a function that takes an array of integers as an argument and returns the same array with its contents reversed. Your function should have the following format.

    public static int [] example(int list[]) {
      /* This function reverses the list passed to it.
     */

      // Your code here
    }

    Exercise II.28. Write a function that takes an array of integers and integers x and y as arguments, replaces every instance of value x with value y, and returns the array.

    Exercise II.29. Write a function that takes an array of integers and an integer n as arguments and returns the average (as a double) of the first n integers in the list. If n is greater than the length of the array, find the average of all elements in the array.

    Exercise II.31. Write a function that takes an array of integers representing the coefficients of a polynomial in x as an argument and outputs the result of differentiating that polynomial with respect to x. The argument array will have the following format: polynomial 4x3 + 7x + 1 would be represented by an array of length 4 with elements {1, 7, 0, 4}, polynomial x would be represented by an array of length 2 with elements {1, 0}.

    Exercise II.32. Write a function that takes an array of integers representing the coefficients of a polynomial in x and an integer value for x as arguments. The function should evaluate and return the polynomial for that input x. The argument array will have the following format: polynomial 4x3 + 7x + 1 would be represented by an array of length 4 with elements {1, 7, 0, 4}, polynomial x would be represented by an array of length 2 with elements {1, 0}.


    Section III: Nested loops

    Exercise III.1. Write a function that takes a number n as an argument and writes out n rows of asterisks to the screen as shown below. This sample output of the function occurs when n has the value 4.

    ****
    ****
    ****
    ****

    Exercise III.2. Write a function that takes a number n as an argument and writes out n rows of asterisks to the screen as shown below. This sample output of the function occurs when n has the value 4.

    *
    **
    ***
    ****

    Exercise III.3. Write a function that takes a number n as an argument and writes out n rows of asterisks to the screen as shown below. This sample output of the function occurs when n has the value 4.

    ****
    ***
    **
    *

    Exercise III.4. Write a function that takes an integer n as an argument and writes out n rows of asterisks to the screen as shown below. This sample output of the function occurs when n has the value 4.

       *
      **
     ***
    ****

    Exercise III.6. Write a function that takes a number n as an argument and writes out n rows of asterisks to the screen as shown below. This sample output of the program occurs when n is 4. [Java solution]

    ****
     ***
      **
       *

    Exercise III.7. Write a function that takes a number n as an argument and writes out n rows of asterisks to the screen as shown below. This sample output of the function occurs when it is passed the number 4. [Java solution]

    * ****
    * ***
    * **
    * *

    Exercise III.8. Write a function that takes a number n as an argument and writes out n rows of text to the screen. Each row contains (nth-1) blanks followed by nth 'a' characters. Sample output of the program is shown below, when n is passed as 4. [Java solution]

    a
     aa
      aaa
       aaaa

    Exercise III.9. Write a function that takes an integer array of length n and prints out the array n times, each time starting at a new element and wrapping around to the beginning of the array (if needed) until each element has been printed out. This sample output of the function occurs when the input is the array {0, 5, 10, 12}.

    0 5 10 12
    5 10 12 0
    10 12 0 5
    12 0 5 10

    Exercise III.11. Write a function that takes an array of integers as an argument and prints out the indexes of the first two duplicate integer values found in the list. If no duplicates are found in the list, print an appropriate message. [Java solution]

    Exercise III.12. Write a function that takes an integer array as an argument and returns true if the array is a palindrome, and false if it is not. (A palindrome reads the same backwards as it does forwards: {1,2,2,1} and {21,2,21} are palindromes, {1,1,2,1} is not.) If the array is empty, return true.

    Exercise III.13. Write a function that takes an array of integers as an argument and returns the index of the first integer encountered that is the square root of any integer in the list. [Java solution]

    Exercise III.14. Write a function that takes an array of integers as an argument and returns the index of the first integer it finds that is equal in value to the addition of any two neighbouring integers in the list.


    Section IV: Dynamically allocating static arrays

    Exercise IV.1. Write a function that takes an integer array list[] and a positive integer n as arguments and returns a newly created array that only contains the last n integers of list[]. If there are no integers in list[] return an array of length zero. Your function should not change list[] and should have the following format. [Java solution]

    int [] example(int list[], int n) {
      /* This function returns a newly created array containing
      ** the last n integers from list[]. If there are no integers
      ** in list[] return an array of length 0.
      */

      // Your code here
    }

    Exercise IV.2. Write a function that takes an array of type int and a double as arguments. Using a newly created array of type double, of the same length, the function multiplies each element of the list by the double. It then prints each int-double pair before returning the new array.

    Exercise IV.3. Write a function that takes an array of type int as an argument. Using a newly created array of type double of length 2, the function stores the sum and the average of the list of integers. Finally, the function returns this array. [Java solution]

    Exercise IV.4. Write a function that takes an array of type int as an argument. Using a newly created array of type int, of the same length, the function stores half the value of each of the first array's integers. Finally, the function prints each int-int pair where a rounding error has occurred and returns the new array. [Java solution]

    Exercise IV.6. Write a function that takes an integer array list[] and an integer n as arguments and returns a newly created array that is one element larger containing n at index 0 followed by the contents of list[].

    Exercise IV.7. Write a function that takes an integer array list[] and an integer n as arguments and returns a newly created array that contains the contents of list[] with the first occurance (if any) of n removed.

    Exercise IV.8. Write a function that takes an integer array list[] sorted in increasing order and an integer n as arguments and returns a newly created array that is one element larger containing n and the contents of list[]. n must be positioned within the new array such that the sorted order is maintained.

    Exercise IV.9. Write a function that takes an integer array list[] as an argument and returns a newly created array that only contains the odd valued integers from list[]. If there are no odd integers in list[] return an array of length zero. [Java solution]

    Exercise IV.11. Write a function that takes an array of type int and an integer n as arguments and returns a newly created array containing only those values from list[] with values less than n.


    Section V: Stepwise refinement

    Exercise V.1. Write a function that takes a number n as an argument and writes out 2n rows of asterisks to the screen as shown below. This sample output of the function occurs when it is passed the number 4. [Java solution]

    ****
     ***
      **
       *
       *
      **
     ***
    ****

    Exercise V.2. Write a function that takes a number n as an argument and writes out n rows of asterisks to the screen as shown below. This sample output of the function occurs when it is passed the number 4. [Java solution]

    ****
    *  *
    *  *
    ****

    This sample output of the function occurs when n is 5.

    *****
    *   *
    *   *
    *   *
    *****

    Exercise V.3. Write a function that takes a number n as an argument and writes out n2 rows of characters to the screen as shown below. This sample output of the function occurs when n is 2. [Java solution]

    ****
    *XX*
    *XX*
    ****

    This sample output of the function occurs when n is 3.

    *********
    *********
    *********
    ***XXX***
    ***XXX***
    ***XXX***
    *********
    *********
    *********

    Exercise V.4. Write a function that takes a number n as an argument and writes out n2 rows of characters to the screen as shown below. This sample output of the function occurs when n is 2. [Java solution]

    X**X
    *XX*
    *XX*
    X**X

    This sample output of the function occurs when n is 3.

    X*******X
    *X*****X*
    **X***X**
    ***X*X***
    ****X****
    ***X*X***
    **X***X**
    *X*****X*
    X*******X

    Exercise V.6. Write a function that takes a number n as an argument and writes out characters to the screen as shown below. This sample output of the function occurs when n is 1.

     |
    -+-
     |

    This sample output of the function occurs when n is 2.

      ||
      ||
    --++--
    --++--
      ||
      ||

    Exercise V.7. Write a function that takes a number n as an argument and writes out characters to the screen to form the octagonal shape below. This sample output of the function occurs when n is 1.

     *
    ***
     *

    This sample output of the function occurs when n is 2.

      **
     ****
    ******
    ******
     ****
      **

    This sample output of the function occurs when n is 3.

       ***
      *****
     *******
    *********
    *********
    *********
     *******
      *****
       ***



    Section VI: More arrays and iteration

    Exercise VI.1. Write a function that takes an array of integers and an integer n as arguments and returns the index of the element with the highest value that is less than n. If multiple indexes have such a property return the first encountered. If no suitable values are found then return -1. [Java solution]

    Exercise VI.2. Write a function that takes an array of integers and an integer n as arguments and returns the index of the element with the lowest value that is greater than n. If multiple indexes have such a property return the last encountered. If no suitable values are found then return an index to the first element of the list. If the list is empty return -1.

    Exercise VI.3. Write a function that takes an array of integers and an integer n as arguments and returns the index of the element in the array with a value closest to n. If multiple indexes have such a property, or if two values are equidistant ((n+2) and (n-2), for example) return the first encountered. If the list is empty return -1. [Java solution]

    Exercise VI.4. Write a function that takes an array of integers and an argument and copy each value down one index (thus removing the 0th element). Pad the last element of the array with a zero and return the array.

    Exercise VI.6. Write a function that takes an array of integers and an integer n as arguments and removes the value at that index by copying all subsequent values down one index. Pad the last element with a zero and return the array.

    Exercise VI.7. Write a function that takes an array of integers and an integer n as arguments and adds n to the front of the array, making room by copying all elements up one index. Return the element pushed off the end of the array.

    Exercise VI.8. Write a function that takes a array of integers sorted in ascending order and an integer n as arguments and adds n to the array at such a position that the increasing order is maintained. Make room by copying all elements up one index. Return the element pushed off the end of the array.

    Exercise VI.9. The Greatest Common Divisor (GCD) of 2 integers is the largest integer that evenly divides each of the two numbers. Write a function that returns the greatest common divisor of its two integer arguments.

    Exercise VI.11. An integer number is said to be a perfect number if its factors, including 1 (but not the number itself), sum to the number. For example, 6 is a perfect number because 6 = 1 + 2 + 3. Write a function that determines if its argument is a perfect number.

    Exercise VI.12. Write a function that takes an array of integers and an integer n as arguments and removes the first occurance of n in the array by copying subsequent values down one index. Pad with a zero and return the array.

    Exercise VI.13. Write a function that takes an array of integers and an integer n as arguments and removes all occurances of n in the array by copying subsequent values down one index. Pad with zeros and return the array.

    Exercise VI.14. To normalise the contents of an array means to divide each element by the maximum value in the array. Write a function that takes an array of doubles and returns the normalised array.

    Exercise VI.16. Write a function that takes an array of integers as an argument and removes the first duplicate value found in the array by copying subsequent values down one index. Pad with a zero and return the array.

    Exercise VI.17. Write a function that takes an array of integers as an argument and removes all duplicates of values found in the array by copying subsequent values down one index. Pad with zeros and return the array.

    Exercise VI.18. Write a function that takes an array of integers as an argument and prints out the value that occurs most often in the array. If there are several such different values, they should all be printed out.


    Section VII: Recursion

    Exercise VII.1. Write a recursive function that takes an integer array and prints out the contents in reverse order. [Java solution]

    Exercise VII.2. Write a recursive function that takes an integer array and prints out the contents in the order in which they appear in the array.

    Exercise VII.3. Write a recursive function that takes an integer array and and integer n as arguments and determines whether or not n is in the array.

    Exercise VII.6. Write a recursive function that returns the factorial of its integer argument.


    Section VIII: Objects

    Exercise VIII.1. Write a class that has a public integer data member and two methods isOdd() and isEven() that determine whether the integer is odd or even, respectively. The user will specify the data member's value through the constructor. Include a program to test the class. [Java solution] [Java test program]

    Exercise VIII.2. Write a class that has a private integer data member and methods isOdd() and isEven() that determine whether the integer is odd or even, respectively. The constructor will always set the data member's value to zero by default. Include setData(int newval) and getData() methods to interact with the data member. Include a program to test the class.

    Exercise VIII.4. Write a class Compass that has the attribute direction, which can represent the 4 main compass points (N,S,E,W). There should be a constructor that sets direction to North, a reset() method that also sets direction to North, a turnRight() method that sets direction to the next point clockwise, a corresponding turnLeft() method, and a getDirection() method. You should also write a program TestCompass to test your class.

    Exercise VIII.6. Write a class that stores an integer and has methods isPrime(), isGreaterThanZero(), and isGreaterThan(int testvalue).

    Exercise VIII.7. Write a class that stores a fraction as a pair of integers, one for the numerator (above the line) and one for the denominator (below the line). For example, "1/3" could be represented by integer pairs (1,3), or (2,6), and so on. Methods should include isGreaterThanOne(), multiplyBy(int value), and divideBy(int value). The class will also have a compact() method that makes both integers as small as possible while still representing the same fraction.

    Exercise VIII.8. Write a class that calculates and maintains a list of the factorials of integers from 1 to 100. It should have a public method that recursively calculates and returns the factorial of its integer argument. The class should also have a private integer array to store factorials as they are calculated. The method will check the array to avoid recalculating any previously calculated factorials.

    Exercise VIII.11. Write a class that maintains an array of integers. It will have methods size(), contains(int testvalue), countOdd(), add(int newvalue), and remove(int remvalue). The add(int newvalue) and remove(int remvalue) methods should dynamically adjust the size of the array.


    NUIM Logo