6: Vectors

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What does the line 'std::vector crossed_out = std::vector(n, false);' do?

Creates a vector of Booleans initialized to false. (correct)

Creates a vector of Booleans initialized to true.

Creates a vector of characters initialized to empty.

Creates a vector of integers initialized to zero.

The part 'for (int i=0; i < n; i++)' indicates that the loop will iterate n times.

True

What is the primary purpose of a vector in programming?

To store a dynamically sized collection of elements.

In C++, a vector is part of the ________ Library.

Standard Template Signup and view all the answers

Match the following vector operations with their descriptions:

Push_back = Adds an element to the end of the vector Pop_back = Removes the last element of the vector Size = Returns the number of elements in the vector Clear = Removes all elements from the vector Signup and view all the answers

What does a precondition define in the context of a function?

What is required to hold when the function is called Signup and view all the answers

The postcondition specifies what is required to be true before the function is called.

False Signup and view all the answers

What happens if a function is called with invalid preconditions?

Undefined behavior Signup and view all the answers

The function 'pow' has a postcondition that guarantees the return value is ___ when the precondition is met.

b^e Signup and view all the answers

Which of the following is a recommended practice for defining preconditions?

Ensure the precondition is as weak as possible Signup and view all the answers

Match the following terms with their definitions:

Precondition = Requirements before function call Postcondition = Guaranteed outcomes after function call Undefined behavior = Results of invalid preconditions Overflow = Exceeding the limits of data representation Signup and view all the answers

Weak postconditions provide the most detailed information available regarding a function's effects.

False Signup and view all the answers

What should you document to help understand the function's behavior under its preconditions?

Document the function's expected behavior and limitations. Signup and view all the answers

If a function is called with preconditions not met, it may lead to ________ behavior.

undefined Signup and view all the answers

What is the primary goal when defining preconditions and postconditions for functions?

To document expectations and maintain reasonable limits Signup and view all the answers

What is the consequence of using an assert statement with a false expression?

It halts the program with an error message. Signup and view all the answers

Preconditions are always checked using assert statements.

False Signup and view all the answers

What are the postconditions in the root function example?

The result should return the larger root of the polynomial x^2 + p x + q. Signup and view all the answers

The expression used in an assert statement must be convertible to ______.

bool Signup and view all the answers

Match the type of assertion with its purpose:

Precondition = Checks validity before computation starts Postcondition = Checks correctness after computation finishes Invariant = Checks properties throughout method execution Signup and view all the answers

What is the purpose of using assert statements in function 'pow'?

To ensure the precondition holds when the function is called. Signup and view all the answers

In the gcd function example, the assertion 'assert(x > 0 && y > 0);' confirms that both inputs are non-negative.

False Signup and view all the answers

Why is stepwise refinement important in programming?

It simplifies problem-solving by breaking problems into smaller, manageable parts. Signup and view all the answers

Using assertions helps to enforce ______ during program execution.

correctness Signup and view all the answers

Match the programming concept with its definition:

Preconditions = Requirements that must be true before a function is executed Postconditions = Requirements that must be true after a function is executed Assertions = Statements that check conditions during runtime Signup and view all the answers

What is the first step in the process of stepwise refinement?

Create a coarse solution Signup and view all the answers

The refinement process only focuses on coding functions without considering data representation.

False Signup and view all the answers

What is the purpose of stepwise refinement in programming?

To break down a problem into smaller, manageable parts sequentially. Signup and view all the answers

In the example problem, the rectangles are defined by their top-left corner coordinates and ______.

dimensions Signup and view all the answers

Match the rectangles with their respective properties:

(x1, y1, w1, h1) = First rectangle with top-left corner at (x1, y1) (x2, y2, w2, h2) = Second rectangle with top-left corner at (x2, y2) w1 = Width of the first rectangle h2 = Height of the second rectangle Signup and view all the answers

What is a critical factor to check when determining if two rectangles overlap?

The position and dimensions of both rectangles Signup and view all the answers

The refinement process leads to the development of partial solutions that can be used in other problems.

True Signup and view all the answers

In the main function of the coarse solution, what are the two main actions captured?

Input rectangles and output the solution on overlap. Signup and view all the answers

Width and height inputs for the rectangles may be ______.

negative Signup and view all the answers

Which of the following is NOT a step in the refinement process?

Finalizing the program Signup and view all the answers

What is true about function declarations in programming?

A function can only be used after its declaration in the code. Signup and view all the answers

A function's definition is never considered a declaration.

False Signup and view all the answers

What must be true about the lines of code that follow a function declaration?

They can use the function that has been declared. Signup and view all the answers

The statement 'void B (int i);' is an example of a ___ declaration.

separate Signup and view all the answers

Match the following terms with their definitions regarding functions:

Declaration = A statement that introduces a function's name and type Definition = A statement that includes the body of the function and implementation Precondition = A condition that must be true before a function is executed Postcondition = A condition that must be true after a function is executed Signup and view all the answers

Study Notes

Introduction to Computer Science

Course details: 252-0032, 252-0047, 252-0058
Authors: Manuela Fischer and Felix Friedrich
Department: Department of Computer Science, ETH Zurich
Semester: Fall 2024

Vectors

