Test Flashcards
1
Q
What is the definition of finiteness in algorithms?
A
An algorithm must always have a finite number of steps before it ends
It must have a defined endpoint or output and not enter an endless loop.
2
Q
Define definiteness in the context of algorithms.
A
An algorithm needs to have exact definitions for each step
Clear and straightforward directions ensure that every step is understood and can be taken easily.
3
Q
What are inputs in an algorithm?
A
Values supplied to the algorithm before its processing
These inputs come from a predetermined range of acceptable values.
4
Q
What is meant by output in an algorithm?
A
One or more results produced after the algorithm completes its steps
The relationship between the input and the result should be clear.
5
Q
Explain the effectiveness characteristic of an algorithm.
A
Stages must be straightforward to be carried out in finite time using basic operations
Every operation in the algorithm should be doable and practicable.
6
Q
What does generality mean in terms of algorithms?
A
An algorithm should solve a group of issues rather than just one specific case
It should offer a generic fix that manages a variety of inputs.
7
Q
What does modularity refer to in algorithm design?
A
The ability to break a problem down into small modules or steps
This is a basic definition of an algorithm.
8
Q
Define correctness in the context of an algorithm.
A
When given inputs produce the desired output
It indicates that the algorithm was designed correctly.
9
Q
What is maintainability in algorithm design?
A
The algorithm should be designed in a straightforward, structured way
This allows for redefinition without significant changes.
10
Q
What does functionality mean in algorithms?
A
It takes into account various logical steps to solve a real-world problem
11
Q
What is robustness in an algorithm?
A
An algorithm’s ability to define a problem clearly
12
Q
What does user-friendly mean in the context of algorithms?
A
The algorithm should be easy to understand for the programmer
13
Q
How does simplicity impact algorithms?
A
A simple algorithm is easier to understand
14
Q
What is extensibility in algorithm design?
A
The algorithm should be usable by other designers or programmers
15
Q
What is a brute force algorithm?
A
A straightforward approach that exhaustively tries all possible solutions
Suitable for small problem instances but may become impractical for larger ones.
16
Q
Define a recursive algorithm.
A
A method that breaks a problem into smaller, similar subproblems and applies itself to solve them
It continues until reaching a base case.
17
Q
What is an encryption algorithm?
A
Utilized to transform data into a secure, unreadable form using cryptographic techniques
18
Q
What is a backtracking algorithm?
A
A trial-and-error technique used to explore potential solutions by undoing choices
Commonly employed in puzzles and optimization problems.
19
Q
What is the purpose of a searching algorithm?
A
Designed to find a specific target within a dataset
20
Q
What does a sorting algorithm do?
A
Aims to arrange elements in a specific order
This enhances data organization and retrieval.
21
Q
What is a hashing algorithm?
A
Converts data into a fixed-size hash value for rapid data access
Commonly used in databases and password storage.
22
Q
What is the divide and conquer algorithm?
A
Breaks a complex problem into smaller subproblems, solves them independently, and combines their solutions
23
Q
What is a greedy algorithm?
A
Makes locally optimal choices at each step to find a global optimum
Useful for optimization problems but may not always lead to the best solution.
24
Q
What is dynamic programming in algorithms?
A
Stores and reuses intermediate results to avoid redundant computations
25
What is a randomized algorithm?
Utilizes randomness in its steps to achieve a solution
26
What is a base case in recursive algorithms?
The condition under which the recursion stops
## Footnote
It represents the simplest instance of the problem.
27
What is a recursive case?
The part of the algorithm that breaks the problem down into smaller instances
28
What is a stack in the context of recursion?
Each recursive call is placed on the system call stack
29
What is the factorial of a number n in terms of recursion?
Defined as n! = n * (n-1)! for n > 0, and 0! = 1 as the base case
30
What are the advantages of recursion?
* Simplicity
* Direct translation for naturally recursive problems
31
What are the disadvantages of recursion?
* Performance overhead due to multiple function calls
* Higher memory usage from call stack
32
When should recursion be used?
When a problem can be divided into similar sub-problems or when the recursive solution is simpler
33
What is linear search?
A simple search algorithm that checks each element sequentially
## Footnote
It has a time complexity of O(n).
34
What is the time complexity of linear search in the worst case?
O(n)
35
What is binary search?
A more efficient search algorithm that repeatedly divides the search interval in half
## Footnote
Requires the array to be sorted.
36
What is the time complexity of binary search?
O(log n)
37
What is the best case time complexity for binary search?
O(1)
38
Define interpolation search.
Similar to binary search but works on uniformly distributed data
39
What is depth-first search (DFS)?
Explores as far as possible along one branch before backtracking
40
What is breadth-first search (BFS)?
Explores all neighbors at the present depth before moving on to the next depth level
41
What is bubble sort?
A simple sorting algorithm that repeatedly swaps adjacent elements
## Footnote
It is inefficient for large datasets.
42
What is the worst-case time complexity of bubble sort?
O(n^2)
43
What is selection sort?
Finds the minimum element and swaps it with the first unsorted element
## Footnote
Always performs O(n^2) comparisons.
44
What is the worst-case time complexity of selection sort?
O(n^2)
45
What is the time complexity of Selection Sort in the best case?
O(n^2)
## Footnote
Selection sort does not improve with better input scenarios.
46
What is the primary characteristic of Insertion Sort?
Builds a sorted list one element at a time
## Footnote
Efficient for small or nearly sorted datasets.
47
What is the worst-case time complexity of Insertion Sort?
O(n^2)
## Footnote
Occurs when the array is sorted in reverse order.
48
What is the best-case time complexity for Merge Sort?
O(n log n)
## Footnote
The time complexity remains the same in all cases.
49
What is the main approach used in Quicksort?
Selects a pivot element and partitions the array around it
## Footnote
Recursively sorts the partitions.
50
What is the average-case time complexity of Quicksort?
O(n log n)
## Footnote
Occurs with random pivots.
51
What data structure does Heap Sort utilize?
Binary heap data structure
## Footnote
Builds a max-heap and repeatedly extracts the maximum element.
52
What is the time complexity of Counting Sort?
O(n + k)
## Footnote
Where k is the range of the input.
53
What is Radix Sort effective for?
Sorting large numbers or strings with fixed length
## Footnote
Sorts numbers by processing individual digits.
54
What is the worst-case time complexity for Bucket Sort?
O(n^2)
## Footnote
All elements may end up in one bucket in a degenerate case.
55
What is the defining characteristic of Shell Sort?
Generalization of insertion sort with a gap sequence
## Footnote
Sorts elements far apart and gradually reduces the gap.
56
What is Big O Notation?
Provides an upper bound on time or space complexity
## Footnote
Represents the worst-case scenario for an algorithm's efficiency.
57
What does O(1) signify in Big O Notation?
Constant Time
## Footnote
The algorithm takes the same time to execute regardless of input size.
58
What is the time complexity of Linear Search?
O(n)
## Footnote
The runtime increases linearly with the input size.
59
What is the worst-case time complexity of Bubble Sort?
O(n^2)
## Footnote
Inefficient for large datasets.
60
What is the average-case time complexity for Merge Sort?
O(n log n)
## Footnote
Consistent across different input scenarios.
61
What is the primary use case for Insertion Sort?
Good for small or nearly sorted lists
## Footnote
Efficient for building a sorted list incrementally.
62
Fill in the blank: The best case for Insertion Sort is _______.
O(n)
## Footnote
Occurs when the array is already sorted.
63
What is a key observation regarding Quick Sort?
Can degrade to O(n^2) if poor pivot selection occurs
## Footnote
While it is efficient on average, the worst-case scenario exists.
64
What is the time complexity of Heap Sort in all cases?
O(n log n)
## Footnote
Consistent across best, average, and worst cases.
65
What does O(n log n) represent in terms of algorithm efficiency?
Log-Linear Time
## Footnote
Common in efficient sorting algorithms like merge sort and quicksort.
66
What characterizes Exponential Time complexity?
Runtime doubles with each additional element
## Footnote
Common in algorithms that solve problems by brute force.
67
What is the definition of a Data Type?
Classification that specifies the type of data a variable can hold
## Footnote
Defines operations that can be performed on the data.
68
Give examples of primitive data types.
* Integer
* Floating Point
* Character
* Boolean
## Footnote
Basic building blocks of data in programming.
69
What is an Enumeration in programming?
A data type allowing a variable to be a set of predefined constants
## Footnote
Improves code readability and limits possible values.
70
What is the advantage of using Enums?
* Readability
* Maintainability
* Type Safety
## Footnote
Prevents assigning invalid values to variables.
71
Fill in the blank: The average case for linear search is _______.
O(n)
## Footnote
This simplifies from O(n/2) in Big O notation.
72
What is an Enum in Python?
A symbolic name for a set of values, improving code readability and type safety
## Footnote
Enums are defined in Python using the enum module.
73
List three advantages of using Enums
* Readability
* Maintainability
* Type Safety
## Footnote
Enums help prevent errors by restricting variable values to a set of specific options.
74
Define a data structure
A specific way of organizing and storing data in a computer for efficient access and modification
## Footnote
Data structures are built on top of data types.
75
Give two examples of data structures
* Arrays
* Linked Lists
## Footnote
Other examples include stacks, queues, trees, graphs, and hash tables.
76
What is an Abstract Data Type (ADT)?
A theoretical model of a data structure defining behavior from the user's perspective without implementation details
## Footnote
ADTs specify operations and expected behavior.
77
List two differences between Data Structures and ADTs
* Data Structures: Concerned with organization and access
* ADTs: Concerned with operations and expected behavior
## Footnote
Data types are the most basic level of abstraction.
78
What is an array?
A collection of homogeneous elements stored in contiguous memory locations
## Footnote
Each element can be accessed using its index.
79
What is the time complexity for accessing an element in an array?
O(1)
## Footnote
Direct access via index allows for constant time complexity.
80
What is a linked list?
A linear collection of nodes where each node contains data and a reference to the next node
## Footnote
Linked lists can be singly, doubly, or circular.
81
What is the time complexity for inserting a node at the beginning of a linked list?
O(1)
## Footnote
This is because only the head pointer needs to be adjusted.
82
What does the append() method do in Python lists?
Adds an element to the end of the list
## Footnote
Example: list.append(element)
83
True or False: A stack follows the First-In-First-Out (FIFO) principle.
False
## Footnote
A stack follows the Last-In-First-Out (LIFO) principle.
84
What is a queue?
A linear data structure that follows the First-In-First-Out (FIFO) principle
## Footnote
The first element added is the first one to be removed.
85
What is a hash table?
A data structure that maps keys to values using a hash function
## Footnote
It provides fast lookup for key-value pairs.
86
What is the purpose of a hash function?
To convert a key into an index for a hash table
## Footnote
A good hash function ensures uniform distribution and fast computation.
87
What data structure uses the Last-In-First-Out (LIFO) principle?
Stack
## Footnote
Operations include push, pop, and peek.
88
Fill in the blank: A _______ allows for storing duplicate elements.
Bag
## Footnote
Also known as a multiset.
89
What is the time complexity for searching an element in a linked list?
O(n)
## Footnote
Requires traversal from the head to find the target element.
90
What is a tree?
A hierarchical data structure composed of nodes with a root node and child nodes
## Footnote
The top node is called the root, and nodes without children are leaves.
91
What is the time complexity for deleting an element from the end of a stack?
O(1)
## Footnote
This operation is constant time because it only involves removing the top element.
92
What is a tree in data structures?
A hierarchical data structure composed of nodes, with a top node called the root and nodes with no children called leaves.
## Footnote
Each node contains a value and references to child nodes.
93
Define a Binary Tree.
A tree where each node has at most two children (left and right).
## Footnote
It is the simplest form of a tree structure.
94
What is a Binary Search Tree (BST)?
A binary tree where the left child contains values less than the parent, and the right child contains values greater than the parent.
## Footnote
Allows for efficient searching.
95
What characterizes an AVL Tree?
A self-balancing binary search tree where the height of the two child subtrees of any node differs by at most one.
## Footnote
It rebalances through rotations when this condition is violated.
96
What is a Red-Black Tree?
A binary search tree with an extra bit of storage per node for color, which can be either red or black, with specific properties to maintain balance.
## Footnote
Properties include that the root is always black and red nodes cannot have red children.
97
What is a B-Tree?
A self-balancing search tree where nodes can have more than two children, commonly used in databases and file systems.
## Footnote
A B-tree of order m can have at most m-1 keys and m children.
98
What is the time complexity for insertion in balanced trees like AVL or Red-Black Trees?
O(log n).
## Footnote
For unbalanced trees, the complexity can be O(n).
99
What are the types of tree traversal?
* In-order
* Pre-order
* Post-order
* Level-order
## Footnote
Each traversal method has different orders of visiting nodes.
100
Define In-order Traversal.
Left, Node, Right.
## Footnote
Used in BSTs to get sorted order.
101
What is a heap?
A specialized tree-based data structure that satisfies the heap property, where in a max-heap, the parent node is greater than or equal to its children.
## Footnote
In a min-heap, the parent node is less than or equal to its children.
102
What is the time complexity for searching in a binary heap?
O(1).
## Footnote
This is for accessing the root element.
103
What operations can be performed on a set?
* Insert: O(1)
* Delete: O(1)
* Search: O(1)
* Union: O(n)
* Intersection: O(n)
* Difference: O(n)
## Footnote
Sets manage unique elements.
104
What is a graph?
A collection of nodes (vertices) connected by edges, which can be directed or undirected.
## Footnote
Can also be weighted or unweighted.
105
What is Dijkstra's Shortest Path Algorithm?
A greedy algorithm that finds the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights.
## Footnote
Time complexity is O(V^2) for the simplest implementation.
106
What distinguishes the Bellman-Ford algorithm from Dijkstra's algorithm?
Bellman-Ford handles negative edge weights and can detect negative cycles, while Dijkstra's cannot.
## Footnote
Time complexity for Bellman-Ford is O(V*E).
107
What is the time complexity for adding an edge in a graph using an adjacency list?
O(1).
## Footnote
This applies when using an adjacency matrix as well.
108
Fill in the blank: A _______ is an abstract data structure that stores unique elements without a specific order.
set
## Footnote
Sets are useful for managing unique collections of data.
109
What is the difference between a directed and an undirected graph?
Directed graphs have edges with direction, while undirected graphs do not.
## Footnote
This affects how relationships between nodes are represented.
110
Define the time complexity for removing a vertex in a graph.
O(V + E).
## Footnote
This is for an adjacency list representation.
111
What is the time complexity of searching in a balanced tree?
O(log n).
## Footnote
For unbalanced trees, the complexity can be O(n).
112
What is a Deque?
Double-ended queue; flexible insertions/deletions.
113
What data structure uses key-value pairs for fast lookups?
Hash Table.
114
Define a Tree in data structures.
Hierarchical structure; efficient searches and sorted data.
115
What is a Heap used for?
Binary tree for priority queues; fast access to max/min.
116
What characterizes a Set in programming?
Unique elements; fast membership checks.
117
What is a Graph in the context of data structures?
Nodes and edges; used in networks and relationship modeling.
118
What are the key operations in a Dictionary/Map?
* Insertion * Lookup * Deletion * Update * Check Existence * Iteration * Get Method * Length * Clearing * Copying * Pop * Popitem * Setdefault
119
How do you add a new key-value pair to a dictionary?
dictionary[key] = value.
120
What is the syntax to retrieve a value associated with a key in a dictionary?
value = dictionary[key].
121
What does the 'del' statement do in a dictionary?
Removes a key-value pair from the dictionary.
122
How do you update a value in a dictionary?
dictionary[key] = new_value.
123
What is the purpose of the 'in' keyword in a dictionary?
Checking if a key exists in the dictionary.
124
Fill in the blank: To iterate over values in a dictionary, use _______.
dictionary.values()
125
What does the 'get' method do in a dictionary?
Retrieves the value associated with a key, with an optional default.
126
How can you find the number of key-value pairs in a dictionary?
len(dictionary).
127
What does the 'clear' method do in a dictionary?
Removes all key-value pairs from the dictionary.
128
What does the 'copy' method do in a dictionary?
Creates a shallow copy of the dictionary.
129
What is the purpose of the 'pop' method in a dictionary?
Removes a key and returns its value.
130
What does the 'popitem' method do in a dictionary?
Removes and returns an arbitrary key-value pair as a tuple.
131
What does the 'setdefault' method do in a dictionary?
Returns the value of a key if it exists; otherwise, inserts the key with a specified value and returns that value.
132
What is the difference between static and dynamic variable declaration?
* Static: Memory allocated at compile time. * Dynamic: Memory allocated at runtime.
133
What is a characteristic of static variables?
Fixed size; allocated during compilation.
134
Fill in the blank: Dynamic variables are allocated memory at _______.
runtime
135
What defines strongly-typed languages?
Strict type enforcement; no implicit conversions.
136
What is a key characteristic of weakly-typed languages?
Implicit type coercion; allows automatic conversion between types.
137
What are the assignment operators in programming?
* Simple Assignment (=) * Compound Assignment (+=, -=, *=, /=, etc.)
138
What is the order of operations in programming?
* Arithmetic Operations * Comparison Operations * Logical Operations * Assignment Operators * Bitwise Operations * Miscellaneous
139
What is the purpose of a for loop?
Iterates over a sequence or range, executing a block of code for each item.
140
What does the while loop do?
Repeatedly executes a block of code as long as a condition is True.
141
What is a do-while loop?
Executes a block of code at least once, then repeats while a condition is True.
142
What does the 'break' statement do in a loop?
Exits the loop immediately.
143
What is the purpose of the 'continue' statement in loops?
Skips the rest of the current iteration and proceeds to the next.
144
What is the function of the 'pass' statement in Python?
Acts as a placeholder statement.
145
What are nested loops?
Loops inside other loops to perform complex iterations.
146
What is the if statement used for?
Executes a block of code if its condition is True.
147
What is the difference between if-else and if-elif-else statements?
if-else handles two conditions; if-elif-else checks multiple conditions in sequence.
148
What does the switch-case statement do?
Dispatches execution to different parts of code based on the value of an expression.
149
What does the AND operator return?
True if both conditions are True.
150
What does the OR operator return?
True if at least one condition is True.
151
What does the AND operator do?
Returns True if both conditions are True
## Footnote
Syntax: condition1 and condition2 (Python/C/C++)
152
What is the syntax for the OR operator in Python?
condition1 or condition2
## Footnote
Example: if x < 0 or x > 10:
153
Describe the NOT operator.
Returns the opposite Boolean value of the condition
## Footnote
Syntax: not condition (Python/C/C++)
154
Define a class.
A template for creating objects that encapsulates data and methods
## Footnote
Example: class ClassName: ...
155
What are attributes in a class?
Variables that hold data related to the class
## Footnote
Defined within the __init__ method using self in Python.
156
What are methods in a class?
Functions defined within a class that operate on its attributes or perform actions
## Footnote
Defined with def keyword in Python.
157
What is a constructor?
A special method that initializes objects of the class
## Footnote
In Python, it's the __init__ method.
158
What is a destructor?
A method that cleans up when an object is destroyed
## Footnote
In C++, defined with ~ClassName().
159
What is inheritance in programming?
Allows creating a new class based on an existing class, inheriting its attributes and methods
## Footnote
Example: class ChildClass(ParentClass): ...
160
What does encapsulation refer to?
The concept of restricting access to certain details of an object’s implementation
## Footnote
Involves using access specifiers.
161
What are access specifiers in C++?
Keywords that control access to class members
## Footnote
Examples: public, protected, private.
162
What is polymorphism in programming?
Allows objects of different classes to be treated as objects of a common base class
## Footnote
Typically through method overriding.
163
What is garbage collection?
A process by which a computer's memory is automatically managed
## Footnote
Frees up memory that is no longer being used.
164
What is reference counting?
A count of the number of times an object is referred to in a program
## Footnote
In Python, when the count becomes zero, the object is deleted.
165
What is memory allocation?
The process of reserving memory space for an object in a program
## Footnote
Example: new keyword in Java.
166
Define linked allocation.
A memory allocation technique where memory is allocated in linked nodes
## Footnote
Example: Linked lists.
167
What is sequential allocation?
A memory allocation technique where memory is allocated in a sequential manner
## Footnote
Example: Arrays.
168
What is a Data Flow Diagram (DFD)?
A graphical representation of the flow of data through a system
## Footnote
Shows how data enters, moves, and exits the system.
169
What do processes represent in a DFD?
How data is transformed or manipulated
## Footnote
Represented by circles or rounded rectangles.
170
What are data stores in a DFD?
Where data is stored within the system
## Footnote
Represented by open-ended rectangles.
171
What do data flows represent in a DFD?
Movement of data between processes, data stores, and external entities
## Footnote
Represented by arrows.
172
What are external entities in a DFD?
Outside the system but interact with it
## Footnote
Represented by squares or rectangles.
173
How do DFDs assist in algorithm design?
Help visualize how data will flow through the algorithm
## Footnote
Useful for designing algorithms that manipulate data.
174
What benefit do DFDs provide for modularity?
Break down the system into smaller processes for better organization
## Footnote
Each process can correspond to a function or module.
