3 - Booleans and selection

Question 1

How does the Conjunction operator work in the boolean ADT?

Answer 1

The Conjunction operator (AND) in the boolean ADT returns “true” if both operands are “true,” otherwise it returns “false.” It is left associative and has the second highest precedence among logical operators.

Question 2

What is the behavior of the Disjunction operator in the boolean ADT?

Answer 2

The Disjunction operator (OR) in the boolean ADT returns “false” if both operands are “false,” otherwise it returns “true.” It is left associative and has the lowest precedence among logical operators.

Question 3

How does the Negation operator function in the boolean ADT?

Answer 3

The Negation operator (NOT) in the boolean ADT returns “false” if the operand is “true,” and it returns “true” if the operand is “false.” It is right associative and has the highest precedence among logical operators.

Question 4

What is a decision problem, and how many possible outcomes does it typically have?

Answer 4

A decision problem is a type of problem that has only two possible outcomes, and it is best represented using a boolean data type.

Question 5

What type of problem is a decision problem, and how is it related to classification?

Answer 5

A decision problem is a type of classification problem. It involves categorizing an input into one of two possible classes or outcomes.

Question 6

What is a problem definition in software development, and how is it typically written?

Answer 6

A problem definition in software development is the description of the problem that needs to be solved, usually written in plain English.

Question 7

How does a problem definition translate into a function definition in software development?

Answer 7

A problem definition translates into a function definition by specifying the function’s name, inputs, preconditions, outputs, and postconditions.

Question 8

What are the key considerations when translating a problem description into a function definition?

Answer 8

When translating a problem description into a function definition, ensure that:

• The function has a clear name.
• All inputs mentioned in the problem description are accounted for as function inputs.
• Outputs match the expected outcomes.
• Postconditions clearly represent the desired conditions using boolean logic.
  
  • The postcondition may use brackets to explicitly convey the precedence remember in engish the precedence of conjunction and disjunction are opposite to boolean logic

Question 9

What is a problem instance in the context of software testing?

Answer 9

A problem instance in software testing is a specific, concrete problem or scenario that consists of input values satisfying the preconditions of a function definition.

Question 10

What is a test case, and how is it related to a problem instance?

Answer 10

A test case is a specific problem instance along with the expected output for that instance. It is usually represented as one row in a test table.

Question 11

Why is it important to consider edge cases when defining problem instances and test cases and what should we be testing?

Answer 11

It is important to consider edge cases because they represent extreme or boundary conditions of inputs. They include
* the lowest and highest possible values
* zero (boundary between negative and positive integers)
* 1 (lowest positive number)
* -1 (highest negative number)
* etc.,
*
* which can help uncover potential issues in the function’s behavior and off by one errors

Question 12

How can you calculate the total number of problem instances when you have multiple inputs with two possible values each?

Answer 12

To calculate the total number of problem instances when you have multiple inputs with two possible values each, you can use the formula:

Total Instances = (Number of Values for Input 1) x (Number of Values for Input 2) x (Number of Values for Input 3) x …

and so on.

Question 13

How is the complexity of an algorithm determined, and what is it based on?

Answer 13

The complexity of an algorithm is determined based on the English-written version of the algorithm. It involves analyzing the operations within the algorithm to understand its computational efficiency.

Question 14

What are three key considerations when analyzing the complexity of an algorithm?

Answer 14

When analyzing the complexity of an algorithm, consider the following:

• Identify and count the operations within the algorithm.
• Assess the complexity of each operation (e.g., constant complexity).
• Determine if the number of operations is fixed or variable.

Question 15

What is the complexity of an algorithm that has constant complexity operations and a fixed number of operations?

Answer 15

An algorithm that has constant complexity operations and a fixed number of operations is considered to have constant complexity, denoted as Θ(1).

For this algorithm we would say:

The algorithm has complexity Θ(1)

Question 16

What is the time complexity associated with comparison and logical operations?

Answer 16

Comparison and logical operations are considered to have constant time complexity, denoted as O(1).

Question 17

What is the precedence order of operators, from highest to lowest, including arithmetic, comparison, and logical operators?

Answer 17

The precedence order of operators, from highest to lowest, is as follows:

1. Arithmetic operators
2. Comparison operators
3. Logical operators

Question 18

How are comparisons evaluated when they are on the same level, and what is this evaluation order called?

Answer 18

When comparisons are on the same level, they are evaluated from left to right. This evaluation order is called left-associative.

Question 19

What does a double inequality like “1 ≤ day ≤ 31” check for in a variable, and how can it be expressed differently?

Answer 19

A double inequality like “1 ≤ day ≤ 31” checks that the variable “day” lies within a certain interval. It can also be expressed as:

• “1.1 ≤ day and day ≤ 31”
• “0 < day < 32,”

although the latter may be less clear as it doesn’t explicitly express the bounds of the interval.

Question 20

What is a classification problem in the context of problem-solving?

Answer 20

A classification problem is a type of problem where all possible inputs can be categorized into distinct categories. The number of categories depends on the specific problem, and if there are only two categories, it is referred to as a decision problem.

Question 21

In the context of complexity analysis, what does “best-case complexity” refer to, and what does it indicate about an algorithm?

Answer 21

“Best-case complexity” refers to the minimum number of operations an algorithm performs under ideal conditions. It indicates the algorithm’s lower bound efficiency.

Question 22

What does “worst-case complexity” mean in complexity analysis, and what information does it provide about an algorithm?

Answer 22

“Worst-case complexity” represents the maximum number of operations an algorithm performs under the least favorable conditions. It provides insights into the algorithm’s upper bound efficiency and helps ensure it doesn’t perform exceptionally poorly for certain inputs.

Question 23

Why are best and worst case complexity analysis required and name a problem where we would likely need this

Answer 23

Best and worst case complexity is sometimes essential when we have an algorithm that can carry out a varying amount of operations

with best and worst we get a fuller understanding of the algorithms complexity for given inputs

a problem where we would likely require best and worst would be when the algorithm is a type of classification problem

Question 24

What conditions should be met for a sequence of selection statements in a classification algorithm to be considered correct?

Answer 24

For a classification algorithm to be correct, the conditions in the selection statements must be both:

• mutually exclusive (non-overlapping)
• comprehensive (covering all problem instances).

This ensures that each input falls into exactly one category

Question 25

What is the associativity of logical and comparison operators?

Answer 25

All logical and comparison operators are left-associative, except negation, which is right-associative.

Question 26

What is the precedence of operations, from highest to lowest

Answer 26

The precedence of operations, from highest to lowest, is:
1. arithmetic operations
2. comparisons
3. negations, conjunctions, disjunctions. (logic operations)