AP Computer Science A - All posts

About AP Computer Science A  |  All posts  |  Post list

Quiz 7 Sorting Algorithms Practice

  1. Sort the following array using each of the three sorting algorithms.
  2. 26   48   12   92   28   6    33

    • Selection Sort







    • Insertion Sort







    • Merge Sort








  3. Which of the following sorting algorithms is shown in the sort below? (Choose all correct answers.)

    8    73   89   20   94   83   58
    8    73   89   20   94   83   58
    8    73   89   20   94   83   58
    8    73   89   20   94   83   58
    8    73   20   89   83   94   58
    8    20   73   89   58   83   94
    8    20   58   73   83   89   94
    • Selection Sort
    • Insertion Sort
    • Merge Sort
    • None of the above


  4. Which of the following sorting algorithms is shown in the sort below? (Choose all correct answers.)

    51   11   56   83   20   26   33
    11   51   56   83   20   26   33
    11   20   56   83   51   26   33
    11   20   26   83   51   56   33
    11   20   26   33   51   56   83
    11   20   26   33   51   56   83
    11   20   26   33   51   56   83
    • Selection Sort
    • Insertion Sort
    • Merge Sort
    • None of the above


  5. Which of the following sorting algorithms is shown in the sort below? (Choose all correct answers.)

    83   5    8    12   65   72   71
    5    83   8    12   65   72   71
    5    8    83   12   65   72   71
    5    8    12   83   65   72   71
    5    8    12   65   83   72   71
    5    8    12   65   72   83   71
    5    8    12   65   71   72   83
    • Selection Sort
    • Insertion Sort
    • Merge Sort
    • None of the above


  6. What are the advantages and disadvantages of each of the following sorting algorithms?
    1. Selection Sort




    2. Insertion Sort




    3. Merge Sort




  7. Which of the following sorting algorithms should you use to sort short arrays in a memory-limited real-time application?
    • Selection Sort
    • Insertion Sort
    • Merge Sort

  8. Which of the following sorting algorithms is most efficient for sorting arrays that are already mostly in order?
    • Selection Sort
    • Insertion Sort
    • Merge Sort

  9. Which of the following sorting algorithms is most efficient for sorting large arrays with values in random order?
    • Selection Sort
    • Insertion Sort
    • Merge Sort
  10. For searching an unordered list, which search algorithm is the better choice?
  11. For searching an ordered list, which search algorithm is the better choice?
  12. In what situations would the binary search algorithm be useful?
  13. In what situations would the linear search algorithm be useful?
  14. For an array of a million element, how many elements at most would you need to check using binary search in order to determine whether a specific element is in the array?
  15. For a list of 100 elements, how many elements would you need to check using binary search in order to find out if a particular element is in the list?

 

Recursion-1

We will use what you've learned about recursion on some CodingBat problems:

  1. Go to http://codingbat.com/java
  2. Do the coding problems in Recursion-1. All 30 problems in Recursion-1 must be done by Wednesday, January 18th.

Quiz 4 Review

Quiz 4 will be on Monday, November 7th. It will cover for loops for arrays and strings as well as number representations (binary, hexadecimal, octal) and unit testing. Here are some review questions:

  • What is the hexadecimal (base-16) number that is equivalent to the binary (base-2) number 11011100?
  • (See hw2 for more example questions on binary, hexadecimal, etc.)
  • How do you test a method that does not return anything?
  • Why is unit testing beneficial?
  • Why is writing more tests better than writing just a few?
  • (Review JUnit Testing lesson slides.)
  • Multiple Choice Practice with loops
  • What is the printed output of this code?
    
    int[] arr = {3, 5, 8, 10, 3, 4, 5, 3};
    for(int i = 2; i < arr.length-2; i+=3)
    {
        arr[i] = arr[i] - i + 1;
    }
    System.out.println(arr[1] +" "+ arr[2] +" "+ arr[4] +" "+ arr[5]);
    
  • Write a method that returns an array of 30 random integers from 0 to 50.
  • Write the twoBOrNotTwoB method with a for loop to that will return whether the String has exactly two 'b' characters in it.
    
    public boolean twoBOrNotTwoB(String a) {
    
    
    }
    
  • Write the sumMod4Is3 method (with a for loop) to find and return the sum of all the values x in the given array where x mod 4 is 3. (i.e. if the remainder is 3 when dividing by 4)
    
    public int sumMod4Is3 (int[] c) {
    
    
    }
    
  • Write the squareMultiplesOf5 method (with a for loop) to modify all the values in the array that are multiples of 5 by squaring them. The method must modify the given array and return the same array. (e.g. if the array is {1,3,4,5,10}, the modified array would be {1,3,4,25,100})
    
    public int[] squareMultiplesOf5(int[] b) {
    
    
    }
    
  • Write the shortestString method (with a for loop) to find and return the length of the shortest string in a given array of Strings. (e.g. if the array is {"Halloween","Java","Testing","Number"}, the method would return 4)
    
    public int shortestString(String[] d) {
    
    
    }
    

String-2

We will use what you've learned about strings and for loops to solve some more puzzles:

  1. Go to http://codingbat.com/java
  2. Do the coding problems in String-2. All 20 problems in String-2 must be done by Thursday, October 27th.

Array-2

We will use what you've learned about arrays and for loops to solve some more puzzles:

  1. Go to http://codingbat.com/java
  2. Do the coding problems in Array-2. All 34 problems in Array-2 must be done by Wednesday, October 19th.

DragonPokemon Subclass

