Accompanying code files:
- N/A
Jump to Homework
We already know the importance of algorithms and why they need to be formulated before we begin writing code. In this lesson, we will be learning common basic algorithms that you will likely encounter on the exam: swap, copy, sequential search, accumulate, and find-highest algorithms. We will see how some of these simpler algorithms play a part in sorting algorithms, like insertion sort, sequential sort, and merge sort. In addition, we will be learning how to write pseudocode.
- Pseudocode is an inner-step when turning your ideas into code. It is "code-like" but does not use the syntax of any programming language.
- It looks like shorthand instructions for your algorithm (like a recipe), and it is often useful to translate you algorithms into pseudocode first before actually writing your code, because you can write a program in any language based off these easy-to-read "human-friendly" instructions.
- This makes it easier to switch to writing a program in a different language if necessary (e.g. support for different operating systems, or newer technologies available in other languages that makes switching to another language a good idea)
- For coding interviews, if you forget specific syntax, writing pseudocode also shows you have an understanding of what you want your program to do, which still has merit over leaving the board blank!
- This simply involves switching values that are stored in 2 different variables
- The key thing to remember about this algorithm is that you need to use a temporary variable to store one of the values
How would you swap the values inside two integer variables. (e.g. if a = 6, and b = 8, make a = 8 and b = 6).
| Algorithm | Pseudocode | Java Code |
|---|---|---|
| 1. Create variable a with value of 6. | set a = 6 | int a = 6; |
| 2. Create variable b with value of 8. | set b = 8 | int b = 8; |
| 3. Create a temporary variable called temp. | initialize temp | int temp; |
| 4. Assign temp the value of a. | let temp = a | temp = a; |
| 5. Assign a the value of b. | let a = b | a = b; |
| 6. Assign b the value of temp. | b = temp; |
- Make a copy of an Array/ArrayList by creating a brand-new object that is a duplicate of the original
- This is not the same as creating a new array variable that references the original array (aliasing)
Suppose you have an array of integers. Make a new array object that is a copy of this array. The two arrays should contain the exact same values but not be the same object. Now, modify your code to work with an ArrayList of numbers.
Algorithm
- Create an array that is the same length as the original.
- Look at each of the values in the original array one at a time.
- Assign the value in the copy to be the corresponding value in the original.
- Continue until you reach the last index of the original array.
Pseudocode
original = {23, 51, 14, 50}
duplicate = new Array[length of original]
for each element in original:
set duplicate[index] = original[index]Java Code (using for loop)
int[] original = {23, 51, 14, 50};
int[] duplicate = new int[original.length];
for (int i = 0; i < original.length; i++)
duplicate[i] = original[i];- This is the process of looking at each of the elements in a list, one at a time, until you find what you are looking forum
Given an array of song titles, write a method called searchForTitle that allows you to search it for a specific song title using a string that represents the search target. The method should return the index of the target string if it is found and -1 if it does not
Algorithm
- Look at each of the titles in the array one at a time.
- Compare the target title to each of the titles.
- If the title is equal to the target title, stop looking and return the current index.
- If not keep going until you reach the end of the list.
- Return -1.
Pseudocode
index = 0
while (not at end of list) {
if (title = target title)
return index
index++
}
return -1Java Code
public int searchForTitle(String[] titles, String target) {
int index = 0;
while (index < titles.length) {
if (titles[index].equals(target))
return index;
index++;
}
return -1;
}- This involves using an accumulator (usually a variable) to add up or collect a specific value in a list
Given an array of hits for a baseball team, write a method called findSum that has one parameter: an int array, and sums all of the hits in the array.
Algorithm
- Create an accumulator, sum, and instantiate it to zero
- Look at each of the elements in the list
- Add the element to the sum
- Continue until you reach the end of the list
- Return the sum
Pseudocode
set sum = zero
for (iterate through all elements in list)
sum = sum + elementJava Code
public int findSum(int[] arr) {
int sum = 0;
for (int value : arr)
sum += value;
return sum;
}- This involves saving the value of the highest value seen so far in a list of values
Given a number of people's high scores in a video game, write a method called findHiScore that has one parameter: an int array, and returns the largest value in the array.
Algorithm
- Create a variable, high, and set it to the first element in the list
- Look at each of the scores in the list
- If the new score is greater than the current high score, set that new score as the current high score
- Continue until you reach the end of the list
- Return the high score
Pseudocode
set high = first score
for (iterate through all scores in the list) {
if (score > high)
high = score
}
Java Code
// What do you think is the pre-condition for this to work?
public int findHigh(int[] arr) {
int high = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > high)
high = arr[i];
}
return high;
}In-class questions will be updated soon!
ANSWERS
In-class question answers will be updated soon!
Assignments:
- Complete Algorithms (Basic Version pp 206 - 209) Review Questions
- Answers will be posted on the Topic 5 assignment answers issue.
Prep for Next Class:
- Review these notes