Introduction - Chapter 1

Question 1

A blank is a way of organizing, storing, and performing operations on data.

Answer 1

data structure

Question 2

A blank is the data structure that stores subitems, often called fields, with a name associated with each subitem.

Answer 2

record

Question 3

An blank is a data structure that stores an ordered list of items, where each item is directly accessible by a positional index.

Answer 3

array

Question 4

A blank is a data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node.

Answer 4

linked list

Question 5

A blank is a data structure in which each node stores data and has up to two children, known as a left child and a right child.

Answer 5

binary tree

Question 6

A blank is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array.

Answer 6

hash table

Question 7

A blank is a tree that maintains the simple property that a node’s key is greater than or equal to the node’s childrens’ keys.

Answer 7

max-heap

Question 8

A blank is a tree that maintains the simple property that a node’s key is less than or equal to the node’s childrens’ keys.

Answer 8

min-heap

Question 9

A blank is a data structure for representing connections among items, and consists of vertices connected by edges.

Answer 9

graph

Question 10

A blank represents an item in a graph.

Answer 10

vertex

Question 11

An blank represents a connection between two vertices in a graph.

Answer 11

edge

Question 12

A linked list stores an blank of items

Answer 12

ordered list

Question 13

A node in blank can have zero, one, or two children.

Answer 13

binary tree

Question 14

The data stored in a blank can be a record with multiple subitems.

Answer 14

list node

Question 15

Items stored in an array can be accessed using a blank

Answer 15

positional index

Question 16

Inserting an item at the end of a 999-item array requires how many items to be shifted?

Answer 16

0

Question 17

Inserting an item at the end of a 999-item linked list requires how many items to be shifted?

Answer 17

0

Question 18

Inserting an item at the beginning of a 999-item array requires how many items to be shifted?

Answer 18

999

Question 19

Inserting an item at the beginning of a 999-item linked list requires how many items to be shifted?

Answer 19

0

Question 20

An blank is a set of commands that must be followed for a computer to perform calculations or other problem-solving operations.

Answer 20

algorithm

Question 21

According to its formal definition, an algorithm is a blank carried out in a specific order to perform a particular task.

Answer 21

finite set of instructions

Question 22

An algorithm is not the blank; it is simple logic to a problem represented as an informal description in the form of a flowchart or pseudocode.

Answer 22

entire program or code

Question 23

Input -> blank -> output

Answer 23

algorithm

Question 24

A blank can be defined as a real-world problem or real-world instance problem for which you need to develop a program or set of instructions.

Answer 24

problem

Question 25

An blank is defined as a step-by-step process that will be designed for a problem.

Answer 25

algorithm

Question 26

After designing an algorithm, the algorithm is given the necessary and desired blank.

Answer 26

inputs

Question 27

The input will be passed to the blank, producing the desired output.

Answer 27

processing unit

Question 28

The outcome or result of the program is referred to as the blank.

Answer 28

output

Question 29

Blank are step-by-step procedures designed to solve specific problems and perform tasks efficiently in the realm of computer science and mathematics.

Answer 29

Algorithms

Question 30

Algorithms take blank, which can be in various formats, such as numbers, text, or images.

Answer 30

input data

Question 31

The algorithm blank the input data through a series of logical and mathematical operations, manipulating and transforming it as needed.

Answer 31

processes

Question 32

After the processing is complete, the algorithm produces an blank, which could be a result, a decision, or some other meaningful information.

Answer 32

output

Question 33

A key aspect of algorithms is their blank, aiming to accomplish tasks quickly and with minimal resources.

Answer 33

efficiency

Question 34

Algorithm designers constantly seek ways to blank their algorithms, making them faster and more reliable.

Answer 34

optimize

Question 35

Algorithms are implemented in various blank, enabling computers to execute them and produce desired outcomes.

Answer 35

programming languages

Question 36

Algorithms aids in your understanding of blank. When you have a sizable real-world problem, you must break it down into small steps to analyze it quickly.

Answer 36

scalability

Question 37

The real world is challenging to break down into smaller steps. If a problem can be easily divided into smaller steps, it indicates that the problem is blank.

Answer 37

feasible

Question 38

Algorithms are used in blank and blank to find patterns in big datasets and forecast outcomes.

Answer 38

data analysis
machine learning

Question 39

Thanks to machine learning methods like blank, blank and blank, computers can learn from data and improve over time. These techniques are essential for applications such as recommendation systems, natural language processing, and picture recognition.

Answer 39

support vector machines,
decision trees, and
neural networks

Question 40

Blank safeguard data by using encryption and decryption techniques, guaranteeing safe data storage and communication

Answer 40

Cryptography algorithms

Question 41

Algorithms such as blank, blank and blank are commonly employed in data integrity maintenance, user authentication, and sensitive information security. These algorithms comprise the foundation of cybersecurity measures used in secure communications, data encryption, and online transactions.

Answer 41

SHA-256,
AES, and
RSA

Question 42

blank can efficiently index and retrieve pertinent information thanks to search algorithms such as PageRank and Hummingbird.

Answer 42

Search engines

Question 43

By prioritizing web pages according to their significance and relevancy, what algorithms assist users in locating the most relevant information available online. Effective search algorithms are necessary to manage the enormous volume of online information.

Answer 43

PageRank and Hummingbird.

Question 44

Blank are utilized to select the optimal answer from various options. In various industries, including banking, engineering, logistics, and artificial intelligence, sophisticated issues are resolved using methods like gradient descent, linear programming, and genetic algorithms.

Answer 44

Optimization methods

Question 45

Blank algorithms increase productivity, reduce expenses, and optimize resources for operations and decision-making.

Answer 45

Optimization

Question 46

Due to their ability to analyze medical images, forecast disease outbreaks, and recognize genetic changes, algorithms are indispensable in blank.

Answer 46

medical diagnostics

Question 47

Blank has been transformed by machine learning algorithms, in particular, which enable the creation of customized treatment regimens based on each patient’s unique genetic profile