You will write a DragonPokemon class that is a subclass of the Pokemon superclass. Here are the things you should include in the DragonPokemon class:

  • It should be a subclass of the Pokemon superclass.
  • It should have instance variables for storing Pokemon types (note that Pokemon can have up to two types).
  • It should have multiple constructors depending on if a type is given when the object is instantiated.
  • It should have a method that prints out the Pokemon's types
  • Dragon-type Pokemon are powerful so you need to override their attack method to deal 200 damage instead of 50.
  • All Dragon-type Pokemon can use an attack called Dragon Rage. Write a new method called dragonRage that allows them to use the superclass's attack method to deal damage eight times (for a total of 400 damage) using Dragon Rage, but does not override/overload the attack method. The hit points of the other Pokemon should be printed out each time it does 50 damage. Use a for loop in this method.
  • All variables and methods in this subclass should be set to either public or private.

Once you are finished with both the Trainer class and DragonPokemon class (and you have tested both thoroughly), make sure they are pushed to GitHub.

Pokemon & OOP

Hope you enjoyed the Pokemon connection.

Code for the Pokemon class is provided on GitHub.

Now that we have created Pokemon objects, we need to create some Pokemon Trainers. Use the template for the Trainer class and implement the variables and methods specified in the comments.

Feel free to modify the test file to thoroughly test all your methods.

Logic-2

Time to solve some more logic puzzles:

  1. Go to http://codingbat.com/java
  2. Do the coding problems in Logic-2. All 9 problems in Logic-2 must be done by Wednesday, September 28th.

Magpie Chatbot Lab

For this lab, you will explore some of the basics of NLP. As you explore this, you will work with a variety of methods of the String class and practice using the if statement. You will trace a complicated method to find words in user input.

Get the MagpieLab repository via the link on Slack, which contains the Magpie Student Guide and Starter Code for each of the activities. Clone the forked repository on Codenvy and work on the lab in the Codenvy IDE. Complete each of the exercises and questions. When you are done, make sure to stage, commit, and push your changes to GitHub.

The due date for all the activites is Monday, September 26th. Here is a suggested timeline for completing the lab:

  • Activity 1 - Friday
  • Activity 2 - Tuesday
  • Activity 3 - Wednesday
  • Activity 4 - Wednesday
  • Activity 5 - Friday

String-1

We will use what you've learned about Strings to solve some logic puzzles:

  1. Go to http://codingbat.com/java
  2. Do the coding problems in String-1. All 33 problems in String-1 must be done by Thursday, September 15th.

Array-1

We will use what you've learned about arrays to solve some logic puzzles:

  1. Go to http://codingbat.com/java
  2. Do the coding problems in Array-1. All 27 problems in Array-1 must be done by Friday, September 9th.

Logic-1

We will use what you've learned about methods and if statements to solve some logic puzzles:

  1. Go to http://codingbat.com/java
  2. Click on "create account" and create an account. Make sure to put your name (last, first). This is not optional.
  3. After you have created your account, click on "prefs".
  4. In the "Share To" text box, enter my email address (tand@sfusd.edu). Click Share.
  5. Do the coding problems in Logic-1. All 30 problems in Logic-1 must be done by Friday, September 2nd.

Functions and Methods

Part 1:

We’re going to take another look at functions and do some math today. Complete this worksheet before moving on to Part 2.

Part 2:

We will now take our multi-variable functions and turn them into multi-parameter methods in Java. Clone the git repository and edit the two Java files in the project: GeometryLab.java and GeometryLabTest.java. The first Java file will have your method definitions from the worksheet. The second file will have a main method with the method invocations/calls from the worksheet and use System.out.println to print out your answers. Check your answers with the worksheet answers from Part 1.

CalendarPrinter

This program will be called CalendarPrinter for reasons that will shortly become obvious.  Start a new project CalendarPrinter and clone your git repository. Edit the main in the Java file to create a program that will produce the below output.

When compiled and executed, your program should output:

September 1
September 2
September 3 – WEEKEND
September 4 - WEEKEND
September 5 – NO SCHOOL (LABOR DAY)
September 6
September 7
September 8
September 9
September 10 – WEEKEND
September 11 – WEEKEND
September 12
September 13
September 14
September 15
September 16
September 17 – WEEKEND
September 18 – WEEKEND
September 19
September 20
September 21
September 22
September 23 - END OF THE MARKING PERIOD
September 24 – WEEKEND
September 25 – WEEKEND
September 26
September 27
September 28
September 29
September 30

Your output should match the above exactly. Observe all capitalization, punctuation, and spacing. As you might expect, there are some other requirements for writing this program. The most important of these is that you may only have one line of code that calls System.out.println (and no uses of System.out.print). Clearly, there is more than one line of printed output. Therefore, you must use a loop and you must use conditionals (if statements) in your program. You must also have at least one String variable.

Getting Started with Github

  1. Use cd to navigate in the terminal to your project folder
  2. Clone your git repository using
    git clone URL
  3. Use cd to navigate in the terminal to your cloned git repository
  4. Create a Hello.java file in your git repository with the code for the Hello class:
    
    public class Hello {
      public static void main (String[] args) {
        System.out.println("Hello world");
      }
    }
    
  5. You will use javac to compile your Java files in the terminal and java to run them. Example:
    javac Hello.java

    java Hello
  6. If you have not done so, setup the git config with your email and name:
    git config --global user.email "yourusername@s.sfusd.edu"

    git config --global user.name "Your Name"
  7. Use git in the terminal to stage, commit, and push your files to GitHub.
    Check your changed files using the git status command
    git status

    Stage your uncommited files (this is for adding all uncommited files):
    git add --all

    Commit your staged files:
    git commit -m "add Hello program"

    Push your changes to GitHub.
    git push
  8. You can check if you have done this correctly by checking to see if your program files appear on GitHub.

All posts  |  Post list