A.P. Computer Science Course Unit 3
A.P. Computer Science Course Unit 3
Variables and Assignments (3.1):
A variable is an abstraction inside a program that can hold a value. Each variable has associated data storage that represents one values at a time, but that value can be a list or other collection that in turn contains multiple values
Using meaningful variable names helps with the readability of program code and understanding of what values are represented by the variables
Some programming languages provide types to represent data, which are referenced using variables. These types includes numbers, Boleans, list and strings
Some values are better suited to representation using one type of datum rather than another
Variable: an abstraction inside a program that can hold a value
Example Analogy:
A variable can be represented as a container cap, which stores data types inside the container.
Data Type:
Integer (ie. highscore)
Text/string (ie firstname/phoneNum)
Boolean (ie isRaining)
Upcoming Topics:
Variables
Declaring a variable
Assigning values
Data Types
Define a variable:
A variable
Is a defined element in a computer program or inside of a data file that can be substituted to retrieve a piece of information stored under the element name.
a name given to a piece of data/information
Examples:
Contact names in a cell phone
Favorites in a browser menu
Mathematical symbols, eg. x,y,z,etdc
Benefits:
Easier to remember
Quickly accessible
Save time
Reusable
Variable Declaration:
Before a variable can be used in the code, it has to be created in the program
To do so, you need a Javascript statement known as the variable declaration.
*A local variable can only be used inside of the code block where it has been created (eg. function parameter, loops; let)
//Let - (local - inside a specified code block)
*A global variable can be used throughout the entire program. (eg var)
//Var - (global - used anywhere)
Variables and Assignments (3.1)
The assignment operator allows a program to change the value represented by a variable
The exam reference sheet provides the “<--” operator to use for assignments. For example,
Text:
A < – expression
Block
A ← expression (blocks surrounding)
Evaluates expression and then assigns a copy of the result to the variable A
The value stored in a variable will be the most recent value assigned. For example
A←1
B←A
A←2
display(b)
Still displays 1
Storing Values
highScore ← 100 (int)
firstName ← “Ashley” (str)
isRaining ← True (boolean)
phoneNumber ← “555-0101” (str)
Not a mathematical number, so it’s a string
Can’t do math
Data Types:
In addition to text, variables can store different types of information depending on program need
The type of information found inside of a variable is known as the data type.
Data Types:
Javascript supports the following data types:
Numeric variables:
Any number in standard or scientific notation
No quotation marks are needed
String variables:
Contains any group of alphanumeric characters.
Variable values must be in quotes
Boolean variables:
This type of variable indicates whether the statement/condition is true or false
Null variables:
A null variable has no assigned value
Serves as a placeholder for future data
Weakly types language
Variables do not need to have the data type defined in the code as it is determined by the type of value placed in the variable.
Strongly typed languages
The data type for each variable has to be specified in the code
Data Abstraction (3.2)
A list is an ordered sequence of elements
An element is an individual value in a list that is assigned a unique index
An index is a common method for referencing the element in a list or string using natural numbers.
For purposes of the AP exam, the index starts at 1.
A string is an ordered sequence of characters.
New types of variables:
String:
An ordered sequence of characters
May contain letters, numbers and all other special characters
Words, phrases, sentences and ID number
Lists:
An ordered sequence of elements
Each element is a variable
Playlist of songs, names of students in school/class, contacts in phone
List Index:
Each element of a string (or list) is referenced by an index
For purpose of the AP exam, the index starts at 1
Animals - “zebra”, “elephant”, “giraffe”, “warthog”, “lion”
Arrays and Strings
Arrays
In a typical computer program, data cannot be stored without the use of a database such as Access, Oracle, DB2 etc.
Some of the program data, however, can be stored on a temporary basis by using data structures known as arrays.
An array is a systematic arrangement of objects usually in rows and columns.
An array is a collection of data values organized under a single name with an assigned index to distinguish each item in the array.
The name of the array has to be declared just as any new variable name. The size is expressed as the number of elements that the array is going to contain
If the number of elements is not specified upfront, the JavaScript will automatically increase the array size as new elements are added.
New = program invoking constructor
Constructor = special commands that creates a new instance of an object
Object = built-in function in a computer program that can do many different things depending on how it’s called
Each object has a collection of methods that can be invoked that can make the object do different things. - Change behavior of object when each method is caused
Var is not constructor
New is constructor; new instance of object
Data Abstraction (3.2)
Data abstraction provides a separation between the abstract properties of a data type and the concrete details of its representation
Data abstraction can be created using lists.
The exam reference sheet provides notation for lists
The exam reference sheet describes a list structure whose index values are 1 through the number of elements in the list, inclusive. For all list operations, if a list index is less than 1 or greater than the length of the list, an error message is produced and the program will terminate.
Note: Arrow takes place in equal sign (assignment operator)
Data Abstraction - Lists
Lists allows for data abstraction
Bundle variables together
Strings, numbers, characters etc
Give one name to a set of memory set
Do not need to know how many variables will be needed
Do not need to know how the elements are stored together
Populating
Like variables, creating an array doesn’t automatically populate it with data
To populate an array one value at a time, use the array name along with the index value:
var Days = new Array()
To populate an array all at once, use a single expression without index values. This approach should only be used if you have a complete dataset for the array.
Populate arrays separately (easier to look at)
Data Abstraction (3.2)
Data abstraction manage complexity in programs by giving a collection of data a name without referencing the specific details of the representation
Developing a data abstraction to implement in a program can result in a program that is easier to develop and maintain
The use of lists allows multiple related items to be treated a single value
The exam reference sheet provides notation for lists (see the next slide for details)
The exam reference sheet describes a list structure whose index values are 1 through the number of elements in the list, inclusive. For all list operations, if a list index is less than 1 or greater than the length of the list, an error message is produced and the program will terminate
How lists manage complexity of a program?
May not need as many variables
Variables for each student versus one variable that holds all students
Change the number of variables
Student transfers in/out of school –do not need to add/delete entire variable
Consistent computation
List of test scores can be curbed with same calculation for all scores
Variable name < —- [ many indexes of elements of values ] This is a list
Scores < – [95, 100, 20]
How can a line of code using a list manage the complexity of this code?
Improves readability
Does not need new variables to add more scores
Can easily update each score by the same amount (curve)
Can easily convert score to a different form (percent)
Mathematical Expressions (3.3)
An algorithm is a finite set of instructions that accomplish a specific task
Beyond visual and textual programming languages, algorithms can be expressed in a variety of ways, such as natural language, diagrams and pseudocode
Algorithms executed by programs are implemented using programming languages
Every algorithm can be constructed using combinations of sequencing, selection and iteration
Algorithm: a finite set of instructions that accomplish a specific task
Finite: start and end
Sequencing: algorithmic simple steps (1,2,3…)
Going to do these things in the order that they are specified
Selecting: conditional
Choose 2 dif outcomes based on decision / condition
Iteration : going back into loops
Repat something as long as something is true or stop once condition is done
The concept of sequencing is that it connects arrows that allow the sequence of steps.
Represented by the direct arrows in a direction
first step... second step... third step
Selection happens when there is a conditional/decision being made through a boolean value.
Represented by a diamond shape showing the decision being made, as well as arrows pointing in different directions
If/then conditions
Iteration happens as a loop, going back into the program and checking for boolean value.
Represented by arrows going back to different direction after a decision (in the form of a diamond)
arrows that form like a circle to represent the looping
for/while loops
Mathematical Expressions (3.3)
Sequencing is the application of each step of an algorithm in the order in which the code statement are given
A code statement is a part of program code that expresses an action to be carried out
An expression can consist of a value, a variable, an operator or a procedure call that returns a value
Expressions are evaluated to produce a single value
The evaluation of expressions followed a set order of operations defined by the programming language
Sequential statements execute in the order they appear in the code segment
Clarity and reliability are important considerations when expressing an algorithm in a programming language.
<--
Display ()
What is an object?
An object is a built-in function with a collection of properties and methods just as a real life physical object contains its own properties and features.
Objects and Methods
Each function that’s applicable to a given object is known as the object method
What is an Object?
In computer programming, an object is a built-in function with a collection of properties and methods just as real-life physical objects contain its own properties and features.
Objects and Methods:
Each function that’s applicable to a given object is known as the object method.
Array Methods
Like JavaScript objects, arrays have methods that can be applied to them to quickly accomplish a specific task when the method name is called.
Array Fill
A quick way to populate a newly created array with data is by using the fill method
This method allows you to populate the array completely by using a single call statement.
Array From
The from method allows you to populate an array with data by breaking up an existing text string
As a result, each string element will become its own separate value in the array with its own indexed location
Two examples of array methods are:
reverse()
sort()
Reversing an Array
The reverse method changes the order of items in the array by making the first item last and the last item first.
Sorting Arrays
You can quickly arrange the array items in alphabetical order by applying the sort() method to your array
Populating
Like variables, creating an array doesn’t automatically populate it with data
To populate an array one value at a time, use the array name along with the index value:
var Days = new Array()
To populate an array all at once, use a single expression without index values. This approach should only be used if you have a complete dataset for the array.
Populate arrays separately (easier to look at)
Mathematical Expressions (3.3)
Arithmetic operators are part of most programming languages and include addition, subtraction, multiplication, division and modulus operators
The exam reference sheet provides a MOD b which evaluates to the remainder when a is divided by b. Assume that a is an integer greater than or equal to 0 and b is an integer greater than 0.
For example, 17 MOD 5 values to 2
The exam reference sheet provides the arithmetic operators +, -, *, /, and MOD.
Text and block:
a + b
a - b
a * b
a / b
a % b ← mod
These are used to perform arithmetic on a and b. For example, 17/5 evaluates to 3.4
The order of operations used in mathematics applies when evaluating expressions. The MOD operator has the same precedence as the * and / operators sign.
Modulus Operator.
MOD: returns remainder after division
You can use it to tell whether a number is divisible or not.
Handled as same level as multiply/divide
Order of Operations
USE PEMDAS OR BODMAS
Controlling Array Length
Unless otherwise specified, the size of an array can be increased simply by adding more items to it.
This occurs even if the array size/length has been specified in the array declaration.
You have the option to decrease or increase the size of the array with the following command:
To increase the size set length property to a number higher than the highest index value
To decrease the size set length to a number lower than the highest index value.
Extracting
Javascript allows you to copy and store some items of an array elsewhere
This process is known as extracting
As a result the original array isn’t affected but some data is retrieved and may be used for other purposes, such as creating another array.
Slice
Splice
Push
You can add values to the end of an array using the push() method as follows:
Pop
You can also drop the last value of an array using the pop() method as follows:
Strings (3.4)
String concatenation joins two or more strings end to end to make a new string
A substring is a part of an existing string.
Strings:
Ordered sequence of characters
Some procedures may exist that can be used with strings
Each language has its own procedures/methods/functions
Sparse Array
If an array has only been filled partially, i.e. has several items missing in between the first and last value it is called sparse array.
Ascending:
arrayName.sort((num1, num2) => num1 - num2);
Descending:
arrayName.sort((num1, num2) => num2 - num1);
Boolean Expression (3.5)
Boolean value:
Either true or false
arrayName.sort();
If you’re working with numbers, however, you must use a compare functions to sort the array content
This function will compare each set of two values found in the array and decide which is greater
If you’d like to sort the items in increasing order ie from lowest to highest, use the compare functions as follows:
Function nomSort (a,b) {
Return a-b;}
arrayName.sort(numSort);
If the difference is positive, it means that the first item has a higher value and is out of order
As a result the first item is moved to the array position after the second item.
If the difference is negative, it means that the items are already in order
Their position remains unchanged.
If the difference between both values is 0, it means they are equal
Their position remains unchanged
If you’d like to reverse the order of tiems, i.e. sort them in decreasing order just reverse the order of operations as follows:
Function numSort (a,b) {
Return b-a;
]
Boolean Expression (3.5)
Boolean Expression (3.5)
Conditions (3.6)
Selection determines which part of an algorithm are executed based on a condition being true or false
How to make a conditional/selection using a flowchart? Use this image below! Also, use the diamond shape to convey decision and construct pathways for True/False. It’s decision making time!
You can use either pseudocode (blocks/written) or flowchart to convey conditionals (it also applies to anything other than conditions)
Conditional statements or “if statements” affect the sequential flow of control by executing different statements based on the value of a Boolean expression.
Conditions (3.6)
Conditional statements
When properly programmed, computers can mimic that behavior to act in a similar, AI-like fashion
When a computer program is executing it may occasionally come to a place in the code where a decision has to be made.
This decision may be made based on a variety of factors
Result of user input
Result of arithmetic operations
The result of data analysis
Conditional statement: piece of code that will execute only if the circumstances in the controlling condition are met.
Programs can make decisions by executing conditional statements
If statement: the code will only execute if the condition defined in the statement is true
Most basic conditional statement used in programming
Nested Conditionals (3.7)
Nested conditionals statements consists of conditional statements nested inside of conditional statement.
Nested Conditionals (3.7)
Nested conditionals statements consists of conditional statements within conditional statements.
Nested Conditionals
Complexe Decisions
There are numerous scenarios where the decisions you are making depends on multiple factors
Limiting your decision to a single factor may lead to an inaccurate selection
A plain IF statement or an IF ELSE statement alone cannot handle these types Of situations
It uses a single boolean condition in the statement.
Nesting
Nesting - Storing Similar objects one inside of the other
Nesting IF Statements
JavaScript provides you with the ability to combine conditional statements if there is more than one possible condition to be evaluated.
This process is known as nesting conditional statements
As a result the code will run only if the specified combinations of conditions are met.
Iteration (3.8)
Iteration is a repeating portion of an algorithm. Iteration repeats a specific number of times or until a given condition is met
Loops are a form of iteration.
Iteration:
Stopping Condition: a condition that stops the looping iteration process.
Iteration (3.8)
Iteration statements change the sequential flow of control by repeating a set of statements zero or more times, until a stopping condition is met.
In REPEAT UNTIL(condition) interaction, if the condition evaluates to true initially, the loop body is not executed at all, due to the condition being checked before the loop.
Program Loops
A set of commands executed repeatedly until a stopping condition has been met.
A sequence of instructions that is continually repeated until a certain condition is reached
Another way of thinking about it is a function that keeps running over and over again until it is told to stop.
Each time the loop iterates, the program has to make a decision whether or not the loop execution should continue
The decision is evaluated using a boolean condition.
Using a loop will save you trouble of rewriting identical code many times over
Space
Time
Debug
Programs become much smaller and easier to manage as a result
Less time is required to complete the code execution
Two types of loops commonly found in Javascript are the FOR loop and the WHILE loop
For loop
Will repeat execute a group of commands
This loop will run the exact number of times the programmer wants it to run
The loop is controlled through the counter-variable
The counter tracks the number of times the loop has been executed
The start and end values of the counter are set by the programmer in the loop’s control statement
The value of the loop counter is updated by the counter update statement each time the loop runs.
For (start value; end condition; counter update)
{code}
Every time the block of code is executed, the value of the counter will change through the counter update.
Once the counter reaches its end value, the loop will stop and the code wil. exit.
While loop
Iteration (3.8)
Iteration statements change the sequential flow of control by repeating a set of statements zero or more times, until a stopping condition is met
In REPEAT UNTIL (condition) iteration, an infinite loop occurs when the ending condition will never evaluate to true.
WHILE Loops
Like all loops, the WHILE loops will allow you to repeatedly run a block of code.
Usually, the code inside of a WHILE loop will continue executing as long as the condition controlling the loop is TRUE
With a WHILE loop, you have the option of setting up a counter if you’d like the loop to complete an exact number of iterations
If you choose this option, the code will run a predetermined number of times just as it would in a FOR loop.
DO/WHILE Loop
The DO/While loop is a variation of the WHILE loop
Like all of the other types of loops, it is meant to execute code repeatedly until told to exit by the loop control statement
In a DO/WHILE loop the code runs first and the boolean condition is checked
In all other loop types, the condition is checked first and the code runs second
Unlike in other loops the code is executed at least once and is re executed each time the condition evaluates to True
Do {Code}
While {condition};
3.9 Developing Algorithms:
Algorithms can be written in different ways and still accomplish the same tasks
Algorithms that appear similar can yield different side effects or results
Some conditional statements can be written as equivalent Boolean expression
Some Boolean expressions can be written as equivalent conditional statements
Different algorithms can be developed or used to solve the same problem
-
3.9 Developing Algorithms:
Algorithms can be created from an idea, by combining existing algorithms or by modifying existing algorithms.
Infinite Loops
An infinite number is any number that goes on forever
An infinite loop is a loop that goes on forever because its controlling condition never becomes false
Usually created by accident, e.g. incorrect program logic
Can be caused by any of the following:
An incorrectly written Boolean condition, ie one that can never be met
An incorrectly written counter update
Incorrect start/end values
Missing counter update
Missing termination condition
An infinite loop may cause any of the following:
A system slowdown or crash
An unresponsive system
A memory shortage
The only way to exterminate an infinite loop is through external / manual intervention such as:
Powering down the device
Disconnecting the power source
Stopping program execution (eg ALT + F4)
While usually triggered by incorrectly written code, infinite loops do have some legitimate uses.
In some cases, infinite loops may be employed to run continuously in 24 hour security monitoring system such as Ring (motion sensor)
3.9 Developing Algorithms:
Knowledge of existing algorithms can help in constructing new ones. Some existing algorithms include:
Determining the maximum or minimum value of two or more numbers
Computing the sum or average of two or more numbers
Identifying if an integer is or is not evenly divisible by another integer
Determining a robot’s path through a maze
Using existing correct algorithms as building blocks for constructing another algorithms has benefits such as reducing development time, reducing testing and simplifying the identification of errors.
3.10 Lists:
3.10 Lists
The exam reference sheet provides basic operations on the list (see next slide for details).
List procedures are implemented in accordance with syntax rules of the programming language
Traversing a list can be a complete traversal, where all elements in the list are accessed or a partial traversal where only a portion of elements are accessed.
Iteration statements can be used to traverse a list
The exam reference sheet provides pseudocode for loops (see next slide for details)
Knowledge of existing algorithms that use iteration can help in constructing new algorithms. Some examples of existing algorithms that are used with lists include:
Determining a minimum or maximum value in a list
Computing sum or average of a list of numbers
Linear or sequential search algorithms check each element of a list, in order, until the desired value is found or all elements in the list have been checked.
3.10 Lists
The exam reference sheet provides basic operations on the list (see next slide for details).
List procedures are implemented in accordance with syntax rules of the programming language
Traversing a list can be a complete traversal, where all elements in the list are accessed or a partial traversal where only a portion of elements are accessed.
Iteration statements can be used to traverse a list
The exam reference sheet provides pseudocode for loops (see next slide for details)
Knowledge of existing algorithms that use iteration can help in constructing new algorithms. Some examples of existing algorithms that are used with lists include:
Determining a minimum or maximum value in a list
Computing sum or average of a list of numbers
3.11 Binary Search
Linear or sequential search algorithms check each element of a list, in order, until the desired value is found or all elements in the list have been checked.
The binary search algorithm start at the middle of a sorted data set of numbers and eliminated half of the data; this process repeats until the desired value is found or all elements have been eliminated
Data must be in sorted order to use the binary search algorithm
A binary search is often more efficient than sequential/linear search when applied to sorted data
The difference between binary and sequential searches:
BINARY SEARCH:
first put numbers in order (ascending/descending)
start our search by looking at the middle number first
middle number = (highest_index + lower_index)/2 [Note: Chop off any decimal. point values]
e.g. divide and conquer
definition: start at the middle of a sorted data set of numbers and eliminated half of the data; this process repeats until the desired value is found or all elements have been eliminated
Advantage: Uses less memory, work and power to operate; faster and more efficient in general
Disadvantage: Less commonly known and implemented; harder to use; only use for bulk work (less efficient in smaller list)
SEQUENTIAL SEARCHES:
Each element in a list is examined starting with the first element until we find the desired target or each the end of the list.
does not need the elements to be in correct order
definition: check each element of a list, in order, until the desired value is found or all elements in the list have been checked.
Advantage: Used by programmers more often; simple to think and implament; less brain-power needed to understand.
Disadvantage: Could be used for longer list, but not recommended; not the best at handling long listing (which takes lots of time and energy)
Functions
…Functions are then invoked/executed through a JavaScript statement known as the Function Call.
Once declared, a function can be executed multiple times simply by calling the function name along with its parameters in any line of code.
3.12 Calling Procedures
A procedure is a named group of programming instructions that may have parameters and return values
Procedures are referred to by different names, such as method or function, depending on the programming language
Parameters are input values of a procedure. Arguments specify the values of the parameters when a procedure is called.
A procedure call interrupts the sequential execution of statements causing the program to execute the statements within the procedure before continuing. Once the last statement in the procedure (or a return statement) has executed, the flow of control is returned to the point immediately following where the procedure was called.
3.12 Calling Procedures
A procedure is a named group of programming instructions that may have parameters and return values
Procedures are referred to by different names, such as method or function, depending on the programming language
Parameters are input values of a procedure. Arguments specify the values of the parameters when a procedure is called.
A procedure call interrupts the sequential execution of statements causing the program to execute the statements within the procedure before continuing. Once the last statement in the procedure (or a return statement) has executed, the flow of control is returned to the point immediately following where the procedure was called.
In a standard function, all of the function commands are contained inside of the function
When the function is called upon to execute these commands; output is provided from within the function
Returning - This action can be accomplished using the return command along with the variable data
3.13 Developing Procedures
PROCEDURE detour() {
ROTATE_LEFT()
MOVE_FORWARD()
ROTATE_RIGHT()
MOVE_FORWARD()
MOVE_FORWARD()
ROTATE_RIGHT()
MOVE_FORWARD()
ROTATE_LEFT()
}
detour()
3.13 Developing Procedures
One common type of abstraction is procedural abstraction, which provides a name for a process and allows a procedure to be used only knowing what it does, not how it does it.
Hiding an entire process under a single name
Only need to know name
Procedural abstraction allows a solution to a large problem to be based on the solutions of smaller subproblems. This is accomplished by creating procedures to solve each of the subproblems.
The subdivision of a computer program into separate subprograms is called modularity.
A procedural abstraction may extract shared features to generalize functionality instead of duplicating code. This allows for program reuse, which helps manage complexity.
Using parameters allows procedures to be generalized, enabling the procedures to be reused with a range of input values or arguments
Using procedural abstraction helps improve code readability
Using procedural abstraction in a program allows programmers to change the internals of the procedure (to make it faster, more efficient, use less storage, etc.) without needing to notify users of the change as long as what the procedure does is preserved.
The benefits the code on the right have from the code on the left is that it is better, simpler and convenient (since it uses abstraction).
The procedure round(number) takes in a number and return the rounded value.
We do not need to know how the procedure round(number) works, just what it does and how to call it.
3.14 Libraries
A software library contains procedures that may be used in creating new programs.
Existing code segments can come from internal or external sources, such as libraries or previously written code
The use of libraries simplifies the task of creating complex programs.
Application program interfaces (APIs) are specifications for how the procedure in a library behave and can be used.Documentation for API/Library is necessary in understanding the behaviors provided by the API/library and how to use them.
The exam reference ship is a library example itself!!!!
3.15 Random Values
/
3.15 Random Values
You would like to write a segment of code that will simulate a flipping of a coin with “Heads” or “Tails”
You will need to use a random number generator and assign the output of “Heads” or “Trails to a specified result.
Result ← RANDOM(1, 2)
If Result = 1:
{Result ← “Heads”}
Else:
{Result ←”Tails”}
Display(Result)
spinner ← Random(1, 8)
If spinner <= 3:
display(“green”)
Else:
If spinner <= 5:
display(“blue”)
Else:
If spinner <= 6:
display(“red”)
Else:
If spinner <= 7:
display(“purple”)
Else:
display(“yellow”)
3.16 Simulations
Simulations are abstractions of more complex objects or phenomena for specific purpose
A simulation is a representation that use varying sets of values to reflect the changing state of a phenomena
Simulations often mimic real world events with the purpose of drawing inferences allowing investigation of a phenomenon without the constraints of the real world
The process of developing an abstract simulation involves removing specific details or simplifying functionality
Simulations can contain bias derived from the choices of real world elements that were included or excluded.
Simulations are most useful when real world events are impractical for experiments (eg too big, too small, too fast, too slow, too expensive, or too dangerous)
Simulations facilitate the formulation and refinements of hypotheses related to the object or phenomena under consideration. (NEW THEORIES)
Random number generators can be used to simulate the variability that exists in the real world.
Computer simulations usually have to make assumptions about the real world object or system they are modeling
For example, we can assume that people will be in a car when it is moving
We can and cannot assume the driver will have a seatbelt on
Simulations can have bias. In this case, the type of cars that may be chosen to simulate the crash.
4) removing more data and calculation so the simulation can run faster.
Removing more data does not provide better accuracy because when one removes data, they have less varied results, and therefore the answer is not as reliable.
(remove data → less test values → less varied results → not reliable data → worse accuracy)
SIMULATION NOTES
Simulations are abstractions of complex situations done for a specific purpose
Simulations provide opportunities to study and make predictions when experiments are not feasible for many reasons to include:
Cost 💰
Safety 🦺
Accessibility🦿
A simulation uses and represents varying sets of data to reflect the changing state of a phenomena
Developing abstract simulations involve removing details or simplifying functionality
Simulations can be done without the constraints of the real world
Simulations can have bias
Simulations can refine previous results and hypotheses
Random number generators can be used to create simulations related to the real world.
The simulation may reveal possible safety issues that can be corrected before (train) construction begins
A is the answer because in a simulation, one could observe the safety issues without being harmed during the process. Once those problems are corrected, the construction can begin.
A retail wants to identify the item which sold the most of their website
A is least beneficial because it already happened in the past
3.16 Simulations
Simulations are abstractions of more complex objects or phenomena for a specific purpose.
A simulation is a representation that uses varying sets of values to reflect the changing state of a phenomenon.
Simulations often mimic real world events with the purpose of drawing inferences, allowing investigation of a phenomenon without the constraint of the real world
The process of developing an abstract simulation involves removing specific details or simplifying functionality.
Simulations can contain bias derived from the choices of real world elements that were included or excluded.
Simulations are most useful when real world events are impractical for experiments (eg too big, too small, too slow, too expensive, or too dangerous)
Simulations facilitate the formulation and refinement of hypotheses related to the object or phenomena under consideration
Random number generators can be used to simulate the variability that exists in the real world.
Car Simulation Software
Let’s look at some reasons why car simulations software may be more beneficial?
Safer
Less expensive
Present safety issues that may have been previously thought of
Provides insight to various possibilities.
What are some details you may need to eliminate in order to improve the functionality of the simulations?
Limit amount of characteristics/functionality
Which of the following scenarios is better to do as a simulation than a calculation?
2. Study the set of insects on a farm
4. Studying the impact carbon emissions on the environment
Which of the following statements expresses a constraint of using a computer simulation to imitate real world objects or systems?
C) Computer simulations usually make some assumptions about the real world object or system being modeled.
Which of the scenarios below is using a simulation more beneficial than performing a calculator?
C) Investigation ways to reduce the amount of waste in natural rivers
D) Studying the impact of the change of the honeybee population in the USA.
3.17 Algorithm Efficiency
Algorithm: sequence of logical steps or instruction needed to find a solution to a problem
A problem is a general description of a task that can (or cannot) be solved algorithmically. An instance of a problem also includes specific input. For example, sorting is a problem; sorting the list (2,3,1,7) is an instance of the problem.
A decision problem is a problem with a yes/no answer (eg, is there a path from A to B?)
An optimization problem is a problem with the goal of finding the “best” solution among many (eg, what is the shortest path from A to B?)
Efficiency is an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input. An algorithm’s efficiency is determined through formal or mathematical reasoning.
An algorithm’s efficiency can be informally measured by determining the number of times a statement or group of statements executes.
Different correct algorithms for the same problem can have different efficiencies.
Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
Comparing efficiency through cards
Algorithm 2 seems better
Linear or polynomial searches are better than exponential in terms of efficiency. Choose algorithm 1 and 3.
Factorial 5! = 5*4*3*2*1
Algorithm 1, 3 runs in a reasonable amount of time, and algorithm 2,4 runs in an unreasonable time.
Algorithm 2 appears to run in an unreasonable amount of time because it’s exponential.
Algorithm 1 and 3 appears to run in a reasonable amount of time.
A problem is a general description of a task that can (or cannot) be solved algorithmic-ally. An instance of a problem also includes specific input. For example, sorting is a problem; sorting the list (2,3,1,7) is an instance of the problem.
Efficiency is an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input. An algorithm’s efficiency is measured through formal or mathematical reasoning, but it can also be measured informally by determining the number of times the statement executes. The role of it in problem solving is an efficient solution helps the computer process less resources, time, energy and effort into a task while getting the same input from a more bulky solution.
An algorithm is efficient if it follows this stated requirement:
Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time.
The graph below shows a reasonable efficiency because it is linear:
An algorithm is inefficient if it follows this stated requirement:
Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
The graph below describes an unreasonable efficiency because it is exponential.
The criteria that best determines the efficiency of an algorithm is to make sure the number of steps go in a polynomial-fashion way rather than an exponential or factorial way. Graphing can indeed help most of the time, but using an equation can be more clear in complicated situations. Therefore, the best way to determine efficiency is through equations, as it is much more transparent to look at once all the work is done.
3.17 Algorithm Efficiency
A decision problem is a problem with a yes/no answer (e.g. is there a path from A to B).
An optimization problem is a problem with the goal of finding the “best” solution among many (e.g. what is the shortest path from A to B)?
Efficiency is an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input.
An algorithm efficiency is determined through formal or mathematical reasoning.
Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for them. In these cases, approximate solutions are sought.
A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.
Heuristic is an approach to a problem that is not guaranteed to be optimal every time but can be used since finding the optimal solution would take an unreasonable amount of time.
3.18 Undecidable Problems
A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs (eg, “Is the number even?”)
An undecidable problem is one for which no algorithm can be constructed that is always capable of providing a correct yes or no answer.
An undecidable problem may have some instances that have algorithmic solutions, but there are no algorithmic solutions that could solve all instances of the problem.
Decidable problem:
One that we can come to a yes/no answer given any input
An example would be given a number to determine if it is divisible by 3. We know that the algorithm below would provide the correct output every time.
Undecidable problem:
Halting problem -
The halting problem is defined as: Given an arbitrary computer program with given inputs, will the program stop or will it run forever?
There is no way to solve this problem with a yes/no answer every time. How do you test for an ending if there is not one?
One way would be to test for an ending, but what if that ending is not easily found? What if it takes an unreasonable amount of time to find the ending? Is that because there is an ending or does one not exist?
You see where the problem comes in?
This is an undecidable problem - there is no algorithm which can always produce a yes/no answer for every input of the problem.
Where may we have seen this in computers today? When a website or program takes too long to load. It may never load, or it may be taking a long time. Either way, after a certain time the computer decides the program should be stopped.