Answer 47

Personalized medicine

Question 48

Algorithms help to speed up the sequencing and interpretation of blank, improving biotechnology and genomics research.

Answer 48

genomic data

Question 49

Name 6 Characteristics of an Algorithm

Answer 49

Finiteness
Definiteness
Input
Output
Effectiveness
Generality

Question 50

An algorithm must always have a blank number of steps before it ends. When the operation is finished, it must have a defined endpoint or output and not enter an endless loop.

Answer 50

finite

Question 51

An algorithm needs to have exact blank for each step. Clear and straightforward directions ensure that every step is understood and can be taken easily.

Answer 51

definitions

Question 52

An algorithm requires one or more blank. The values that are first supplied to the algorithm before its processing are known as blank. These blanks come from a predetermined range of acceptable values.

Answer 52

inputs

Question 53

One or more blank must be produced by an algorithm after every step has been completed. The relationship between the input and the result should be clear.

Answer 53

outputs

Question 54

An algorithm’s stages must be sufficiently straightforward to be carried out in a finite time utilizing blank. With the resources at hand, every operation in the algorithm should be doable and practicable.

Answer 54

fundamental operations

Question 55

Rather than being limited to a single particular case, an algorithm should be able to solve a blank. It should offer a generic fix that manages a variety of inputs inside a predetermined range or domain.

Answer 55

group of issues

Question 56

A straightforward approach that exhaustively tries all possible solutions, suitable for small problem instances but may become impractical for larger ones due to its high time complexity.

Answer 56

Brute Force Algorithm

Question 57

A method that breaks a problem into smaller, similar subproblems and repeatedly applies itself to solve them until reaching a base case, making it effective for tasks with recursive structures.

Answer 57

Recursive Algorithm

Question 58

Utilized to transform data into a secure, unreadable form using cryptographic techniques, ensuring confidentiality and privacy in digital communications and transactions.

Answer 58

Encryption Algorithm

Question 59

A trial-and-error technique used to explore potential solutions by undoing choices when they lead to an incorrect outcome, commonly employed in puzzles and optimization problems.

Answer 59

Backtracking Algorithm

Question 60

Designed to find a specific target within a dataset, enabling efficient retrieval of information from sorted or unsorted collections.

Answer 60

Searching Algorithm

Question 61

Aimed at arranging elements in a specific order, like numerical or alphabetical, to enhance data organization and retrieval.

Answer 61

Sorting Algorithm

Question 62

Converts data into a fixed-size hash value, enabling rapid data access and retrieval in hash tables, commonly used in databases and password storage.

Answer 62

Hashing Algorithm

Question 63

Breaks a complex problem into smaller subproblems, solves them independently, and then combines their solutions to address the original problem effectively.

Answer 63

Divide and Conquer Algorithm

Question 64

Makes locally optimal choices at each step in the hope of finding a global optimum, useful for optimization problems but may not always lead to the best solution

Answer 64

Greedy Algorithm

Question 65

Stores and reuses intermediate results to avoid redundant computations, enhancing the efficiency of solving complex problems.

Answer 65

Dynamic Programming Algorithm

Question 66

Utilizes randomness in its steps to achieve a solution, often used in situations where an approximate or probabilistic answer suffices.

Answer 66

Randomized Algorithm

Question 67

There are no well-defined standards for blank. It is, however, a problem that is resource-dependent. Algorithms are never written with a specific programming language in mind.

Answer 67

writing algorithms

Question 68

As you all know, blank such as loops like do, for, while, all programming languages share flow control such as if-else, and so on. An algorithm can be written using these common constructs.

Answer 68

basic code constructs

Question 69

Algorithms are typically written in a blank, but this is not always the case. Algorithm writing is a process that occurs after the problem domain has been well-defined. That is, you must be aware of the problem domain for which you are developing a solution.

Answer 69

step-by-step fashion

Question 70

Algorithms instruct programmers on how to blank.

Answer 70

write code

Question 71

This feature was perfectly designed for the algorithm if you are given a problem and break it down into small-small modules or small-small steps, which is a basic definition of an algorithm.

Answer 71

Modularity

Question 72

An algorithm’s blank is defined as when the given inputs produce the desired output, indicating that the algorithm was designed correctly. An algorithm’s analysis has been completed correctly.

Answer 72

Correctness

Question 73

It means that the algorithm should be designed in a straightforward, structured way so that when you redefine the algorithm, no significant changes are made to the algorithm.

Answer 73

Maintainability

Question 74

It takes into account various logical steps to solve a real-world problem.

Answer 74

Functionality

Question 75

Blank refers to an algorithm’s ability to define your problem clearly.

Answer 75

Robustness

Question 76

If the algorithm is difficult to understand, the designer will not explain it to the programmer.

Answer 76

User-friendly

Question 77

If an algorithm is blank, it is blank to understand.

Answer 77

simple

Question 78

Your algorithm should be blank if another algorithm designer or programmer wants to use it.

Answer 78

extensible

Question 79

9 Qualities of a good algorithm

Answer 79

Efficiency
Correctness
Clarity
Scalability
Reliability
Optimality
Robustness
Adaptability
Simplicity

Question 80

Blank: A good algorithm should perform its task quickly and use minimal resources.

Answer 80

Efficiency

Question 81

Blank: It must produce the correct and accurate output for all valid inputs.

Answer 81

Correctness

Question 82

Blank: The algorithm should be easy to understand and comprehend, making it maintainable and modifiable.

Answer 82

Clarity

Question 83

Blank: It should handle larger data sets and problem sizes without a significant decrease in performance.

Answer 83

Scalability

Question 84

Blank: The algorithm should consistently deliver correct results under different conditions and environments.

Answer 84

Reliability

Question 85

Blank: Striving for the most efficient solution within the given problem constraints.

Answer 85

Optimality

Question 86

Blank: Capable of handling unexpected inputs or errors gracefully without crashing.

Answer 86

Robustness

Question 87

