# Chapter 4: Algorithms and Programming

## Abstraction

• An abstraction is a way to represent essential features without including the background details or explanations.

• Abstractions reduce complexity and allow for efficient design and implementation of complex software systems.

• Abstractions become a necessity as systems become more complex.

• In JAVA, the same code can be written using the System.out.print abstraction:

• System.out.print(“Hello World”);

• The first language to use abstractions instead of machine language was COBOL, which was designed by Grace Hopper.

• Programmers have worked to hide details by using abstractions.

• This allows the user to focus on the problem.

## Variables

• Variables vary.

• The assignment operator allows a program to change the value represented by a variable.

• The value stored in “score” will be the most recent value assigned.

• In the above example, the value of score changed from 7 to 10.

• Meaningful variable names help with the readability of program code and reduce the level of complexity of a program.

## Abstraction Examples Used on the AP Exam

• Coding in a programming language is often translated into code in another low- level language that the computer can execute.

• DISPLAY(expression) is an abstraction that is used on your AP exam to display a value of expression followed by a space.

• The input parameter for the DISPLAY abstraction is expression.

Operator

Meaning

Example

+

5 + 7 = 12

-

Subtraction

2 - 1 = 1

*

Multiplication

3 * 3 = 9

/

Division

3 / 2 = 1.5

MOD

Modulus

3 MOD 2 = 1

## Operator Precedence (Order of Operations)

• First: Parentheses

• Second: MOD, *, /

• Third: +, −

Example One

3 / 2 = 1.5

• As there is only one operation in this example, simply divide 3 by 2 for a final answer of 1.5.

Example Two

6 + 3 * 5 = 21

• In accordance with the order of operations, first multiply 3 by 5 to get a product of 15.

• Then add 6 to 15 for a final answer of 21.

Example Three

• In this example, first divide 12 by 4 to get a quotient of 3.

• Then since addition and subtraction have the same precedence, evaluate the problem from left to right—subtract 5 from 17 for a difference of 12 and then add 3 for a final answer of 15.

## MODULUS

• A modulus is a mathematical operation that returns the remainder after an initial number (the dividend) is divided by another number (the divisor).

## Example

The modulus is the integer remainder when two numbers are divided.

• The dividend is 4, and 3 is the divisor.

• The number 3 goes into 4 one time.

• Write a 1 on top, and multiply it by the divisor: 1 multiplied by 3 is 3.

• Then subtract 3 from 4. This gives 4 minus 3 equals 1, which is the remainder.

• The remainder, 1, is the answer.

## Notes:

1. If the divisor is a multiple of the dividend, it will divide evenly with no remainder, resulting in a modulus calculation of 0.

2. If the dividend is less than the divisor, the resulting modulus calculation will equal the value of the dividend.

3. A zero to the right of MOD results in a DIVIDE BY ZERO error.

4. A zero to the left of MOD is feasible and results in a modulus calculation of 0.

## ASSIGNMENT OPERATORS

• First the expression is evaluated.

• Then the variable is set to the value that was calculated for the expression.

## Example

What is the value of a after the expression is evaluated?

First multiply 4 by 5 to get 20, and then add 6 to get 26.

## LISTS

• A list is an ordered sequence of elements starting with the index 1.

• A list is a data abstraction that reduces the complexity in programs by giving a collection of data a name without referencing the specific details of the representation.

## DISPLAY OPERATORS

Example

What will the following program display?

• Note that a is initialized to the value of 3 and b is set to 17.

• The next step sets the value of a to the value of b, which is 17.

## INPUT OPERATORS

Example

What will the following program display if the INPUT function reads an even number such as 4?

• For 4 (or any even number) divided by 2, the remainder will always be 0.

## RELATIONAL AND BOOLEAN OPERATORS

### Example

• a is initialized to 3; b is initialized to the remainder when 3 is divided by 5. Since 3 is equal to 3, the program will display true.

## Numeric Procedures

### Example

• If the below code was executed several times, what is the percentage of times “true” would be expected to be displayed?

• RANDOM can pick 1 or 2.

• The chance of 1 being picked is 1/2 or 50%.

## Rotate the Robot

• ROTATE_RIGHT will rotate the robot 90 degrees clockwise.

• ROTATE_LEFT will rotate the robot 90 degrees counterclockwise.

## Move the Robot Forward

• To prevent the robot from moving off the grid and resulting in an error, use the CAN_MOVE(direction) abstraction.

## REPEAT_UNTIL Loop

• Loops will repeat a section of code until a condition is met.

• THE SWAP: A common algorithm is the swap.

# SEARCHING

## Linear Search

• A linear search (or sequential search) is an algorithm for finding an element in a list.

• This search starts from the beginning of a list and sequentially checks each element of the list until a match is found or the entire list is searched without finding the element.

• A linear search can be used for either a sorted list or an unsorted list.

## Binary Search

• A binary search is a search algorithm that halves the number of elements that need to be searched after every comparison.

• To use a binary search, the list must be sorted.