15-121 FALL 2020 [Reid-Miller]

HOMEWORK 5 - Part I and checkpoint due Monday, October 5 by 11:55PM
Completed PROGRAM due Monday, 12 October by 11:55 pm

PART I (8 pts)

For each of the following problems, write up your answers in a plain text (ASCII) file with at most 80 characters per line. Do not use Word (.doc or docx) or Rich Text Format (.rtf). At the top of the file put your name, andrew id, and time you spent to complete both the problems and programming parts. Put this file in the project folder Homework5 you will create in Part II of this assignment.

  1. (1 pt) Assume that strings s1 and s2 have n characters each, where n ≤ 0.
    1. What is the worst-case runtime complexity of the following operation in big-O notation in terms of n? Explain your answer.
          System.out.println(s1.equals(s2));
          
    2. What is the best-case runtime complexity of of the following operation in big-O notation in terms of n? Explain your answer.
          System.out.println(s1.equals(s2));
         
  2. (2 pts) What is the runtime complexity of the following code fragments in Big-O notation as functions of m and/or n? Explain each answer. (Your answers should represent the tightest/closest function for the code given.)

    1. int sum = 0;
      for (int i = 1; i <= n; i+=2)
          for (int j = 1; j <= n; j+=3)
              sum += (i+j);
        
    2. int sum = 0;
      for (int i = 1; i <= 5; i++)
          for (int j = 1; j <= n; j++)
              sum += (i+j);
      

    3. int sum = 0;
      for (int i = 1; i <= m; i*=2)
          for (int j = 1; j <= n; j++)
              sum += (i+j);
      

    4. int sum1 = 0;
      for (int i = 1; i <= n; i++)
          sum1 += i;
      int sum2 = 0;
      for (int j = 1; j <= n*n; j++)
          sum2 += j;
      

  3. (1 pt) Consider the following Java method that returns true if an array of n integers has two adjacent values that are the same, false otherwise:

    public static boolean hasAdjacentDuplicates(int[] a) {
        for (int i = 0; i < a.length-1; i++)
            if (a[i] == a[i+1])
                return true;
        return false;
    }
    

    1. What is the runtime complexity of this method using Big-O notation in the worst case? Explain your answer.

    2. What is the runtime complexity of this method using Big-O notation in the best case? Explain your answer.

  4. (1.5 pts)

    1. Suppose an algorithm processes n data elements using exactly n2 operations. If we double the number data elements, the number of operations needed will increase by a factor of what?

    2. Suppose an algorithm processes n data elements using exactly n3 operations. If we double the number data elements, the number of operations needed will increase by a factor of what?

    3. Suppose an algorithm processes n data elements using exactly log2n operations. If we double the number data elements, the number of operations needed will increase by how much?

  5. (1.5 pts) Given an array of integers in increasing order, and given a target sum, we wish to determine if the array contains two integers that can be added together to make that sum.

    1. What is the worst-case runtime complexity (in Big-O notation) of the following solution if the length of the array is n? Briefly explain your answer.

      public static boolean sumInArray(int[] a, int sum) {
      	//finds sum of all pairs in the array
      	for (int i = 1; i < a.length; i++)
      	        for (int j = 0; j < i; j++)
      	                if (a[i] + a[j] == sum)
      	                        return true;
      	return false;
      }
      

    2. Describe an algorithm (or give computer code) that performs better asymptotically than the algorithm above. Determine the worst-case runtime complexity of your algorithm.

  6. (3 pts) Given n data values, an algorithm processes these n data values with a running time given by the equation T(n) = 7n2 + 6n + 8.

    1. Show that T(n) = O(n2).

    2. Is T(n) = O(n3)? Explain.

    3. Is T(n) = O(n)? Explain.

PROGRAMMING PROJECT (10 points)

Card images from http://www.jfitz.com/cards/

In this assignment, you will complete a program to play the game Aces Up.

Game Rules

The goal is to discard as many cards from four piles as possible, leaving only Aces at the end.

A standard 52-card deck is shuffled and the four cards are dealt face-up to create four one-card piles. On each turn, the player can discard a card, move a card or deal four cards.

DISCARD: The top card on a pile can be discarded if there is another face-up card of the same suit that has a higher rank. (Ranks, from low to high, are 2,3,4,5,6,7,8,9,10,J,Q,K,A.) Whenever a card is discarded, the player earns points based on the rank of the card. Number cards are worth their value in points (e.g. a 9 of Hearts is worth 9 points). Jacks are worth 11 points, Queens are worth 12 points, andn Kings are worth 13 points. Aces are not worth any points since they cannot be discarded in this game.

MOVE: The top card on a pile can be moved to any empty pile.

DEAL 4: If a player chooses to deal four more cards from the deck, either by choice or because no cards can be discarded or moved, one card is placed face-up on the top of each pile (including any empty piles). Note that at any time, you can only see the top card on each non-empty pile.

The game ends when all cards have been discarded except the Aces or when no further play is possible.

Assignment

Download a copy of the AcesUp.zip project file.

Complete the supplied Java program to play a correct game of Aces Up.

The file contains four classes:

Programming Requirements

In the GameController class, you must use an ArrayList to store a standard deck of 52 playing cards. Use generics for this list with a type of PlayingCard as its base type. Use ArrayLists for each of the four piles of cards and for the discard pile as well. You can shuffle the deck of cards by using the Collections.shuffle method. Its parameter should be a reference to the array list that holds your deck of cards. When you move a card from one list to another, do this in the most efficient manner possible. You may add additional private helper methods as you wish to simplify and organize your program code.

Implementation Note: The GUI has a button for DISCARD and MOVE for each pile and a button to DEAL 4 more cards. If any of these operations are invalid for the current state of the game, nothing should change in the game. Clicking NEW GAME always starts a new game.

DO NOT CHANGE ANY CODE ALREADY GIVEN TO YOU. YOUR ADDITIONAL CODE SHOULD WORK WITH THE CODE PROVIDED TO YOU.

Debugging/Testing

In your code, you must print the current cards in the deck and the four piles to the console window after each play is made. This will be helpful to you and to the TA for testing purposes.

Eclipse vs. Command-Line execution - Card images

The project you downloaded contains a folder named images that contains pictures of all of the playing cards used in the game. If you use Eclipse to run this project, the folder is in its correct place (the top level of the project). If you use the command-line to compile and run the program, move this folder to the src folder where the Java source code is.

Documentation & Style

Write comments to match the Javadoc comments given above (as best as you can). Add additional comments in your methods to explain your code where necessary. Use appropriate variable names for self-documentation and indent properly.

PIAZZA

You can use Piazza to ask general questions about the assignment or about Java for the course staff or for other students to answer. Please make your questions public so the course staff only need answer the question once. If your question is of general interest, we reserve the right to make it public, after anonymizing your name. You should, however, treat Piazza with the same academic integrity policies outlined above and in the academic integrity policy statement on the course website. If your question may reveal a solution to a problem make your question private. Please use appropriate etiquette when writing to Piazza.

Submitting your work

When you have completed this assignment and tested your code thoroughly, create a .zip (archive or compress) file of your Homework3 folder. Autolab only accepts .zip files. (To create a .zip file, right-click (or -click on a Mac or press-and-hold on Windows) on your project folder (containing both your written .txt file and code) and choose "compress" or "archive", making sure to choose ".zip".) Submit your .zip file to autolab. Verify on autolab that your submission contains both your text file with answers to Part I and Encryptor.java.

Make sure to keep a copy of your work just in case!