Blank: Ideally, it can be applied to a range of related problems with minimal adjustments.

Answer 87

Adaptability

Question 88

Blank: Keeping the algorithm as simple as possible while meeting its requirements, avoiding unnecessary complexity.

Answer 88

Simplicity

Question 89

The amount of time required to complete an algorithm’s execution is called blank.

Answer 89

time complexity

Question 90

The blank is used to represent an algorithm’s time complexity

Answer 90

big O notation

Question 91

The blank for describing time complexity, in this case, is big O notation.

Answer 91

asymptotic notation

Question 92

The blank is calculated primarily by counting the number of steps required to complete the execution

Answer 92

time complexity

Question 93

The blank is generally considered because it is the maximum time required for any given input size.

Answer 93

worst-time complexity

Question 94

The amount of space an algorithm requires to solve a problem and produce an output is called its blank.

Answer 94

space complexity

Question 95

Space complexity, like time complexity, is expressed in blank.

Answer 95

big O notation

Question 96

The space is required for an algorithm for the following reasons:

Answer 96

To store program instructions.
To store track of constant values.
To store track of variable values.
To store track of function calls, jumping statements, and so on.

Question 97

Space Complexity = Blank + Blank

Answer 97

Auxiliary Space + Input Size

Question 98

5 Advantages of Algorithms:

Answer 98

Efficiency
Reproducibility
Problem-solving
Scalability
Automation

Question 99

5 Disadvantages of Algorithms:

Answer 99

Complexity:
Limitations:
Resource Intensive:
Inaccuracy:
Maintenance:

Question 100

An blank is a structured and ordered set of instructions to do calculations and perform operations.

Answer 100

algorithm

Question 101

The expected inputs of an algorithm must be blank to ensure its correctness, predictability, and repeatability.

Answer 101

well-defined

Question 102

Well-defined inputs ensure that the algorithm’s behavior is blank, which means, that the same input will always produce the same output.

Answer 102

deterministic

Question 103

Blank help prevent incorrect implementations and misunderstanding of the algorithm’s requirements.

Answer 103

Unambiguous inputs

Question 104

With well-defined inputs, it is easier to blank the algorithm based on the characteristics of the input.

Answer 104

optimize

Question 105

The outputs of an algorithm should be blank to ensure that the algorithm produces the intended and accurate result for a given set of inputs.

Answer 105

well-defined

Question 106

Well-defined outputs avoid blank and guarantees that the algorithm solves the problem correctly.

Answer 106

ambiguity

Question 107

Well-defined outputs allow you to optimize the algorithm further to achieve the results blank.

Answer 107

more efficiently

Question 108

Ambiguity in the algorithm’s description can lead to blank and blank. That is why it is important for an algorithm to be unambiguous.

Answer 108

incorrect implementations and unreliable results

Question 109

Unambiguity allows the algorithm to be blank i.e., the same input produces the same output, which makes debugging an implementation easier

Answer 109

predictable

Question 110

Unambiguity is also easier to be blank and used widely for different applications.

Answer 110

standardized

Question 111

While implementing unambiguous algorithms, you can focus more on blank rather than handling unexpected errors and edge cases.

Answer 111

optimizations

Question 112

The algorithm should end after a blank amount of time, and it should have a limited number of instructions.

Answer 112

finite

Question 113

A blank ensures that it will eventually stop executing and produce a result.

Answer 113

finite algorithm

Question 114

An blank would never reach a conclusion, which is impractical in real-world scenarios where computation cannot be performed infinitely.

Answer 114

infinite algorithm

Question 115

The blank can be analyzed in the case of a finite algorithm which is important for performing further optimizations.

Answer 115

time and space complexity

Question 116

A blank can be easily ported to different programming languages and platforms, making it more adaptable and usable across various environments.

Answer 116

language-independent algorithm

Question 117

Being language-independent also makes an algorithm blank which means it can be implemented easily using newer programming languages.

Answer 117

future-proof

Question 118

It also makes it easier to compare the algorithm’s blank using different programming languages.

Answer 118

performance

Question 119

An algorithm should be blank because feasibility indicates that it is practical and capable of being executed within reasonable constraints and resources.

Answer 119

feasible

Question 120

blank can make an algorithm unusable in real-world scenarios.

Answer 120

excessive execution times

Question 121

Feasible algorithms can be easily implemented using blank infrastructure without using specialized resources.

Answer 121

existing hardware

Question 122

Feasible algorithms are adopted easily for usage across different fields due to its blank.

Answer 122

practical hardware requirements

Question 123

Sorting Algorithms: Blank and blank are efficient but can be complex to implement and understand.

Answer 123

Quick sort and merge sort

Question 124

Graph Algorithms: Blank is powerful for shortest path problems but requires significant memory.

Answer 124

Dijkstra’s algorithm

Question 125

Cryptographic Algorithms: Blank is secure but computationally intensive, making it less efficient for large-scale data.

Answer 125

RSA encryption

Question 126

It is the approach that comes first to mind when solving a problem. It is the most basic approach to solving a problem.

Answer 126

Brute-force Algorithm

Question 127

The blank searches for a particular element or a set of elements in a data structure. It can be linear search, binary search or any other search algorithm.

Answer 127

searching algorithm

Question 128

Blank sort a data structure according to a set of rules. Generally, we use them to sort elements in increasing or decreasing order. These include bubble sort, insertion sort, and more.

Answer 128

Sorting algorithms

Question 129

The blank uses the concept of recursion. It breaks a problem into more minor problems and calls the same function repeatedly for those sub-problems. It continues to do so until it reaches a base case that terminates the function provided the given conditions are met.

Answer 129

recursive algorithm

Question 130

Blank searches for all the possible solutions. For each path, we backtrack to the first failure point of that path and then search again for the possible solution in the next path until we find the desired solution. The algorithm takes more amount of time.

Answer 130

Backtracking algorithm

Question 131

Blank divide a problem set into smaller subsets, solve each separately, and then combine them for the final solution of the main problem. These include merge sort, quick sort, and more.

