knowt logo

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.

MATHEMATICAL OPERATORS

Operator

Meaning

Example

+

Addition

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.

  • Answer: 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.

  • Answer: 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%.

  • Answer: 50%

Boolean Tables

Example

THE ROBOT

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.

I

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.

MATHEMATICAL OPERATORS

Operator

Meaning

Example

+

Addition

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.

  • Answer: 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.

  • Answer: 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%.

  • Answer: 50%

Boolean Tables

Example

THE ROBOT

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.

robot