Introduction - Chapter 1 Flashcards
1
Q
A blank is a way of organizing, storing, and performing operations on data.
A
data structure
2
Q
A blank is the data structure that stores subitems, often called fields, with a name associated with each subitem.
A
record
3
Q
An blank is a data structure that stores an ordered list of items, where each item is directly accessible by a positional index.
A
array
4
Q
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.
A
linked list
5
Q
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.
A
binary tree
6
Q
A blank is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array.
A
hash table
7
Q
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.
A
max-heap
8
Q
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.
A
min-heap
9
Q
A blank is a data structure for representing connections among items, and consists of vertices connected by edges.
A
graph
10
Q
A blank represents an item in a graph.
A
vertex
11
Q
An blank represents a connection between two vertices in a graph.
A
edge
12
Q
A linked list stores an blank of items
A
ordered list
13
Q
A node in blank can have zero, one, or two children.
A
binary tree
14
Q
The data stored in a blank can be a record with multiple subitems.
A
list node
15
Q
Items stored in an array can be accessed using a blank
A
positional index
16
Q
Inserting an item at the end of a 999-item array requires how many items to be shifted?
A
0
17
Q
Inserting an item at the end of a 999-item linked list requires how many items to be shifted?
A
0
18
Q
Inserting an item at the beginning of a 999-item array requires how many items to be shifted?
A
999
19
Q
Inserting an item at the beginning of a 999-item linked list requires how many items to be shifted?
A
0
20
Q
An blank is a set of commands that must be followed for a computer to perform calculations or other problem-solving operations.
A
algorithm
21
Q
According to its formal definition, an algorithm is a blank carried out in a specific order to perform a particular task.
A
finite set of instructions
22
Q
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.
A
entire program or code
23
Q
Input -> blank -> output
A
algorithm
24
Q
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.
A
problem
25
An blank is defined as a step-by-step process that will be designed for a problem.
algorithm
26
After designing an algorithm, the algorithm is given the necessary and desired blank.
inputs
27
The input will be passed to the blank, producing the desired output.
processing unit
28
The outcome or result of the program is referred to as the blank.
output
29
Blank are step-by-step procedures designed to solve specific problems and perform tasks efficiently in the realm of computer science and mathematics.
Algorithms
30
Algorithms take blank, which can be in various formats, such as numbers, text, or images.
input data
31
The algorithm blank the input data through a series of logical and mathematical operations, manipulating and transforming it as needed.
processes
32
After the processing is complete, the algorithm produces an blank, which could be a result, a decision, or some other meaningful information.
output
33
A key aspect of algorithms is their blank, aiming to accomplish tasks quickly and with minimal resources.
efficiency
34
Algorithm designers constantly seek ways to blank their algorithms, making them faster and more reliable.
optimize
35
Algorithms are implemented in various blank, enabling computers to execute them and produce desired outcomes.
programming languages
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.
scalability
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.
feasible
38
Algorithms are used in blank and blank to find patterns in big datasets and forecast outcomes.
data analysis
machine learning
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.
support vector machines,
decision trees, and
neural networks
40
Blank safeguard data by using encryption and decryption techniques, guaranteeing safe data storage and communication
Cryptography algorithms
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.
SHA-256,
AES, and
RSA
42
blank can efficiently index and retrieve pertinent information thanks to search algorithms such as PageRank and Hummingbird.
Search engines
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.
PageRank and Hummingbird.
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.
Optimization methods
45
Blank algorithms increase productivity, reduce expenses, and optimize resources for operations and decision-making.
Optimization
46
Due to their ability to analyze medical images, forecast disease outbreaks, and recognize genetic changes, algorithms are indispensable in blank.
medical diagnostics
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
Personalized medicine
48
Algorithms help to speed up the sequencing and interpretation of blank, improving biotechnology and genomics research.
genomic data
49
Name 6 Characteristics of an Algorithm
Finiteness
Definiteness
Input
Output
Effectiveness
Generality
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.
finite
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.
definitions
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.
inputs
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.
outputs
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.
fundamental operations
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.
group of issues
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.
Brute Force Algorithm
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.
Recursive Algorithm
58
Utilized to transform data into a secure, unreadable form using cryptographic techniques, ensuring confidentiality and privacy in digital communications and transactions.
Encryption Algorithm
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.
Backtracking Algorithm
60
Designed to find a specific target within a dataset, enabling efficient retrieval of information from sorted or unsorted collections.
Searching Algorithm
61
Aimed at arranging elements in a specific order, like numerical or alphabetical, to enhance data organization and retrieval.
Sorting Algorithm
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.
Hashing Algorithm
63
Breaks a complex problem into smaller subproblems, solves them independently, and then combines their solutions to address the original problem effectively.
Divide and Conquer Algorithm
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
Greedy Algorithm
65
Stores and reuses intermediate results to avoid redundant computations, enhancing the efficiency of solving complex problems.
Dynamic Programming Algorithm
66
Utilizes randomness in its steps to achieve a solution, often used in situations where an approximate or probabilistic answer suffices.
Randomized Algorithm
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.
writing algorithms
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.
basic code constructs
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.
step-by-step fashion
70
Algorithms instruct programmers on how to blank.
write code
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.
Modularity
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.
Correctness
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.
Maintainability
74
It takes into account various logical steps to solve a real-world problem.
Functionality
75
Blank refers to an algorithm's ability to define your problem clearly.
Robustness
76
If the algorithm is difficult to understand, the designer will not explain it to the programmer.
User-friendly
77
If an algorithm is blank, it is blank to understand.
simple
78
Your algorithm should be blank if another algorithm designer or programmer wants to use it.
extensible
79
9 Qualities of a good algorithm
Efficiency
Correctness
Clarity
Scalability
Reliability
Optimality
Robustness
Adaptability
Simplicity
80
Blank: A good algorithm should perform its task quickly and use minimal resources.
Efficiency
81
Blank: It must produce the correct and accurate output for all valid inputs.
Correctness
82
Blank: The algorithm should be easy to understand and comprehend, making it maintainable and modifiable.
Clarity
83
Blank: It should handle larger data sets and problem sizes without a significant decrease in performance.
Scalability
84
Blank: The algorithm should consistently deliver correct results under different conditions and environments.
Reliability
85
Blank: Striving for the most efficient solution within the given problem constraints.
Optimality
86
Blank: Capable of handling unexpected inputs or errors gracefully without crashing.
Robustness
87
Blank: Ideally, it can be applied to a range of related problems with minimal adjustments.
Adaptability
88
Blank: Keeping the algorithm as simple as possible while meeting its requirements, avoiding unnecessary complexity.
Simplicity
89
The amount of time required to complete an algorithm's execution is called blank.
time complexity
90
The blank is used to represent an algorithm's time complexity
big O notation
91
The blank for describing time complexity, in this case, is big O notation.
asymptotic notation
92
The blank is calculated primarily by counting the number of steps required to complete the execution
time complexity
93
The blank is generally considered because it is the maximum time required for any given input size.
worst-time complexity
94
The amount of space an algorithm requires to solve a problem and produce an output is called its blank.
space complexity
95
Space complexity, like time complexity, is expressed in blank.
big O notation
96
The space is required for an algorithm for the following reasons:
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.
97
Space Complexity = Blank + Blank
Auxiliary Space + Input Size
98
5 Advantages of Algorithms:
Efficiency
Reproducibility
Problem-solving
Scalability
Automation
99
5 Disadvantages of Algorithms:
Complexity:
Limitations:
Resource Intensive:
Inaccuracy:
Maintenance:
100
An blank is a structured and ordered set of instructions to do calculations and perform operations.
algorithm
101
The expected inputs of an algorithm must be blank to ensure its correctness, predictability, and repeatability.
well-defined
102
Well-defined inputs ensure that the algorithm's behavior is blank, which means, that the same input will always produce the same output.
deterministic
103
Blank help prevent incorrect implementations and misunderstanding of the algorithm's requirements.
Unambiguous inputs
104
With well-defined inputs, it is easier to blank the algorithm based on the characteristics of the input.
optimize
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.
well-defined
106
Well-defined outputs avoid blank and guarantees that the algorithm solves the problem correctly.
ambiguity
107
Well-defined outputs allow you to optimize the algorithm further to achieve the results blank.
more efficiently
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.
incorrect implementations and unreliable results
109
Unambiguity allows the algorithm to be blank i.e., the same input produces the same output, which makes debugging an implementation easier
predictable
110
Unambiguity is also easier to be blank and used widely for different applications.
standardized
111
While implementing unambiguous algorithms, you can focus more on blank rather than handling unexpected errors and edge cases.
optimizations
112
The algorithm should end after a blank amount of time, and it should have a limited number of instructions.
finite
113
A blank ensures that it will eventually stop executing and produce a result.
finite algorithm
114
An blank would never reach a conclusion, which is impractical in real-world scenarios where computation cannot be performed infinitely.
infinite algorithm
115
The blank can be analyzed in the case of a finite algorithm which is important for performing further optimizations.
time and space complexity
116
A blank can be easily ported to different programming languages and platforms, making it more adaptable and usable across various environments.
language-independent algorithm
117
Being language-independent also makes an algorithm blank which means it can be implemented easily using newer programming languages.
future-proof
118
It also makes it easier to compare the algorithm's blank using different programming languages.
performance
119
An algorithm should be blank because feasibility indicates that it is practical and capable of being executed within reasonable constraints and resources.
feasible
120
blank can make an algorithm unusable in real-world scenarios.
excessive execution times
121
Feasible algorithms can be easily implemented using blank infrastructure without using specialized resources.
existing hardware
122
Feasible algorithms are adopted easily for usage across different fields due to its blank.
practical hardware requirements
123
Sorting Algorithms: Blank and blank are efficient but can be complex to implement and understand.
Quick sort and merge sort
124
Graph Algorithms: Blank is powerful for shortest path problems but requires significant memory.
Dijkstra's algorithm
125
Cryptographic Algorithms: Blank is secure but computationally intensive, making it less efficient for large-scale data.
RSA encryption
126
It is the approach that comes first to mind when solving a problem. It is the most basic approach to solving a problem.
Brute-force Algorithm
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.
searching algorithm
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.
Sorting algorithms
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.
recursive algorithm
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.
Backtracking algorithm
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.
Divide and Conquer algorithms
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.
Greedy algorithms
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.
Dynamic Programming algorithm
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.
randomized algorithm
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.
TIme complexity
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.
Space complexity
137
Blank: Algorithms provide systematic and optimized approaches to solving problems, ensuring that solutions are obtained with minimal time and resource usage.
Efficiency
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.
Reproducibility
139
Blank: Well-designed algorithms can handle large problem sizes, making them suitable for various applications, including big data processing and complex computations.
Scalability
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.
Abstraction
141
Blank: Some algorithms can be complex and difficult to understand or implement.
Complexity
142
Blank: Developing and optimizing algorithms can be time-intensive.
Time-Consuming:
143
Blank: Some algorithms may not scale well with increased data or input size.
Scalability
144
Blank: Not all algorithms are efficient; some may have high time or space complexity.
Efficiency:
145
Blank: Algorithms may require frequent updates and maintenance as requirements change.
Maintenance:
146
Blank: Algorithms are often tailored to specific problems and may not be easily adaptable.
Problem-Specific:
147
Blank: Certain algorithms require significant memory, affecting performance.
Space Consumption:
148
What are the 3 algorithm characteristics?
The three key characteristics of an algorithm are correctness, efficiency, and clarity.
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.
Correctness
efficiency
clarity
150
What are the characteristics of algorithm and flowchart?
Both algorithms and flowcharts should exhibit clarity, correctness, and efficiency.
151
What are the 5 properties of algorithm?
The 5 properties of an algorithm are well-defined inputs, well-defined outputs, unambiguity, finiteness, language independence, and feasibility.
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.
Data flow diagrams (DFDs)
153
A data flow diagram shows the way blank flows through a process or system.
information
154
DFDs are built using blank and blank to describe various entities and their relationships.
standardized symbols and notation
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.
Logical data flow diagrams
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
business activities
157
Blank focus on how things happen in an information flow.
Physical data flow diagrams
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.
data system
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.
same
160
Data flow diagrams are also categorized by blank
level
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.
Level 0 DFDs,
162
Level 0 data flow diagrams show a blank and its connections to external entities.
single process node
163
Blank are still a general overview, but they go into more detail than a context diagram.
Level 1 DFDs
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.
sub-processes
165
Blank simply break processes down into more detailed sub-processes.
Level 2+ DFDs
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.
level 3
167
There are four basic elements of a data flow diagram: blank, blank, blank, and blank
processes, data stores, external entities, and data flows.
168
5 Steps to create a DFD
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
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.
input
output
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.
context diagram
171
In your level 1 data flow diagram, you should include blank, major databases, and all external entities.
several process nodes
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.
sub-processes
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
External Entity
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.
Process
175
Blank – A blank does not generate any operations but simply holds data for later access.
Data Store
176
Blank – Movement of data between external entities, processes and data stores is represented with an arrow symbol, which indicates the direction of flow.
Data Flow
177
An blank describes a sequence of steps to solve a computational problem or perform a calculation.
algorithm
178
A blank specifies an input, a question about the input that can be answered using a computer, and the desired output.
computational problem
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.
computer
180
Given two DNA sequences from different individuals, what is the longest shared sequence of nucleotides?
Longest common substring problem: A longest common substring algorithm determines the longest common substring that exists in two input strings.
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?
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).
182
Given a user's current location and desired location, what is the fastest route to walk to the destination?
Dijkstra's shortest path: Dijkstra's shortest path algorithm determines the shortest path from a start vertex to each vertex in a graph
183
Blank are a set of problems for which no known efficient algorithm exists.
NP-complete problems
184
NP-complete problems have the following characteristics:
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.
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
polynomially
186
Blank not only define how data is organized and stored, but also the operations performed on the blank.
Data structures
187
While common operations include inserting, removing, and searching for data, the algorithms to implement those operations are typically specific to each blank
data structure
188
Some algorithms utilize data structures to store and organize data during the blank.
algorithm execution
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.
abstract data type (ADT)
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.
data structures
191
A blank is an ADT for holding ordered data.
list
192
list - Common underlying data structures
Array, Linked List
193
A blank is an ADT for holding ordered data and allowing indexed access.
dynamic array
194
A blank is an ADT in which items are only inserted on or removed from the top of a stack.
stack
195
Stack - Common underlying data structures
Linked list
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.
queue
197
Queue, Deque- Common underlying data structures
Linked list
198
A blank is an ADT in which items can be inserted and removed at both the front and back.
deque (pronounced "deck" and short for double-ended queue)
199
A blank is an ADT for storing items in which the order does not matter and duplicate items are allowed.
bag
200
Bag - Common underlying data structures
Array, linked list
201
A blank is an ADT for a collection of distinct items.
set
202
Set - Common underlying data structures
Binary search tree, hash table
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.
priority queue
204
Priority Queue - Common underlying data structures
Heap
205
A blank is an ADT that associates (or maps) keys with values
dictionary
206
Dictionary - Common underlying data structures
Hash table, binary search tree
207
Items are ordered based on how items are added. Duplicate items are allowed.
List
208
Items are not ordered. Duplicate items are not allowed.
Set
209
Items are ordered based on items' priority. Duplicate items are allowed.
Priority Queue
210
Items are not ordered. Duplicate items are allowed.
bag
211
Blank means to have a user interact with an item at a high-level, with lower-level internal details hidden from the user.
Abstraction
212
ADTs support blank by hiding the underlying implementation details and providing a well-defined set of operations for using the ADT.
abstraction
213
Using abstract data types enables programmers or algorithm designers to focus on higher-level operations and algorithms, thus improving programmer blank.
efficiency
214
Knowledge of the underlying blank is needed to analyze or improve the runtime efficiency.
implementation
215
The blank ADTs can be implemented using many different underlying data structures, including arrays, singly-linked lists, and doubly-linked lists
list
216
Knowledge of an ADT's underlying implementation is needed to analyze the blank.
runtime efficiency
217
Most programming languages provide blank that implement common abstract data types.
standard libraries
218
Some languages allow programmers to choose the underlying blank used for the ADTs.
data structure
219
Programming languages may use a specific data structure to implement each blank, or may automatically choose the underlying data-structure.
ADT
220
Python standard library - Common supported ADTs
list, set, dict, deque
221
C++ Standard template library (STL) - Common supported ADTs
vector, list, deque, queue, stack, set, map
222
Java collections framework (JCF) - Common supported ADTs
Collection, Set, List, Map, Queue, Deque
223
Python, C++, and Java all provide built-in support for a blank ADT.
deques, lists, sets, and dictionaries (or maps)
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.
underlying data structures
225
Many blank, which are not built into the programming language standard, implement ADTs.
third-party libraries
226
Given data represented as some quantity of bits, blank transforms the data to use fewer bits
compression
227
Compressed data uses less blank and can be communicated faster than uncompressed data.
storage
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
fewer bits
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.
character frequency table
230
Programming languages commonly provide a blank to store the character frequency table.
dictionary or map object
231
Blank is a common compression technique that assigns fewer bits to frequent items, using a binary tree.
Huffman coding
232
Blank have two data members: a character from the input and an integer frequency for that character.
Leaf nodes
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.
Internal nodes
234
A blank can be built from a character frequency table
Huffman tree
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.
node structure
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.
Huffman tree
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.
each character
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
decompress
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.
heuristic
240
A heuristic technique used for numerical computation may sacrifice accuracy to gain blank.
speed
241
A blank is an algorithm that quickly determines a near optimal or approximate solution.
heuristic algorithm
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.
0-1 knapsack problem
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.
self-adjusting heuristic
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.
0-1 knapsack
245
To construct a Python program to solve the knapsack problem using a heuristic, two classes are defined:
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
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.
greedy algorithm
247
Greedy algorithms tend to be blank, but certain types of problems exist where greedy algorithms don't find the best or optimal solution.
efficient
248
Greedy algorithms produce both efficient and optimal solutions for many problems, including the blank and blank
fractional knapsack problem and the activity selection problem.
249
The blank is similar to the regular knapsack problem, except that fractional pieces of any item can be selected.
fractional knapsack problem
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.
optimal solution
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).
activity selection problem
252
The blank of the activity selection problem will schedule the most activities possible without having any time conflicts.
optimal solution
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.
greedy algorithm
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))
Activity class for the activity selection problem.
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))
activity_selection() function.
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
Fractional knapsack greedy algorithm.
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)
0-1 Knapsack problem heuristic.
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.
Dynamic programming
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.
Fibonacci numbers
260
Blank avoids recomputing previously computed results by storing and reusing such results.
Dynamic programming
261
The blank algorithm takes 2 strings as input and determines the longest substring that exists in both strings. The algorithm uses dynamic programming.
longest common substring
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)
Longest common substring algorithm.
263
The runtime complexity of the iterative version of Fibonacci numbers
O(N)
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
}
FibonacciNumber iterative approach
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
O(N * M)
266
Since an N x M integer matrix is built, the space complexity is blank
O(N*M)
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.
DNA strings
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
O(N)
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.
memory
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.
dynamic programming
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]
Dynamic programming algorithm for the longest common substring problem.
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]
A space-saving optimized version of the longest common substring algorithm.
273
A blank can be used to solve the longest common subsequence problem.
dynamic programming matrix