Answer 131

Divide and Conquer algorithms

Question 132

Blankj look for the best possible solution at each step and continue with that to obtain the final solution. The solutions obtained by this algorithm may or may not be optimal, but it computes solutions relatively quickly. These include algorithms like topological sort, selection sort, and more.

Answer 132

Greedy algorithms

Question 133

A Blank uses the already computed results to avoid the repetition of the same calculations. This algorithm guarantees an optimal solution to the problem.

Answer 133

Dynamic Programming algorithm

Question 134

A blank employs random integers to choose what action to take at any point in its logic. Due to the added randomness, the output can be different for the same inputs on different runs. It is commonly used in cryptographic algorithms to ensure safety. It also helps you avoid worst-case scenarios that a deterministic algorithm may run into.

Answer 134

randomized algorithm

Question 135

The amount of time an algorithm needs to run entirely, depending on the size of the input given, is called the time complexity of an algorithm.

Answer 135

TIme complexity

Question 136

The measure of the memory required by an algorithm to run entirely, depending on the size of the input given, is called the space complexity of an algorithm.

Answer 136

Space complexity

Question 137

Blank: Algorithms provide systematic and optimized approaches to solving problems, ensuring that solutions are obtained with minimal time and resource usage.

Answer 137

Efficiency

Question 138

Blank: Algorithms are well-defined and deterministic, producing the same output for a given set of inputs consistently. This reproducibility ensures reliable results and easy verification.

Answer 138

Reproducibility

Question 139

Blank: Well-designed algorithms can handle large problem sizes, making them suitable for various applications, including big data processing and complex computations.

Answer 139

Scalability

Question 140

Blank: Algorithms provide an blank over complicated processes by describing them with a set of clear and concise instructions, which makes it easy for you to understand them.

Answer 140

Abstraction

Question 141

Blank: Some algorithms can be complex and difficult to understand or implement.

Answer 141

Complexity

Question 142

Blank: Developing and optimizing algorithms can be time-intensive.

Answer 142

Time-Consuming:

Question 143

Blank: Some algorithms may not scale well with increased data or input size.

Answer 143

Scalability

Question 144

Blank: Not all algorithms are efficient; some may have high time or space complexity.

Answer 144

Efficiency:

Question 145

Blank: Algorithms may require frequent updates and maintenance as requirements change.

Answer 145

Maintenance:

Question 146

Blank: Algorithms are often tailored to specific problems and may not be easily adaptable.

Answer 146

Problem-Specific:

Question 147

Blank: Certain algorithms require significant memory, affecting performance.

Answer 147

Space Consumption:

Question 148

What are the 3 algorithm characteristics?

Answer 148

The three key characteristics of an algorithm are correctness, efficiency, and clarity.

Question 149

Blank ensures the algorithm solves the problem accurately, blank focuses on optimal use of time and resources, and blank makes the algorithm easy to understand and implement.

Answer 149

Correctness
efficiency
clarity

Question 150

What are the characteristics of algorithm and flowchart?

Answer 150

Both algorithms and flowcharts should exhibit clarity, correctness, and efficiency.

Question 151

What are the 5 properties of algorithm?

Answer 151

The 5 properties of an algorithm are well-defined inputs, well-defined outputs, unambiguity, finiteness, language independence, and feasibility.

Question 152

Blank visually map your process or system, so you can uncover opportunities to improve efficiency and performance. Whether you are improving an existing process or implementing a new one, a blank will make the task easier.

Answer 152

Data flow diagrams (DFDs)

Question 153

A data flow diagram shows the way blank flows through a process or system.

Answer 153

information

Question 154

DFDs are built using blank and blank to describe various entities and their relationships.

Answer 154

standardized symbols and notation

Question 155

Blank focus on what happens in a particular information flow: what information is being transmitted, what entities are receiving that info, what general processes occur, etc.

Answer 155

Logical data flow diagrams

Question 156

The processes described in a logical DFD are blank—a logical DFD doesn’t delve into the technical aspects of a process or system, such as how the process is constructed and implemented

Answer 156

business activities

Question 157

Blank focus on how things happen in an information flow.

Answer 157

Physical data flow diagrams

Question 158

Physical data flow diagrams specify the software, hardware, files, and people involved in an information flow. A detailed physical data flow diagram can facilitate the development of the code needed to implement a blank.

Answer 158

data system

Question 159

Both physical and logical data flow diagrams can describe the blank information flow. In coordination they provide more detail than either diagram would independently. As you decide which to use, keep in mind that you may need both.

Answer 159

same

Question 160

Data flow diagrams are also categorized by blank

Answer 160

level

Question 161

Blank, also known as context diagrams, are the most basic data flow diagrams. They provide a broad view that is easily digestible but offers little detail.

Answer 161

Level 0 DFDs,

Question 162

Level 0 data flow diagrams show a blank and its connections to external entities.

Answer 162

single process node

Question 163

Blank are still a general overview, but they go into more detail than a context diagram.

Answer 163

Level 1 DFDs

Question 164

In level 1 DFD, the single process node from the context diagram is broken down into blank. As these processes are added, the diagram will need additional data flows and data stores to link them together.

Answer 164

sub-processes

Question 165

Blank simply break processes down into more detailed sub-processes.

Answer 165

Level 2+ DFDs

Question 166

In theory, DFDs could go beyond blank, but they rarely do. Blank data flow diagrams are detailed enough that it doesn’t usually make sense to break them down further.

Answer 166

level 3

Question 167

There are four basic elements of a data flow diagram: blank, blank, blank, and blank

Answer 167

processes, data stores, external entities, and data flows.

Question 168

5 Steps to create a DFD

Answer 168

1. Identify major inputs and outputs in your system
2. Build a context diagram
3. Expand the context diagram into a level 1 DFD
4. Expand to a level 2+ DFD
5. Confirm the accuracy of your final diagram

Question 169

