Big Idea 3: Algorithms and Programming Flashcards
How can a variable be used to represent a value, and what are the implications of using variables in programming? In the answer, explain the definition of variable.
A variable is an abstraction inside a program that can hold a value. Each variable has associated data storage that represents one value 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 include numbers, Booleans, lists, and strings.
Some values are better suited to representation using one type of datum rather than another.
How is the value of a variable determined as a result of an assignment in programming? In the answer, explain the definition of assignment operator.
The assignment operator allows a program to change the value represented by a variable. The exam reference sheet provides the “<-“ operator for assignment. For example, using “a <- expression” in text or as a block evaluates the 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.
How can a variable be used to represent a list or string, and what are the specific characteristics associated with these data types? In the answer, explain the definition of list and string.
A list is an ordered sequence of elements. For example, “[value1, value2, value3, …]” describes a list where value1 is the first element, value2 is the second element, and value3 is the third element, and so on.
An element is an individual value in a list that is assigned a unique index.
An index is a common method for referencing the elements in a list or string using natural numbers.
A string is an ordered sequence of characters.
How can data abstraction be developed using lists to store multiple elements? In the answer, explain the definition of data abstraction.
Data abstraction provides a separation between the abstract properties of a data type and the concrete details of its representation. Data abstractions can be created using lists, which allow multiple related items to be treated as a single value. Lists enable developers to develop a data abstraction that is easier to develop and maintain. Data abstractions often contain different types of elements.
The exam reference sheet provides the notation [value1, value2, value3, …] to create a list with those values as the first, second, third, and so on items. Lists can be assigned using aList <- [value1, value2, value3, …], creating a new list containing the values at indices 1, 2, 3, and so on, and assigns it to aList.
How can data abstraction be developed using lists to store multiple elements, and what are the advantages of using lists in data abstractions? In the answer, explain the definition of data abstraction.
Data abstraction provides a separation between the abstract properties of a data type and the concrete details of its representation.
Data abstractions can be created using lists.
Developing a data abstraction to implement in a program can result in a program that is easier to develop and maintain.
Data abstractions often contain different types of elements.
The use of lists allows multiple related items to be treated as a single value. Lists are referred to by different names, such as array, depending on the programming language.
The exam reference sheet provides the notation [value1, value2, value3, …] to create a list with those values as the first, second, third, and so on items.
For example,
- aList <- [value1, value2, value3, …] creates a new list that contains the values value1, value2, value3, and … at indices 1, 2, 3, and … respectively and assigns it to aList.
- aList <- [ ] creates an empty list and assigns it to aList
- aList <- bList assigns a copy of the list bList to the list aList. For example, if bList contains [20, 40, 60], then aList will also contain [20, 40, 60] after the assignment.
Explain how the use of data abstraction manages complexity in program code and discuss how list operations adhere to indexing rules.
Data abstractions manage complexity in programs by giving a collection of data a name without referencing the specific details of the representation.
The use of lists allows multiple items to be treated as a single value. This abstraction simplifies interactions with data collections and enhances the maintainability and readability of the code.
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.
For example,
- aList <- [value1, value2, value3, …] creates a new list that contains the values value1, value2, value3, and … at indices 1, 2, 3, and … respectively and assigns it to aList.
- aList <- [ ] creates an empty list and assigns it to aList
- aList <- bList assigns a copy of the list bList to the list aList. For example, if bList contains [20, 40, 60], then aList will also contain [20, 40, 60] after the assignment.
How can an algorithm be expressed without using a programming language? In the answer, explain the definition of algorithm.
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.
How can you represent a step-by-step algorithmic process using sequential code statements? In the answer, explain the definition of sequencing and expression.
Sequencing is the application of each step of an algorithm in the order in which the code statements 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 follows a set order of operations defined by the programming language.
Sequential statements execute in the order they appear in the code segment.
Clarity and readability are important considerations when expressing an algorithm in a programming language.
How do you evaluate expressions that use arithmetic operators? In the answer, explain the definition of arithmetic operators and MOD operation.
Arithmetic operators are part of most programming languages and include addition, subtraction, multiplication, division, and modulus operators.
The exam reference sheet provides the arithmetic operators +, -, *, /, and MOD. These are used to perform arithmetic on a and b. For example, “a + b” adds a and b, “a - b” subtracts b from a, “a * b” multiplies a and b, “a / b” divides a by b, and “a MOD b” 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 evaluates to 2.
The order of operations used in mathematics applies when evaluating expressions. The MOD operator has the same precedence as the * and / operators.
How can you evaluate expressions that manipulate strings, and what specific methods are involved? In the answer, explain the definition of string concatenation and substring.
String concatenation joins together two or more strings end-to-end to make a new string.
A substring is part of an existing string.
How do you write and evaluate expressions that use relational operators? In the answer, explain the definition of relational operators.
A relational operator tests the relationship between two variables, expressions, or values.
The exam reference sheet provides the following relational operators: =, ≠, >, <, ≥, and ≤.
These are used to evaluate whether a relationship holds true or false, for example, a = b evaluates to true if a and b are equal; otherwise, it evaluates to false.
How do you write and evaluate expressions that use logic operators? In the answer, explain the definition of logic operators.
Logic operators include NOT, AND, and OR, which evaluate to a Boolean value. The exam reference sheet describes their usage:
- NOT condition evaluates to true if the condition is false; otherwise, it evaluates to false.
- condition1 AND condition2 evaluates to true if both conditions are true; otherwise, it evaluates to false.
- condition1 OR condition2 evaluates to true if either condition1 is true or if both are true; otherwise, it evaluates to false.
The operand for a logical operator is either a Boolean expression or a single Boolean value.
How can you express an algorithm that uses selection without using a programming language? In the answer, explain the definition of selection.
Selection determines which parts of an algorithm are executed based on a condition being true or false.
Conditional statements, or “if-statements,” affect the sequential flow of control by executing different statements based on the value of a Boolean expression.
How do you write conditional statements? How do you determine the result of conditional statements? In the answer, explain the concept of conditional statements and their structure.
Conditional statements or “if-statements” are used to control the flow of execution based on the truth value of expressions. The basic structure is provided as:
- IF(condition) { block of statements } which executes the block of statements if the condition is true.
- IF(condition) { first block of statements } ELSE { second block of statements } which executes the first block if the condition is true, otherwise, it executes the second block.
What are nested selection conditional statements?
Nested conditional statements consist of conditional statements within conditional statements.
How can you express an algorithm that uses iteration without using a programming language? In the answer, explain the definition of iteration.
Iteration is a repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met.
How do you write iteration statements that utilize repeating a block of statements a specified number of times or until a condition is met?
The exam reference sheet provides two forms of iteration:
- REPEAT n TIMES { block of statements } where the block of statements is executed n times.
- REPEAT UNTIL(condition) { block of statements } where the code in the block of statements is repeated until the Boolean expression condition evaluates to true.
How do you determine the result or side effect of iteration statements that utilize ‘REPEAT n TIMES’ and ‘REPEAT UNTIL(condition)’?
- In REPEAT n TIMES iteration, the block of statements executes exactly n times.
- In REPEAT UNTIL(condition) iteration, the code block is repeated until the condition evaluates to true. If the condition never evaluates to true, an infinite loop occurs. If the condition evaluates to true initially, the loop body is not executed at all, due to the condition being checked before the loop.
How can you compare multiple algorithms to determine if they yield the same side effect or result?
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 expressions.
Some Boolean expressions can be written as equivalent conditional statements.
Different algorithms can be developed or used to solve the same problem.
How can you create and combine existing algorithms to construct new ones?
Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing 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 algorithm has benefits such as reducing development time, reducing testing, and simplifying the identification of errors.
How do you write expressions that use list indexing and list procedures?
The exam reference sheet provides basic operations on lists, including:
- Accessing an element by index: aList[i] accesses the element of aList at index i. The first element is at index 1.
- Assigning a value of an element of a list to a variable: x ← aList[i] assigns the value of aList[i] to the variable x.
- Assigning a value to an element of a list: aList[i] ← x assigns the value of x to aList[i].
- Assigning the value of one list element to another: aList[i] ← aList[j] assigns the value of aList[j] to aList[i].
- Inserting elements at a given index: INSERT(aList, i, value) shifts to the right any values in aList at indices greater than or equal to i.
- Adding elements to the end of the list: APPEND(aList, value) increases the length of aList by 1.
- Removing elements: REMOVE(aList, i) removes the item at index i in aList.
- Determining the length of a list: LENGTH(aList) evaluates to the number of elements currently in aList.
List procedures are implemented in accordance with the syntax rules of the programming language.
How do you write iteration statements to traverse a list? How do you determine the result of an algorithm that includes list traversals? In your answer, explain the definition of linear search.
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. The exam reference sheet provides the syntax for iteration statements:
FOR EACH item IN aList { block of statements }
The variable item is assigned the value of each element of aList sequentially, from the first element to the last element. The code in the block of statements is executed once for each assignment of item.
Knowledge of existing algorithms that use iteration can help in constructing new algorithms. Some examples of existing algorithms that are often used with lists include:
- determining a minimum or maximum value in a list
- computing a sum or average of a list of numbers
Linear search 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.
How do you determine the number of iterations required to find a value in a data set using a binary search algorithm? What are the requirements necessary to complete a binary search?
**The binary search algorithm starts at the middle of a sorted data set of numbers and eliminates 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. Binary search is often more efficient than sequential/linear search when applied to sorted data.**
floor(log2(n)) + 1
How do you write statements to call procedures? In your answer, explain the definitions of procedure, parameters, arguments, method, function, and return statement.
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 variables 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, flow of control is returned to the point immediately following where the procedure was called.
The exam reference sheet provides:
- procName(arg1, arg2, …) as a way to call which takes zero or more arguments; arg1 is assigned to parameter1, arg2 is assigned to parameter2, and so on.
- DISPLAY(expression) to display the value of expression, followed by a space.
- RETURN(expression) statement, which is used to return the flow of control to the point where the procedure was called and to return the value of expression.
- result ← procName(arg1, arg2, …) to assign to result the “value of the procedure” being returned by calling.
- INPUT() which accepts a value from the user and returns the input value.