Vectors store sequences of homogeneous data.
Iteration over numbers: for (int i=0; i<n; ++i) {...}
Sieve of Erathostenes example: calculates prime numbers less than n.
Crossing out non-prime numbers using a boolean vector.
Vector type: std::vector<T> where T is the element type.
Vector initialization: std::vector<T>(n,e) where n is the number of elements and e is the initial value for each element. Other initialization methods (e.g., initializer lists) are possible.
Element access: [] index operator, used for reading and writing elements.
std::vector<int> v = std::vector<int>(10); std::cout << v.at(10); example shows accessing elements using .at(), which performs bounds checking at runtime. Using [] might cause undefined behavior if referencing outside container bounds.
Vectors can be initialized with different values (e.g., 0, 2, a direct list of values).

Memory Layout and Properties

Vectors store elements in contiguous memory.
Random access is efficient.

Nested Vectors (Vectors of Vectors)

Used to represent multidimensional structures like tables or matrices.
Can be initialized using initialization lists or filling with a specific size and default value.
Access elements using nested indexing: m[i][j] for row i and column j.
Memory storage is flat, row-by-row.
Example to compute sum of lower triangle of a square matrix using nested for loops.

Beware of Mixed Integer Expressions

Vector functions often use unsigned integers (e.g., v.size()).
Mixed integer expressions can lead to unexpected behavior (e.g., infinite loops due to unsigned arithmetic—common error).
Compiler warnings can help detect potential issues. Example for (int x = 0; a.size()-x-1 >= 0; ++x){ std::cout << x; } demonstrates an infinite loop (due to the unsigned nature of a.size() ).

Reference Types

Pass by reference: Parameter receives the address of the actual argument, allowing modifications to be reflected in the caller.
Pass by value: Parameter receives a copy of the actual argument, modifications do not affect the original argument.
Reference types are denoted by T& (e.g., int&, std::vector<double>&).
Reference variables act as aliases to the objects they reference. References must have an existing object to reference.
Return by reference: Function returns a reference, allowing modifications to the original argument directly. Use of reference return type leads to changes to the original object, like int& inc(int i) example.
Temporary objects: A reference to a temporary object can lead to undefined behavior. A reference must remain valid for the lifetime of the object it refers to. Example: int& foo(int i) { return i; }.

Const References (const T& )

Passing elements by constant reference (const T&): Prevents accidental modification of the passed object within the function, while still avoiding unnecessary copying of large objects.
Improves performance by avoiding unnecessary copying (especially for large objects). Example of computing vector average using const std::vector<double>& values which prevents modification.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

This quiz focuses on the concept of vectors in computer science, covering their storage, iteration, and properties. It includes examples such as the Sieve of Eratosthenes and illustrates the use of nested vectors. Test your understanding of how vectors function and their application in programming.

6: Vectors

Choose a study mode

Podcast

Questions and Answers

What does the line 'std::vector crossed_out = std::vector(n, false);' do?

The part 'for (int i=0; i < n; i++)' indicates that the loop will iterate n times.

What is the primary purpose of a vector in programming?

In C++, a vector is part of the ________ Library.

Match the following vector operations with their descriptions:

What does a precondition define in the context of a function?

The postcondition specifies what is required to be true before the function is called.

What happens if a function is called with invalid preconditions?

The function 'pow' has a postcondition that guarantees the return value is ___ when the precondition is met.

Which of the following is a recommended practice for defining preconditions?

Match the following terms with their definitions:

Weak postconditions provide the most detailed information available regarding a function's effects.

What should you document to help understand the function's behavior under its preconditions?

If a function is called with preconditions not met, it may lead to ________ behavior.

What is the primary goal when defining preconditions and postconditions for functions?

What is the consequence of using an assert statement with a false expression?

Preconditions are always checked using assert statements.

What are the postconditions in the root function example?

The expression used in an assert statement must be convertible to ______.

Match the type of assertion with its purpose:

What is the purpose of using assert statements in function 'pow'?

In the gcd function example, the assertion 'assert(x > 0 && y > 0);' confirms that both inputs are non-negative.

Why is stepwise refinement important in programming?

Using assertions helps to enforce ______ during program execution.

Match the programming concept with its definition:

What is the first step in the process of stepwise refinement?

The refinement process only focuses on coding functions without considering data representation.

What is the purpose of stepwise refinement in programming?

In the example problem, the rectangles are defined by their top-left corner coordinates and ______.

Match the rectangles with their respective properties:

What is a critical factor to check when determining if two rectangles overlap?

The refinement process leads to the development of partial solutions that can be used in other problems.

In the main function of the coarse solution, what are the two main actions captured?

Width and height inputs for the rectangles may be ______.

Which of the following is NOT a step in the refinement process?

What is true about function declarations in programming?

A function's definition is never considered a declaration.

What must be true about the lines of code that follow a function declaration?

The statement 'void B (int i);' is an example of a ___ declaration.

Match the following terms with their definitions regarding functions:

Study Notes

Introduction to Computer Science

Vectors

Memory Layout and Properties

Nested Vectors (Vectors of Vectors)

Beware of Mixed Integer Expressions

Reference Types

Const References (const T& )

Studying That Suits You

Related Documents

Description

More Like This

Vector Quiz

Ransomware Attack Vectors

Vector Processor Architecture Quiz and Flashcards

Chapter 6: Vectors Flashcards