Nearly every process or system begins with blank from an external entity and ends with the blank of data to another entity or database. Identifying such inputs and outputs gives a macro view of your system—it shows the broadest tasks the system should achieve. The rest of your DFD will be built on these elements, so it is crucial to know them early on.

Answer 169

input
output

Question 170

Once you’ve identified the major inputs and outputs, building a blank is simple. Draw a single process node and connect it to related external entities. This node represents the most general process that information follows to go from input to output.

Answer 170

context diagram

Question 171

In your level 1 data flow diagram, you should include blank, major databases, and all external entities.

Answer 171

several process nodes

Question 172

To enhance the detail of your data flow diagram, follow the same process as in step 3. The processes in your level 1 DFD can be broken down into more specific blank. Once again, ensure you add any necessary data stores and flows—at this point, you should have a fairly detailed breakdown of your system.

Answer 172

sub-processes

Question 173

Blank – Also known as actors, sources or sinks, and terminators, external entities produce and consume data that flows between the entity and the system being diagrammed

Answer 173

External Entity

Question 174

Blank – An activity that changes or transforms data flows. Since they transform incoming data to outgoing data, all processes must have inputs and outputs on a DFD.

Answer 174

Process

Question 175

Blank – A blank does not generate any operations but simply holds data for later access.

Answer 175

Data Store

Question 176

Blank – Movement of data between external entities, processes and data stores is represented with an arrow symbol, which indicates the direction of flow.

Answer 176

Data Flow

Question 177

An blank describes a sequence of steps to solve a computational problem or perform a calculation.

Answer 177

algorithm

Question 178

A blank specifies an input, a question about the input that can be answered using a computer, and the desired output.

Answer 178

computational problem

Question 179

A computational problem is a problem that can be solved using a blank. A computational problem specifies the problem input, a question to be answered, and the desired output.

Answer 179

computer

Question 180

Given two DNA sequences from different individuals, what is the longest shared sequence of nucleotides?

Answer 180

Longest common substring problem: A longest common substring algorithm determines the longest common substring that exists in two input strings.

Question 181

Given a product ID and a sorted array of all in-stock products, is the product in stock and what is the product’s price?

Answer 181

Binary search: The binary search algorithm is an efficient algorithm for searching a list. The list’s elements must be sorted and directly accessible (such as an array).

Question 182

Given a user’s current location and desired location, what is the fastest route to walk to the destination?

Answer 182

Dijkstra’s shortest path: Dijkstra’s shortest path algorithm determines the shortest path from a start vertex to each vertex in a graph

Question 183

Blank are a set of problems for which no known efficient algorithm exists.

Answer 183

NP-complete problems

Question 184

NP-complete problems have the following characteristics:

Answer 184

No efficient algorithm has been found to solve an NP-complete problem.
No one has proven that an efficient algorithm to solve an NP-complete problem is impossible.
If an efficient algorithm exists for one NP-complete problem, then all NP-complete problems can be solved efficiently.

Question 185

An efficient algorithm is generally one whose runtime increases no more than blank with respect to the input size. In contrast, an algorithm with an exponential runtime is not efficient

Answer 185

polynomially

Question 186

Blank not only define how data is organized and stored, but also the operations performed on the blank.

Answer 186

Data structures

Question 187

While common operations include inserting, removing, and searching for data, the algorithms to implement those operations are typically specific to each blank

Answer 187

data structure

Question 188

Some algorithms utilize data structures to store and organize data during the blank.

Answer 188

algorithm execution

Question 189

An blank is a data type described by predefined user operations, such as “insert data at rear,” without indicating how each operation is implemented.

Answer 189

abstract data type (ADT)

Question 190

An ADT can be implemented using different underlying blank. However, a programmer need not have knowledge of the underlying implementation to use an ADT.

Answer 190

data structures

Question 191

A blank is an ADT for holding ordered data.

Answer 191

list

Question 192

list - Common underlying data structures

Answer 192

Array, Linked List

Question 193

A blank is an ADT for holding ordered data and allowing indexed access.

Answer 193

dynamic array

Question 194

A blank is an ADT in which items are only inserted on or removed from the top of a stack.

Answer 194

stack

Question 195

Stack - Common underlying data structures

Answer 195

Linked list

Question 196

A blank is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.

Answer 196

queue

Question 197

Queue, Deque- Common underlying data structures

Answer 197

Linked list

Question 198

A blank is an ADT in which items can be inserted and removed at both the front and back.

Answer 198

deque (pronounced “deck” and short for double-ended queue)

Question 199

A blank is an ADT for storing items in which the order does not matter and duplicate items are allowed.

Answer 199

bag

Question 200

Bag - Common underlying data structures

Answer 200

Array, linked list

Question 201

A blank is an ADT for a collection of distinct items.

Answer 201

set

Question 202

Set - Common underlying data structures

Answer 202

Binary search tree, hash table

Question 203

A blank is a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.

Answer 203

priority queue

Question 204

Priority Queue - Common underlying data structures

Answer 204

Heap

Question 205

A blank is an ADT that associates (or maps) keys with values

Answer 205

dictionary

Question 206

Dictionary - Common underlying data structures

Answer 206

Hash table, binary search tree

Question 207

Items are ordered based on how items are added. Duplicate items are allowed.

Answer 207

List

Question 208

Items are not ordered. Duplicate items are not allowed.

Answer 208

Set

Question 209

Items are ordered based on items’ priority. Duplicate items are allowed.

Answer 209

Priority Queue

Question 210

Items are not ordered. Duplicate items are allowed.

Answer 210

bag

Question 211

Blank means to have a user interact with an item at a high-level, with lower-level internal details hidden from the user.

Answer 211

Abstraction

Question 212

ADTs support blank by hiding the underlying implementation details and providing a well-defined set of operations for using the ADT.

Answer 212

abstraction

Question 213

Using abstract data types enables programmers or algorithm designers to focus on higher-level operations and algorithms, thus improving programmer blank.

Answer 213

efficiency

Question 214

