Big Idea 3: Algorithms & Programming (30-35%)

Question 1

Variable

Answer 1

an abstraction inside a program that can hold a value, associated with data storage that represents one value at a time

Question 2

Assignment Operator

Answer 2

Represented by = or arrow sign
- allows a program to change the value represented by a variable

Question 3

Data Abstraction

Answer 3

• Manage complexity in programs by giving a collection of data a name without referencing the specific details of the representation
• Can be created using lists, which allows multiple related items to be treated as a single value.
• Often contain different types of elements

Question 4

Sequencing

Answer 4

statements execute in the order they appear in the code segment.

Question 4

Algorithm

Answer 4

finite set of instructions that accomplish a specific task and can be expressed computationally using natural language, diagrams, and pseudocode

Question 5

Code Statement

Answer 5

a part of program code that expresses an action to be carried out

Question 6

Expression

Answer 6

can consist of a value, a variable, an operator, or a procedure call that returns a value, and are evaluated to produce a single value by following a set order of operations defined by the programming language

Question 7

Arithmetic Operator: a MOD b

Answer 7

Represented by %
- reveals the remainder of a division problem (Ex. 9%3 = 0 because there’s no remainder, but 5 % 2 = 1 has a remainder of 1)

Question 8

a) Boolean Value
b) String
c) Substring

Answer 8

a) true or false
b) ordered set of characters “”
c) part of an existing string

Question 9

Relational Operators

Answer 9

Represented by =, ≠, >, <, ≥, ≤
- used to test the relationship between two variables, expressions, or values and evaluates to a Boolean value.

Question 10

Logical Operators

Answer 10

NOT, AND, OR
- evaluate to a Boolean value

Question 11

Selection (Conditional Statement)

Answer 11

First block of code statements are executed if the Boolean condition expressions evaluates to true, and the second code is executed if otherwise (A CONDITION)
- Nested Conditional: statements consist of conditional statements within conditional statements.

Question 12

Iteration

Answer 12

Repeating portion of an algorithm (a loop)

Question 13

REPEAT UNTIL(condition) iteration

Answer 13

• an infinite loop occurs when the ending condition will never evaluate to true
• if the conditional evaluates to true initially, the loop body is not executed at all, due to the condition being checked before the loop

Question 14

a) List
b) Element
c) Index

Answer 14

a) ordered sequence of elements in brackets
b) an individual value in a list that is assigned a unique index
c) common method for referencing the elements in a list or string using natural numbers

Question 15

a) INSERT(aList, i, value)
b) APPEND(aList, value)
c) REMOVE(aList, i)

Answer 15

a) inserts an element at a given index by shifting to the right any values in aList at indices greater than or equal to i. The length of the list is increased by 1, and value is placed at index i in aList.
b) adds an element to the end of the list, increasing the length of aList by 1.
c) removes the item at index i in aList and shifts to the left any values at indices greater than i. The length of aList is decreased by 1.

Question 16

Linear/Sequential Searches

Answer 16

Contents of the list do not have to be in order to be sequentially searched, starts at the beginning of a list and checks each element/item in the list in order until the desired value is found or all elements have been checked
(Ex. [10, 14, 19, 27, 31, 35, 42] Would take 4 comparisons to find 27 (1 =27 10, 2 = 14, 3 = 19, 4 = 27))

Question 17

Binary Searches

Answer 17

• MUST be sorted in order, starts at the middle of a list of NUMBERS and eliminates half the data and repeats until the desired value is found or all elements have been eliminated, done with the index starting at 1
• middle number is found by taking highest index number plus the lowest and divide by 2
• Can contain alphabetical, more efficient than sequential
• Does not have to be in ascending order and it CAN have duplicates

Question 18

a) Procedure
b) Parameter
c) Arguments

Answer 18

a) named group of programming instructions that may have parameters and return values
b) input variables of a procedure
c) specify the values of the parameters when a procedure is called

Question 19

Procedural Abstraction

Answer 19

• provides a name for a process and allows a procedure to be used only knowing what it does, not how it does it
• allows a solution to a large problem to be based on the solutions of smaller subproblems
• Modularity: The subdivision of a computer program into separate subprograms

Question 20

a) Software Library
b) Application Program Interfaces

Answer 20

a) contains procedures that may be used in creating new programs
b) specifications for how the procedures in a library behave and can be used.

Question 21

Simulation

Answer 21

• Abstraction of complex situations for a specific purpose and mimics real-world events to draw inferences
• Provides opportunities to study and make predictions for when experiments are not feasible for cost/safety/accessibility
• Uses & represents varying sets of data to reflect the changing state of a phenomenon, and can be limited and have bias (excluded or included) as they usually have to make assumptions about the real-world object/system they’re modeling
• Can model real-world events that are impractical for experiments and will not always have the same result and the results are not more accurate than an experiment
• Can refine previous results & hypotheses, investigates a phenomenon without time/money/safety constraints and does not require observations
• Developing abstract simulations involve removing details or simplifying functionality
• Safer, less expensive

Question 22

a) Problem
b) Instance of a Problem
c) Decision Problem
d) Optimization Problem

Answer 22

a) general description of a task that can/cannot be solved algorithmically
b) includes specific input
c) problem with a yes/no answer (Ex. Is there a path from A to B?)
d) problem with the goal of findingthe “best” solution among many (Ex. What is the shortest path from A to B?)

Question 23

Efficiency

Answer 23

estimation of the amount of computational resources used by an algorithm, typically expressed as a function of the input size, and an algorithm’s efficiency is determined through formal or mathematical reasoning

Question 24

Heuristic

Answer 24

- an approach to a problem that produces a solution that’s not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical - Some problems cannot be solved in a reasonable amount of time because there’s no efficient algorithm foir solving them, so approximate solutions are sought - Uses shortcuts to quickly find a good solution when finding an exact one is too hard or takes too long (Ex. Finding a new route) - Simplified: an approach to a problem that’s not guaranteed to be optimal every time but can be used since finding the optimal solution would take an unreasonable amount of solution Heuristic would be useful in creating a master schedule for a high school

Question 25

a) Reasonable Time b) Unreasonable Time c) Decidable Problem d) Undecideable Problem

Answer 25

a) Reasonable Time = algorithms with a polynomial effiency or slower (constant, linear, square, cube, etc such as 10x, x^2 b) Unreasonable Time = algorithms with exponential or factorial efficiencies (2^x, x!) c) decision problem for which an algorithm can be written to produce a correct output for all inputs (Ex. Is the number even?) d) no algorithm can be constructed that’s always capable of providing a correct yes/no answer, may have instances that have an algorithmic solution but there’s no algorithmic solution that could solve all problem instances, a programmer cannot use an algorthm that works most of the time when encountering this