AP Computer Science A

About AP Computer Science A  |  All posts  |  Post list

Slack  |   Google Classroom  |   GitHub  |   Codenvy  |   Gradescope

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.

All posts  |  Post list