Knowledge of the underlying blank is needed to analyze or improve the runtime efficiency.

Answer 214

implementation

Question 215

The blank ADTs can be implemented using many different underlying data structures, including arrays, singly-linked lists, and doubly-linked lists

Answer 215

list

Question 216

Knowledge of an ADT’s underlying implementation is needed to analyze the blank.

Answer 216

runtime efficiency

Question 217

Most programming languages provide blank that implement common abstract data types.

Answer 217

standard libraries

Question 218

Some languages allow programmers to choose the underlying blank used for the ADTs.

Answer 218

data structure

Question 219

Programming languages may use a specific data structure to implement each blank, or may automatically choose the underlying data-structure.

Answer 219

ADT

Question 220

Python standard library - Common supported ADTs

Answer 220

list, set, dict, deque

Question 221

C++ Standard template library (STL) - Common supported ADTs

Answer 221

vector, list, deque, queue, stack, set, map

Question 222

Java collections framework (JCF) - Common supported ADTs

Answer 222

Collection, Set, List, Map, Queue, Deque

Question 223

Python, C++, and Java all provide built-in support for a blank ADT.

Answer 223

deques, lists, sets, and dictionaries (or maps)

Question 224

The blank used to implement ADTs may vary between implementations. Some programming languages allow programmers to select a specific implementation. Ex: Java’s list ADTs can be implemented using arrays or linked lists.

Answer 224

underlying data structures

Question 225

Many blank, which are not built into the programming language standard, implement ADTs.

Answer 225

third-party libraries

Question 226

Given data represented as some quantity of bits, blank transforms the data to use fewer bits

Answer 226

compression

Question 227

Compressed data uses less blank and can be communicated faster than uncompressed data.

Answer 227

storage

Question 228

The basic idea of compression is to encode frequently-occurring items using blank. Ex: Uncompressed ASCII characters use 8 bits each, but compression uses fewer than 8 bits for more frequently occurring characters

Answer 228

fewer bits

Question 229

Prior to compression, a blank must be built for an input string. Such a table contains each distinct character from the input string and each character’s number of occurrences.

Answer 229

character frequency table

Question 230

Programming languages commonly provide a blank to store the character frequency table.

Answer 230

dictionary or map object

Question 231

Blank is a common compression technique that assigns fewer bits to frequent items, using a binary tree.

Answer 231

Huffman coding

Question 232

Blank have two data members: a character from the input and an integer frequency for that character.

Answer 232

Leaf nodes

Question 233

Blank have left and right child nodes, along with an integer frequency value that represents the sum of the left and right child frequencies.

Answer 233

Internal nodes

Question 234

A blank can be built from a character frequency table

Answer 234

Huffman tree

Question 235

Implementations commonly use the same blank for leaf and internal nodes, instead of two distinct structures. Each node has a frequency, character, and 2 child pointers. The child pointers are set to null for leaves and the character is set to 0 for internal nodes.

Answer 235

node structure

Question 236

Huffman codes for each character are built from a blank. Each character corresponds to a leaf node. The Huffman code for a character is built by tracing a path from the root to that character’s leaf node, appending 0 when branching left or 1 when branching right.

Answer 236

Huffman tree

Question 237

To compress an input string, the Huffman codes are first obtained for blank. Then blank of the input string is processed, and corresponding bit codes are concatenated to produce the compressed result.

Answer 237

each character

Question 238

To blank Huffman code data, one can use a Huffman tree and trace the branches for each bit, starting at the root. When the final node of the branch is reached, the result has been found. The process continues until the entire item is decompressed

Answer 238

decompress

Question 239

In practice, solving a problem in the optimal or most accurate way may require more computational resources than are available or feasible. Algorithms implemented for such problems often use a blank: A technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.

Answer 239

heuristic

Question 240

A heuristic technique used for numerical computation may sacrifice accuracy to gain blank.

Answer 240

speed

Question 241

A blank is an algorithm that quickly determines a near optimal or approximate solution.

Answer 241

heuristic algorithm

Question 242

A heuristic algorithm to solve the blank can choose to always take the most valuable item that fits in the knapsack’s remaining space. Such an algorithm uses the heuristic of choosing the highest value item, without considering the impact on the remaining choices. While the algorithm’s simple choices are aimed at optimizing the total value, the final result may not be optimal.

Answer 242

0-1 knapsack problem

Question 243

A blank is an algorithm that modifies a data structure based on how that data structure is used. Ex: Many self-adjusting data structures, such as red-black trees and AVL trees, use a self-adjusting heuristic to keep the tree balanced. Tree balancing organizes data to allow for faster access.

Answer 243

self-adjusting heuristic

Question 244

The blank problem imposes the restriction that each item can be added at most once. A heuristic algorithm to solve the knapsack problem first sorts items in descending order by value, and then iteratively places the most valuable items that fit within the remaining space into the knapsack until no more items can be added.

Answer 244

0-1 knapsack

Question 245

To construct a Python program to solve the knapsack problem using a heuristic, two classes are defined:

Answer 245

An Item class to store each item’s weight and value

A Knapsack class to store the knapsack’s maximum predetermined weight and the list of items the knapsack will hold

Question 246

A blank solves a problem by assuming that the optimal choice at a given moment during the algorithm will also be the optimal choice overall.

Answer 246

greedy algorithm

Question 247

Greedy algorithms tend to be blank, but certain types of problems exist where greedy algorithms don’t find the best or optimal solution.

Answer 247

efficient

Question 248

Greedy algorithms produce both efficient and optimal solutions for many problems, including the blank and blank

Answer 248

fractional knapsack problem and the activity selection problem.

Question 249

The blank is similar to the regular knapsack problem, except that fractional pieces of any item can be selected.

Answer 249

fractional knapsack problem

Question 250

The blank of the fractional knapsack problem can be achieved by first sorting the items by their value-to-weight ratio, in descending order. The items are then added to the knapsack in that order, taking whole units of items until only a fraction of the next item is possible. The highest fraction of that item that will fit in the knapsack is taken, and the algorithm ends.

