Algorithm Structure
Algorithm Efficiency
Unreasonable Time
100

What are the 3 building blocks of algorithms?

What is Sequencing, Selection Iteration

100

I am a measure of how many steps are needed to complete an algorithm



What is algorithm efficiency

100

Any algorithm whose efficiency includes an n2, n3, n4 … is called

What is a polynomial 

200

What is the difference between iteration and selection? 

Iteration-being asked to repeat an action

Selection-making a decision 

200

Your just started working for the ins and they are asking you to write an algorithm to search through past records more efficiently. What type of search should you use?

What is a linear search
200

A mathematician comes up with an algorithm for multiplying two matrices together.

This table shows how many steps the algorithm requires for different matrix sizes:

Write a function that best describes how the number of steps changes as the matrix size increases.

what is n^3

300

Makayla is developing software for an animal shelter. After some research, she comes up with this algorithm for calculating the number of daily calories required for a dog:


  • Calculate the Resting Energy Requirement (RER) by raising the dog's weight to the 3/4 power and multiplying the result by 70
  • If the dog is neutered, multiply RER by 1.6
  • Otherwise, multiply RER by 1.8


Which of the 3 building blocks of algorithms did Makayla use in her software?

What is selection

300

Sarrah develops an algorithm that figures out how to pack variously sized boxes into containers.

The algorithm comes up with this packing for 6 boxes into 2 containers:

Based on the table, describe the run time for this algorithm?

Does not run in a reasonable amount of time. The algorithm is exponential/

300

Kora implements an algorithm for determining whether a list has duplicate values.

She counts the number of steps required by the algorithm for increasing list lengths and comes up with this table:

Based on the table, describe the run time for this algorithm.


The algorithm is a polynomial the runs in a reasonable amount of time.

400

Look at the following example of expressing an algorithm. What is it an example of and how many of the 3 building blocks of algorithms are present?

What is a flow chart.

What is sequencing, selection, iteration

400

Serena operates a security camera that stores still images in timestamped filenames. The camera can generate thousands of images each day, and she needs a way to find the image corresponding to a particular timestamp. 

She comes up with this algorithm:


  1. Start with a list of the image filenames, sorted from oldest to newest.
  2. Set min to 1 and max to the number of images.
  3. Set index to the average of max and min, rounded down so that it is an integer.
  4. Check the filename located at that index in the list.
  5. If the filename equals the desired timestamp, the search is done! Exit the algorithm.
  6. If the filename is older than the desired timestamp, set min to be one larger than index.
  7. If the filename is newer than the desired timestamp, set max to be one smaller than index.
  8. Go back to step 3.


What type of search is used in the algorithm and why is it more efficent?

What is binary search. Binary search is more efficient because it looks at the moddle value of the list and repeatedly halves until the nimbler is found.

400

What is the difference between polynomial and exponential? Why are they important?

Polynomial-Has a consistent growth rate based on the input. Polynomials are considered to run in a reasonable amount of time.


Exponential-has an unstable growth rate based on input. Exponentials are considered to run in an unreasonable amount of time.


These 2 concepts are important in deciding if an algorithm is worth running. 

500

The following algorithm computes the maximum score for a list of final exam scores.


  • Initialize a variable max to the first score in the list.
  • For each score in the list, compare the score to max.
    • If score is greater than max, store score in max
  • Return max.


Which building blocks are involved in this algorithm?

What is sequencing, selection, and iteration.

500

The call to calcDrivingDistance() takes 3 seconds to return a result, as the driving directions algorithm requires searching through many possible routes to calculate the optimal route. The other operations, like incrementing the index and comparing the distances, take only a few nanoseconds.

If the app calls the procedure on a list of 10 stations, approximately how long will it take to complete?

What is 30 seconds

500

One way to measure the efficiency of an algorithm is to use a function to describe how the number of steps increases based on input. Categorize the following function as polynomial or exponential.

Polynomial

Exponential

Polynomial

Polynomial

Exponential 


M
e
n
u