Flowcharts with Operators

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument }$

We introduce some mathematical notation to help us create algorithms to solve mathematical problems.

Operators

Many of the problems we will encounter in this course will require that we perform some iterative process or compute some quantity. For example:

(a): Compute the sum $1+2+3+\cdots +16$ .
(b): Count the number of divisors of $100$ .
(c): Determine the value of your account after 10 years if you invest $1000 into a savings account that offers a $4$ % interest rate compounded monthly.
(d): Sort the list of numbers 1, 5, 6, 2, 3, 8, 4 in ascending order.

When creating algorithms to solve these types of problems, we will often need to compare quantities or keep track of (and update) certain values. To help us with this we introduce some important notation and conventions. (Note that this list is not exhaustive.)

Assignment (:=) - This operator assigns the value of whatever is on the right to whatever is on the left. For example, x:=2 assigns the value 2 to the variable x. Note that x := y and y := x are not the same. Also, a statement like x := x+1 increments the value of x by 1.
Comparison (=,<,>,<=,>=) - These operators are used for comparisons. They give back a truth value to help determine which route to take in a conditional operation/decision. For example, x > 0 will be true if the value of x is larger than 0 and false otherwise.
Arithmetic (+,-,*,**,/,%) - These symbols simply perform the particular operations that we are used to. Note that ** represents exponentiation and % is modular division (it returns the remainder after long division). For example, 2**3 equals 8 and 7%3 is equal to 1.

The assignment and equality comparison operators given above are not given as they are used in Python or other programming languages. The notation above is used in pseudocode, which is a generic, programming language independent way to express algorithms. In later sections we will give examples of how to use these operators in Python.

Here is an example of an algorithm that determines if a number $n$ is divisible by 3. If the number is divisible by 3, the algorithm outputs a 1. Otherwise, the algorithm outputs a 0.

Here is an example of an algorithm that solves the linear equation $Ax+B=C$ for $x$ if $A$ , $B$ , and $C$ are real numbers with $A\neq 0$ . (Why do we need to assume that $A\neq 0$ ?)

The following examples illustrate a concept we will see over and over again. These flowcharts will have a loop showing that a certain step may be repeated multiple times until some condition is met.

Here is an example of an algorithm that finds the smallest integer greater than or equal to a real number $x\geq 0$ .

Here is an example of an algorithm that computes the sum $1+2+3+\cdots +n$ for any integer $n>0$ .

In the example above we need to track two quantities. The value of i tracks the number of times we go through the loop and while sum is updated after each iteration appropriately until we reach the desired sum. Note that the order of the instructions when updating i and sum is important. (Why?)

Here is an example of an algorithm that computes the number of integers divisible by 6 in the interval $[1,n]$ for some integer $n>0$ .

In the example above we also track two quantities. Notice that in this case we have an additional decision compartment as we only update the count of numbers divisible by 6 when the current number under consideration, i, is divisible by 6. Regardless of whether or not we update count, we always increase the value of i before looping back.

Problems

Develop an algorithm that takes in three real numbers $a$ , $b$ , and $c$ with $a\neq 0$ and determines if the roots of quadratic polynomial $ax^2+bx+c$ are real or not. If the roots are real, the output should be a 1. If the roots are complex, the output should be 0. Draw a flowchart for your algorithm.

Consider the quantity $b^2-4ac$ . Note that the second hint for this problem is the solution.

Develop an algorithm that takes in a positive integer $n$ and outputs “Fizz” if the number is divisible only by 3 (and not 5), “Buzz” if the number is divisible by 5 (and not 3), “FizzBuzz” if the number is divisible by 15, and n otherwise. Draw a flowchart for your algorithm.

Consider determining if the number is divisible by 15 first. If it is not, then you can determine if it is divisible by just 3 or just 5. Note that the second hint for this problem is the solution.

The factorial function is defined for a nonnegative integer $n$ in the following way: $n! = \begin {cases}n(n-1)(n-2)\cdots 2\cdot 1 & \text { if $n>0$,}\\ 1 & \text { if $n=0$.} \end {cases}$ Develop an algorithm for computing $n!$ and draw a flowchart for your algorithm.

This problem is similar to the example above where you wanted to compute $1+2+\cdots +n$ . Note that the second hint for this problem is the solution.

For the next few problems we will need the following definition:

For a nonzero integer $n$ , we say that a nonzero integer $m$ is a divisor if and only if there is no remainder when dividing $n$ by $m$ .

For example, 2 is a divisor of 10, but 3 is not a divisor of 10.

Develop an algorithm that takes in two nonzero integers $m$ and $n$ and determines if $m$ is a divisor of $n$ . If $m$ is a divisor of $n$ , the output should be 1. If $m$ is not a divisor of $n$ , the output should be 0. Draw a flowchart for your algorithm.

The solution to this problem is similar to the example above that determines if a number is divisible by 3. The main difference is that 3 should be replaced by the additional input $m$ . Note that the second hint for this problem is the solution.

Develop an algorithm that counts the number of (positive) divisors of $n$ for any integer $n>0$ .

The positive divisors of $n$ will have to be in the interval $[1,n]$ . (Why?)

The solution to this problem is similar to the example above that counds the number of integers divisible by 6 in the interval $[1,n]$ . The main difference is that you are now checking if $n$ (not i) is divisible by any of the numbers in the interval $[1,n]$ . Note that the third hint for this problem is the solution.

Develop an algorithm that computes the sum of (positive) divisors of $n$ for any integer $n>0$ .

The solution to this problem will use elements of the previous problem together with the example for how to compute $1+2+\cdots +n$ . Note that the second hint for this problem is the solution.

Prime numbers are integers greater than 1 that are not divisible by any positive integers other than 1 and hemselves. Develop an algorithm that determines if a positive integer $n$ is a prime number. If $n$ is a prime number, the output should be 1. If $n$ is not a prime number, the output should be 0. Draw a flowchart for your algorithm.

How many distinct divisors must primes have?

You should be able to modify the divisor count algorithm above by replacing the output with a decision compartment that determines whether the number is prime or not given its divisor count. Note that the third hint for this problem is the solution.

Develop an algorithm that computes the largest integer less than or equal to a real number $x\geq 0$ . Draw a flowchart for your algorithm.

The solution to this problem is similar to the example where you computed the smallest integer greater than or equal to a real number $x\geq 0$ . Just be mindful of the output. Note that the second hint for this problem is the solution.

Develop an algorithm that computes the largest integer less than or equal to a real number $x<0$ . Draw a flowchart for your algorithm.

Show that if $n$ is the largest integer less than or equal to a real number $x<0$ , then $-n$ is the smallest integer greater than or equal to $-x$ . Note that the second hint for this problem is the solution.

Develop an algorithm that computes the largest integer less than or equal to a real number $x$ .

Combine the answers to the previous two problems. Note that the second hint for htis problem is the solution.