Answer 250

optimal solution

Question 251

The blank defines a set of “activities” (Ex: Tourist activities on a vacation), as well as when these activities start and finish (Ex: Time of day).

Answer 251

activity selection problem

Question 252

The blank of the activity selection problem will schedule the most activities possible without having any time conflicts.

Answer 252

optimal solution

Question 253

The blank starts by sorting the activities, using the activity finish times as the sorting key, from earliest to latest. The first activity in the list is selected and added to the set of chosen activities. The second activity in the sorted list is selected only if the activity does not conflict with the first activity. If the second activity does conflict with the first, then the activity is not selected. The third activity in the sorted list is selected only if the activity does not conflict with the second activity. The process continues until the entire sorted list of activities is processed.

Answer 253

greedy algorithm

Question 254

class Activity:
def __init__(self, name, initial_start_time, initial_finish_time):
self.name = name
self.start_time = initial_start_time
self.finish_time = initial_finish_time

def conflicts_with(self, other_activity):
    # No conflict exists if this activity's finish_time comes
    # at or before the other activity's start_time
    if self.finish_time <= other_activity.start_time:
        return False
        
    # No conflict exists if the other activity's finish_time
    # comes at or before this activity's start_time
    elif other_activity.finish_time <= self.start_time:
        return False
        
    # In all other cases the two activity's conflict with each
    # other
    else:
        return True

Main program to test Activity objects
activity_1 = Activity(‘History museum tour’, 9, 10)
activity_2 = Activity(‘Morning mountain hike’, 9, 12)
activity_3 = Activity(‘Boat tour’, 11, 14)

print(‘History museum tour conflicts with Morning mountain hike:’,
activity_1.conflicts_with(activity_2))
print(‘History museum tour conflicts with Boat tour:’,
activity_1.conflicts_with(activity_3))
print(‘Morning mountain hike conflicts with Boat tour:’,
activity_2.conflicts_with(activity_3))

Answer 254

Activity class for the activity selection problem.

Question 255

from operator import attrgetter

def activity_selection(activities):

# Start with an empty list of selected activities
chosen_activities = []

# Sort the list of activities in increasing order of finish_time
activities.sort(key = attrgetter("finish_time"))

# Select the first activity, and add it to the chosen_activities list
current = activities[0]
chosen_activities.append(current)

# Process all the remaining activities, in order
for i in range(1, len(activities)):

    # If the next activity does not conflict with
    # the most recently selected activity, select the
    # next activity
    if not activities[i].conflicts_with(current):
        chosen_activities.append(activities[i])
        current = activities[i]
        
# The chosen_activities list is an optimal list of
# activities with no conflicts
return chosen_activities

Program to test Activity Selection greedy algorithm. The
# start_time and finish_time are represented with integers
# (ex. “20” is 20:00, or 8:00 PM).
activity_1 = Activity(‘Fireworks show’, 20, 21)
activity_2 = Activity(‘Morning mountain hike’, 9, 12)
activity_3 = Activity(‘History museum tour’, 9, 10)
activity_4 = Activity(‘Day mountain hike’, 13, 16)
activity_5 = Activity(‘Night movie’, 19, 21)
activity_6 = Activity(‘Snorkeling’, 15, 17)
activity_7 = Activity(‘Hang gliding’, 14, 16)
activity_8 = Activity(‘Boat tour’, 11, 14)

activities = [ activity_1, activity_2, activity_3, activity_4,
activity_5, activity_6, activity_7, activity_8 ]

Use the activity_selection() method to get a list of optimal
# activities with no conflicts.
itinerary = activity_selection(activities)
for activity in itinerary:
# Output the activity’s information.
print(‘%s - start time: %d, finish time: %d’ %
(activity.name, activity.start_time, activity.finish_time))

Answer 255

activity_selection() function.

Question 256

An individual item with a weight and value
class Item:
def __init__(self, item_weight, item_value):
self.weight = item_weight
self.value = item_value
self.fraction = 1.0

The knapsack that contains a list of items and a maximum
# total weight
class Knapsack:
def __init__(self, weight, items):
self.max_weight = weight
self.item_list = items

A key function to be used to sort the items
def value_to_weight_ratio(item):
return item.value / item.weight

The Fractional Knapsack algorithm.
def fractional_knapsack(knapsack, item_list):
# Sort the items in descending order based on value/weight
item_list.sort(key = value_to_weight_ratio, reverse = True)

remaining = knapsack.max_weight
for item in item_list:
    # Check if the full item can fit into the knapsack or
    # only a fraction
    if item.weight <= remaining:
        # The full item will fit. 
        knapsack.item_list.append(item)
        remaining = remaining - item.weight

    else:
        # Only a fractional part of the item will fit. Add that
        # fraction of the item, and then exit.
        item.fraction = remaining / item.weight
        knapsack.item_list.append(item)
        break

Answer 256

Fractional knapsack greedy algorithm.

Question 257

from operator import attrgetter

class Item:
def __init__(self, item_weight, item_value):
self.weight = item_weight
self.value = item_value

class Knapsack:
def __init__(self, weight, items):
self.max_weight = weight
self.item_list = items

def knapsack_01(knapsack, item_list):
# Sort the items in descending order based on value
item_list.sort(key = attrgetter(‘value’), reverse = True)

remaining = knapsack.max_weight
for item in item_list:
    if item.weight <= remaining:
        knapsack.item_list.append(item)
        remaining = remaining - item.weight

Main program
item_1 = Item(6, 25)
item_2 = Item(8, 42)
item_3 = Item(12, 60)
item_4 = Item(18, 95)
item_list = [item_1, item_2, item_3, item_4]
initial_knapsack_list = []

max_weight = int(input(‘Enter maximum weight the knapsack can hold: ‘))

knapsack = Knapsack(max_weight, initial_knapsack_list)
knapsack_01(knapsack, item_list)

print (‘Objects in knapsack’)
i = 1
sum_weight = 0
sum_value = 0

for item in knapsack.item_list:
sum_weight += item.weight
sum_value += item.value
print (‘%d: weight %d, value %d’ % (i, item.weight,item.value))
i += 1
print()

print(‘Total weight of items in knapsack: %d’ % sum_weight)
print(‘Total value of items in knapsack: %d’ % sum_value)

Answer 257

0-1 Knapsack problem heuristic.

Question 258

Blank is a problem solving technique that splits a problem into smaller subproblems, computes and stores solutions to subproblems in memory, and then uses the stored solutions to solve the larger problem.

Answer 258

Dynamic programming

Question 259

Blank can be computed with an iterative approach that stores the 2 previous terms, instead of making recursive calls that recompute the same term many times over.

Answer 259

Fibonacci numbers

Question 260

Blank avoids recomputing previously computed results by storing and reusing such results.

Answer 260

Dynamic programming

Question 261

The blank algorithm takes 2 strings as input and determines the longest substring that exists in both strings. The algorithm uses dynamic programming.

Answer 261

longest common substring

Question 262

LongestCommonSubstring(str1, str2) {
matrix = Allocate str1⇢length by str2⇢length matrix

for (row = 0; row < str1⇢length; row++) {
for (col = 0; col < str2⇢length; col++) {
// Check if the characters match
if (str1[row] == str2[col]) {
// Get the value in the cell that’s up and to the
// left, or 0 if no such cell
upLeft = 0
if (row > 0 && col > 0)
upLeft = matrix[row - 1][col - 1]

        // Set the value for this cell
        matrix[row][col] = 1 + upLeft
     }
     else
        matrix[row][col] = 0
  }    }

substringLength = Maximum value in matrix
rowIndex = Row index of maximum value in matrix
startIndex = rowIndex - substringLength + 1
return str1⇢substr(startIndex, substringLength)

Answer 262

Longest common substring algorithm.

Question 263

The runtime complexity of the iterative version of Fibonacci numbers

Answer 263

O(N)

Question 264

FibonacciNumber(termIndex) {
if (termIndex == 0) {
return 0
}
previous = 0
current = 1
i = 1
while (i < termIndex) {
next = previous + current
previous = current
current = next
i = i + 1
}
return current
}

Answer 264

FibonacciNumber iterative approach

Question 265

The longest common substring algorithm operates on two strings of length N and M. For each of the N characters in the first string, M matrix entries are computed, making the runtime complexity what

Answer 265

O(N * M)

Question 266

Since an N x M integer matrix is built, the space complexity is blank

Answer 266

O(N*M)

Question 267

A real-world application of the longest common substring algorithm is to find common substrings in blank. Ex: Common substrings between 2 different DNA sequences may represent shared traits. DNA strings consist of characters C, T, A, and G.

Answer 267

DNA strings

Question 268

The longest common substring algorithm can be implemented such that only the previously computed row and the largest matrix entry’s location and value are stored in memory. With this optimization, the space complexity is reduced to blank

Answer 268

O(N)

Question 269

Dynamic programming is a technique where solutions to subproblems are stored in blank and used to quickly find the solution to the full problem.

Answer 269

memory

Question 270

The longest common substring problem is solved efficiently using blank. A matrix, a list of lists, stores the length of the longest common substring found in two strings as the strings’ characters are examined. Matrix element (i, j) is assigned with zero if the first string’s ith character doesn’t match the second string’s jth character. If the two characters do match, then matrix element (i, j) is assigned with the matrix element (i-1, j-1) +1.

Answer 270

dynamic programming

Question 271

def longest_common_substring(str1, str2):

# Create the matrix as a list of lists.
matrix = []
for i in range(len(str1)):
    # Each row is started as a list of zeros.
    matrix.append([0] * len(str2))

# Variables to remember the largest value, and the position it
# occurred at.
max_value = 0
max_value_row = 0
max_value_col = 0
for row in range(len(str1)):
    for col in range(len(str2)):
    
        # Check if the characters match
        if str1[row] == str2[col]:
            # Get the value in the cell that's up and to the 
            # left, or 0 if no such cell
            up_left = 0
            if row > 0 and col > 0:
                up_left = matrix[row - 1][col - 1]
            
            # Set the value for this cell
            matrix[row][col] = 1 + up_left
            if matrix[row][col] > max_value:
                max_value = matrix[row][col]
                max_value_row = row
                max_value_col = col
        else:
            matrix[row][col] = 0

# The longest common substring is the substring
# in str1 from index max_value_row - max_value + 1, 
# up to and including max_value_col.
start_index = max_value_row - max_value + 1
return str1[start_index : max_value_row + 1]

Answer 271

Dynamic programming algorithm for the longest common substring problem.

Question 272

def longest_common_substring_optimized(str1, str2):
# Create one row of the matrix.
matrix_row = [0] * len(str2)

# Variables to remember the largest value, and the row it
# occurred at.
max_value = 0
max_value_row = 0
for row in range(len(str1)):
    # Variable to hold the upper-left value from the
    # current matrix position.
    up_left = 0
    for col in range(len(str2)):
        # Save the current cell's value; this will be up_left
        # for the next iteration.
        saved_current = matrix_row[col]
    
        # Check if the characters match
        if str1[row] == str2[col]:
            matrix_row[col] = 1 + up_left
            
            # Update the saved maximum value and row,
            # if appropriate.
            if matrix_row[col] > max_value:
                max_value = matrix_row[col]
                max_value_row = row
        else:
            matrix_row[col] = 0
            
        # Update the up_left variable
        up_left = saved_current

# The longest common substring is the substring
# in str1 from index max_value_row - max_value + 1, 
# up to and including max_value_row.
start_index = max_value_row - max_value + 1
return str1[start_index : max_value_row + 1]

Answer 272

A space-saving optimized version of the longest common substring algorithm.

Question 273

A blank can be used to solve the longest common subsequence problem.

Answer 273

dynamic programming matrix