Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer Science A level > Paper 1 Revision (Not needed) > Flashcards

Paper 1 Revision (Not needed) Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What is a data type?

A

A data type defines the values that can be stored and the operations that can be performed on the data.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the description of the real/float data type?

A

The real/float data type represents positive or negative numbers that can have a fractional part.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the description of the boolean data type?

A

The boolean data type represents a value that can be either true or false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the description of the character data type?

A

The character data type represents a single number, letter, or symbol.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the description of the string data type?

A

The string data type represents a collection of characters.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the description of the date/time data type?

A

The date/time data type represents a point in time and can have various formats.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the description of the pointer/reference data type?

A

The pointer/reference data type is used to store memory addresses

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the description of the records data type?

A

The records data type represents a collection of fields, each with a potentially different data type, similar to a row in a table.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the description of the arrays data type?

A

The arrays data type represents a finite, indexed set of related elements, all having the same data type.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are user-defined data types?

A

User-defined data types are created by deriving from existing data types to create customized data structures

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How can user-defined data types be used?

A

User-defined data types can be used to create customized data structures, such as creating a “Customer” data type with attributes like Forename, Surname, and EmailAddress.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is variable declaration?

A

Variable declaration is the process of creating a variable for the first time, giving it a name and sometimes a data type, and allocating memory for it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is constant declaration?

A

Constant declaration is similar to variable declaration but used for creating constants. The value of a constant does not change during program execution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is assignment?

A

Assignment is the process of giving a constant or variable a value.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is iteration?

A

Iteration is the process of repeating a block of code. It can be definite (with a known number of repetitions) or indefinite (with an unknown number of repetitions).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is definite iteration?

A

Definite iteration is a type of iteration where the number of repetitions required is known before the loop starts. Examples include for loops.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is indefinite iteration?

A

Indefinite iteration is a type of iteration where the number of repetitions required is not known before the loop starts. Examples include while loops.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are nested structures in programming?

A

Nested structures refer to placing one selection or iteration structure within another. It is identified by different levels of indentation in code.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Why is it important to use meaningful identifier names?

A

It is important to use meaningful identifier names for constants, variables, and subroutines to improve code readability and make it easier for others to understand the purpose of named objects in the program.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What does the rounding operation do?

A

The rounding operation limits the degree of accuracy of a number to a specified number of significant figures

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What does the truncation operation do?

A

The truncation operation removes the decimal part of a number and returns only the whole part.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What does the NOT boolean operation do?

A

The NOT operation returns the opposite of a boolean value.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What does the AND boolean operation do?

A

The AND operation returns true if both boolean values are true.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What does the OR boolean operation do?

A

Answer: The OR operation returns true if at least one of the boolean values is true.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What does the XOR boolean operation do?

A

The XOR operation returns true if exactly one of the boolean values is true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What are constants in programming?

A

Constants are data items whose value does not change once assigned. They are used for

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What are variables in programming?

A

Variables are data items whose value can change during program execution. They are used for storing data that can be modified as the program runs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What does the length function do for strings?

A

The length function returns the number of characters in a specified string.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What does the position function do for strings?

A

The position function returns the position of a specified character within a string.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What does the concatenation operation do for strings?

A

The concatenation operation joins two or more strings together to form a new, longer string.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What does the string to integer conversion do?

A

The string to integer conversion converts a string to an integer data type.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What does the string to float conversion do?

A

The string to float conversion converts a string to a float data type

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What does the integer to string conversion do?

A

The integer to string conversion converts an integer to a string data type.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What is random number generation in programming?

A

Random number generation is the ability of a programming language to generate pseudorandom numbers for various purposes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is exception handling in programming?

A

Exception handling is the process of dealing with errors or exceptions that occur during program execution to prevent crashes and inform users of errors.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What are subroutines in programming?

A

Subroutines are named blocks of code that contain instructions designed to perform a frequently used operation, reducing code repetition and improving code readability.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

What are parameters in subroutines?

A

Parameters are pieces of information specified within brackets when calling a subroutine, used to pass data between subroutines.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

How can values be returned from subroutines?

A

Subroutines can return values, and those that always return values are called functions. However, procedures can also return values.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What are local variables in subroutines?

A

Local variables are variables declared within a subroutine and can only be accessed within that subroutine. They exist in memory only during the execution of the subroutine.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

What are global variables in programming?

A

Global variables can be accessed from any part of a program and exist in memory for the entire duration of the program’s execution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

What is the role of stack frames in subroutine calls?

A

Stack frames are used to store return addresses, parameters, and local variables for each subroutine call during program execution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

What is nesting in subroutine calls?

A

Nesting occurs when one subroutine calls another, and each subroutine call is represented by a stack frame pushed onto the call stack.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

How are stack frames used in subroutine calls?

A

Stack frames are used to store information during subroutine calls.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

What happens to stack frames during nested subroutine calls?

A

During nested subroutine calls, stack frames are pushed onto the call stack and popped when the subroutines finish executing.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

What happens when a subroutine completes its execution?

A

When a subroutine completes, its stack frame is popped from the call stack, and the computer returns to the previous subroutine using the stored return address, parameters, and local variables.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

What does the call stack look like when all subroutines have completed their execution?

A

When all subroutines have completed, the call stack becomes empty.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

What is the procedural programming paradigm?

A

The procedural programming paradigm involves writing programs as sequences of instructions executed in order. It utilizes procedures such as functions and subroutines that can be called from anywhere within the program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

How is data stored in procedural programs?

A

Data is stored using constants and variables in procedural programs. Data structures can have a global scope accessible throughout the program or a local scope accessible only within the structure where they are declared

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

What is the structured approach in program design?

A

The structured approach uses four basic structures (assignment, sequence, selection, and iteration) to design and construct programs. It breaks down problems into smaller tasks, which are solved using procedures or modules that form part of the overall solution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

What are the benefits of designing a program from the top down?

A

Designing a program from the top down improves program maintainability by breaking down the solution into manageable elements. It facilitates easier navigation and debugging, especially in large projects.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

How do object-oriented programs store data and instructions?

A

Object-oriented programs use objects as containers for both data and instructions. New objects are created from classes, and each object has unique property values while sharing identical methods with other objects of the same class

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

What is instantiation in object-oriented programming?

A

Objects are created from classes by subroutines called constructors.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

What is a class in object-oriented programming?

A

A class is a blueprint for creating objects in object-oriented programming. It defines the properties (data) and methods (instructions) that objects of its type will have. Class definitions list the class name, properties, and methods.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

What is the difference between private, public, protected in class definitions?

A

In class definitions,
* Private methods or properties can only be accessed from within the object.
* Public methods allow access to and modification of a class’s private properties.
* Protected methods can only be accessed in the same and subclasses

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

What is encapsulation in object-oriented programming?

A

Encapsulation is the process of combining methods and procedures to form an object. It allows objects to encapsulate their contents, including properties and methods.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

What is function overloading in object oriented programming?

A

Overloading is a programming concept that allows programmers to define two or more functions with the same name and in the same scope.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

What is inheritance in object-oriented programming?

A

Inheritance allows a class to inherit the properties and methods of another class while having its own properties and methods.

The inherited class is called the super-class or parent class, and the inheriting class is called the subclass or child class.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

Program to interface, not implementation

A

Design principle allows unrelated classes to make use of similar methods.
An interface is defined as a collection of abstract procedures that can be implemented by unrelated classes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

Why do we favour composition over inheritance?

A

Composition is seen as more flexible relationship between objects.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

What is polymorphism in object-oriented programming?

A

Polymorphism is when objects can be handled in different ways depending on their class.

It allows objects of different classes to be used interchangeably if they have shared methods or properties. .

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

What is overriding in object-oriented programming?

A

Overriding is the process of providing a different implementation for a method that has the same name as a method in an inherited class.

It allows the subclass to customize or extend the behavior of the inherited method

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

What is association in object-oriented programming?

A

Association refers to the relationship between objects.
Association can be categorized as aggregation or composition

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

What is aggregation in object-oriented programming?

A

Aggregation represents a weaker association, where the associated object can exist independently.
Shown with an unfilled diamond-headed arrow.
——-◇

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
64
Q

What is composition in object-oriented programming?

A

Composition represents a stronger association, where the associated object is destroyed when the containing object is destroyed.
Shown with a filled diamond-headed arrow.

—–◆

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
65
Q

Why is object-oriented programming used?

A

Object-oriented programming provides a clear structure for developing and testing programs. It facilitates code reuse, and allows for collaborative development in large projects. Object-oriented programming enhances the efficiency and organization of code.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
66
Q

What are arrays?

A

Arrays are indexed sets of related elements that store data. They must be finite, indexed, and contain elements of the same data type.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
67
Q

How are elements accessed in an array?

A

Elements in an array are accessed using their index, which usually starts from zero.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
68
Q

Can arrays be multidimensional?

A

Yes, arrays can be created in multiple dimensions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
69
Q

What are fields?

A

Fields are individual pieces of data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
70
Q

What are records?

A

Records are collections of fields

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
71
Q

What are files?

A

Files are collections of records.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
72
Q

What is a queue?

A

A queue is an abstract data structure based on an array. It follows the “first in, first out” (FIFO) principle, where the first item added to the queue is the first one to be removed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
73
Q

What are linear queues?

A

Linear queues have a front pointer and a rear pointer to track the positions in the queue. New items are added at the rear and removed from the front. Linear queues maintain the order of insertion

74
Q

What are circular queues?

A

Circular queues are a type of queue where the front and rear pointers can wrap around the ends of the queue, creating a circular structure.

75
Q

What is a priority queue?

A

A priority queue assigns a priority to each item in the queue. Items with higher priority are dequeued before items with lower priority. If multiple items have the same priority, they are removed in the order of their arrival

76
Q

What is a stack?

A

A stack is an abstract data structure based on the “first in, last out” (FILO) principle.

77
Q

How can items be added and removed from a stack?

A

Items can be added to a stack using the “Push” operation, which adds an item to the top of the stack.

Items can be removed from a stack using the “Pop” operation, which removes the item at the top of the stack.

78
Q

Can a stack be full or empty?

A

Yes, a stack can have properties of being full or empty.

The “IsFull” function is used to check if the stack has reached its maximum capacity.

The “IsEmpty” function is used to determine if the stack contains no elements.

79
Q

What is a graph?

A

A graph is an abstract data structure used to represent complex relationships between items within datasets.

A graph consists of nodes (vertices) that are connected by edges (arcs).

80
Q

What is the difference between a weighted and an unweighted graph?

A

In a weighted graph, the edges are assigned a value, representing a quantity such as time, distance, or cost. In contrast, an unweighted graph does not assign any value to the edges.

81
Q

How can graphs be represented?

A

Graphs can be represented using two main methods: adjacency matrices and adjacency lists.

82
Q

What is adjacency matrix?

A

An adjacency matrix is a table-like representation where each node is assigned both a row and a column.

83
Q

What is adjacency list?

A

An adjacency list is a list-based representation where each node has a list of its adjacent nodes.

84
Q

What are the advantages adjacency matrices?

A

Advantages of Adjacency Matrices:

  • Time Efficient
  • Well suited to dense graphs with a large number of edges.
85
Q

What are the disadvantages adjacency matrices?

A
  • Memory inefficient for sparse graphs, as they store every possible edge between nodes, even those that don’t exist.
  • Requires a lot of memory for large graphs.
86
Q

What are the advantages adjacency list?

A
  • Memory efficient for sparse graphs, as they only store existing edges.
  • Requires less memory compared to adjacency matrices for the same graph.
  • Well suited to sparse graphs with few edges.
87
Q

What are the disadvantages adjacency list?

A
  • Inefficient for dense graphs
  • Time ineffiecient
88
Q

What are the characteristics of a tree?

A

A tree is a connected, undirected graph with no cycles.

89
Q

What is a rooted tree?

A

A rooted tree has a root node from which all other nodes stem. The root node is usually at the top of the tree, and it has no parent

90
Q

What are the different types of nodes in a rooted tree?

A
  • Parent nodes: Nodes from which other nodes stem.
  • Child nodes: Nodes that have a parent.
  • Leaf nodes: Child nodes with no children of their own.
91
Q

What is a binary tree?

A

A binary tree is a rooted tree in which each parent node has no more than two child nodes.

92
Q

How can rooted trees, including binary trees, be used in real-world applications?

A

Rooted trees can be used to represent family trees or file systems on a computer’s hard drive.

93
Q

What is the time complexity for retrieving data from a hash table?

A

Retrieving data from a hash table has a constant time complexity of O(1).

94
Q

What is a hash in the context of hash tables?

A

A hash is a unique value generated by a hashing algorithm based on the input. It is used as the key to store and retrieve data in a hash table

95
Q

How do hash tables handle collisions?

A

Hash tables handle collisions by using rehashing techniques to find an available position for the collided data.

96
Q

How does rehashing work in hash tables?

A

Rehashing involves finding the next available position in the hash table when a collision occurs.

This can be done by sequentially checking the next position until an empty slot is found.

97
Q

How does retrieving data from a hash table work in the presence of collisions?

A

When retrieving data from a hash table, the input value is hashed, and the corresponding position in the table is queried.

If a collision occurs, the algorithm continues to search for the desired value by checking the next position until it is found.

98
Q

What is a dictionary in the context of computer science?

A

A dictionary is a collection of key-value pairs, where the value is accessed by its associated key.

99
Q

Using dictionary-based compression, compress this sentence “row, row, row your boat”

Key | Value
_______________
1 | row
2 | your
3 | boat

A

the compressed code “11123”

100
Q

How can vectors be represented?

A

Vectors can be represented as lists of numbers, functions, or points in space.

101
Q

How can a vector be represented as a list of numbers?

A

A vector can be represented as a list of numbers, such as [12, 7, 3, 55].

102
Q

How can a vector be represented as a function?

A

A vector can be represented as a function where each index corresponds to a value, for example:
0 ↦ 12
1 ↦ 7
2 ↦ 3
3 ↦ 55

103
Q

How can vector addition be performed?

A

Vectors can be added by either adding their corresponding components or by adding the arrows “tip to tail.

104
Q

How can vector addition be performed?
[14, 4]
+ [4, -2]

A

[14, 4]
+ [4, -2]
= [18, 2]

105
Q

How does scalar-vector multiplication affect a vector?

[14, 4]
× 3

A

[14, 4]
× 3
= [42, 12]

106
Q

Convex Combinations of two vectors you need to check teams or pmt 💀💀
(am not paying 20 pounds for 1 months to add an image)

107
Q

What is the dot product of two vectors?

A

The dot product of two vectors, a ∘ b, is a single number calculated by taking the sum of the products of their corresponding components.

108
Q

Calculate the dot product
a = [12, 3] and b = [5, 8]
a ∘b

A

(12 × 5) + (3 × 8)
= 84

109
Q

What is a static data structure?

A

Static data structures are fixed in size and do not change in size to store their content

110
Q

What happens if the number of data items exceeds the allocated memory in a static structure?

A

If the number of data items exceeds the allocated memory in a static structure, an overflow error may occur, such as a stack overflow.

111
Q

What is a dynamic data structure?

A

Dynamic data structures can change in size to store their content and are not fixed in size.

112
Q

What happens if the number of data items exceeds the allocated memory in a dynamic structure?

A

If the number of data items exceeds the allocated memory in a dynamic structure, new memory locations are added to accommodate the additional data.

113
Q

What is graph-traversal?

A

Graph-traversal is the process of visiting each vertex in a graph.

114
Q

What are the two algorithms commonly used for graph-traversal?

A

The two algorithms commonly used for graph-traversal are depth-first search and breadth-first search.

115
Q

What is the main characteristic of a depth-first search?

A

In a depth-first search, a branch is fully explored before backtracking

116
Q

What data structure is typically used in depth-first traversal?

A

Depth-first traversal uses a stack to keep track of the vertices to visit.

117
Q

Can depth-first search be performed on any connected graph?

A

Yes, a depth-first search can be performed on any connected graph, not just trees.

118
Q

What is breadth-first search?

A

Breadth-first search is a graph traversal algorithm that explores all vertices of a graph in breadth-first order, visiting the neighbors of a vertex before visiting the neighbors’ neighbors.

119
Q

What data structure is typically used in breadth-first traversal?

A

Breadth-first traversal uses a queue to keep track of the vertices to visit.

120
Q

What is the main characteristic of a breadth-first search?

A

In a breadth-first search, a node is fully explored before venturing on to the next node at the same level

121
Q

Is breadth-first search suitable for any connected graph?

A

Yes, breadth-first search can be applied to any connected graph, regardless of whether it is weighted or unweighted.

122
Q

How does breadth-first search ensure finding the shortest path on an unweighted graph?

A

Breadth-first search explores the graph level by level, guaranteeing that the shortest path from the starting node to any other node is found first.

123
Q

What is tree traversal?

A

Tree traversal is the process of visiting, updating, or outputting each node in a tree, following a specific order or pattern.

124
Q

What is the requirement for starting a tree traversal?

A

Tree traversals must start at the root of the tree and then proceed to other nodes based on the traversal order.

125
Q

How many types of tree traversals are there?

A

There are three types of tree traversals: pre-order, in-order, and post-order.

126
Q

Is in-order traversal well defined for all types of trees?

A

No, in-order traversal is only well defined for binary trees, where each node has at most two child nodes.

127
Q

What is pre-order traversal used for?

A

Pre-order traversal is used for copying a tree, and it can be performed on any type of tree.

128
Q

What can be achieved by completing a pre-order traversal?

A

If all the nodes and edges were copied during pre-order traversal, an exact duplicate of the tree could be made.

129
Q

What is the main use of in-order traversal?

A

In-order traversal is useful for binary search trees because it outputs the contents of a binary search tree in ascending order. It can only be performed on binary trees.

130
Q

On what types of trees can post-order traversals be performed?

A

Post-order traversals can be performed on any type of tree.

131
Q

What are some practical applications of post-order traversal?

A

Post-order traversals are useful for Infix to RPN (Reverse Polish Notation) conversions, producing a postfix expression from an expression tree, and emptying a tree.

132
Q

In the expression “5 + 3”, what are the operands and the operator?

A

The operands are 5 and 3, and the operator is “+”.

133
Q

What is Reverse Polish Notation (RPN)?

A

Reverse Polish Notation is a postfix way of writing expressions, where the opcode comes after the operand.

134
Q

What is the purpose of a sorting algorithm?

A

A sorting algorithm is used to arrange the elements of an array or list in a specific order, making it easier to search, compare, or analyze the data

135
Q

Why are sorted lists preferred for binary searches?

A

Binary searches can only be performed on sorted lists. Sorted lists enable faster searching with a time complexity of O(logN), compared to linear searches with a time complexity of O(N).

136
Q

How does the bubble sort algorithm work?

A

The bubble sort algorithm compares adjacent elements and swaps their positions if they are in the wrong order. This process is repeated until the entire list is sorted. Bubble sort has a time complexity of O(n²), making it inefficient for large datasets.

137
Q

What is the approach used by the merge sort algorithm?

A

Merge sort follows a “divide and conquer” approach. It divides the original list into smaller sublists, recursively sorts them, and then merges them back together to obtain a sorted list. Merge sort has a time complexity of O(nlogn), making it more efficient than bubble sort.

138
Q

What is the purpose of Dijkstra’s algorithm?

A

Dijkstra’s algorithm is used to find the shortest path between two nodes in a graph.

139
Q

How is Dijkstra’s algorithm different from breadth-first search?

A

Dijkstra’s algorithm uses a priority queue to keep track of visited nodes, while breadth-first search uses a standard queue.

140
Q

What are some applications of Dijkstra’s algorithm?

A

Dijkstra’s algorithm is commonly used in systems such as satellite navigation for finding the shortest or fastest route, and in routers for determining the shortest path for routing packets within networks.

141
Q

In what type of computer systems is Dijkstra’s algorithm heavily utilized?

A

Dijkstra’s algorithm is heavily used in computer systems that require calculating shortest paths, such as satellite navigation systems and network routers.

142
Q

What are optimization algorithms used for?

A

Optimization algorithms are used to find the best solution to a given problem by iteratively improving an initial solution.

143
Q

I don’t know if this actually needed but it was in pmt. Update: “It is required knowledge…”

What is information hiding?

A

Information hiding is the process of hiding non-essential details of an object and focusing only on its essential characteristics.

144
Q

What is procedural abstraction?

A

Procedural abstraction involves breaking down a complex model into reusable procedures, abstracting away specific values used in computations.

145
Q

What is functional abstraction?

A

Functional abstraction further abstracts procedures into functions, disregarding the specific method and focusing on the desired outcome.

146
Q

What is data abstraction?

A

Data abstraction abstracts away the representation details of data, allowing the creation of new data structures from existing ones.

147
Q

What is problem abstraction or reduction?

A

Problem abstraction involves simplifying a problem by removing details until it becomes solvable or similar to a problem that has already been solved.

148
Q

What is decomposition?

A

Decomposition is the process of breaking down a problem into smaller sub-problems that can be solved individually or further divided.

149
Q

What is composition?

A

Composition involves combining procedures or components to form a larger system or complex data type.

150
Q

What is context free languages?

A

Is a set of strings and symbols that follow the rules of a
context-free grammar.

151
Q

What is automation?

A

Automation involves implementing models, algorithms, and data structures to solve problems efficiently and execute code on relevant data structures.

152
Q

What is Backus-Naur form used for?

A

Backus-Naur form is used to notate context-free languages.

<FullName> ::= <Title><Forename><Surname></Surname></Forename></Title></FullName>

153
Q

What are non-terminals in Backus-Naur form?

A

Non-terminals are components represented by text inside angle brackets, which can be further broken down into non-terminals or terminals.

< FullName> ::= < Title > < Forename > < Surname >

154
Q

What are terminals in Backus-Naur form?

A

Terminals are components represented by text without any brackets and cannot be broken down further.

< Address > ::= < Number >< Street >
< Number > ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

155
Q

How can recursion be used in Backus-Naur form?

A

Backus-Naur form allows for recursion, where a non-terminal can be defined in terms of itself, enabling the representation of more complex definition

156
Q

Big O notation of a Constant

A

O(C)

157
Q

Big O notation of a Logarithmic

A

O(log2(n))

158
Q

Big O notation of Linear

A

O(n)

159
Q

Big O notation of Linear Logarithmic

A

O(nlog(n))

160
Q

Big O notation of a Polynomial

A

O(n^2) or O(n^3)

161
Q

Big O notation of an Exponential

A

O(2^n)

162
Q

Big O notation of a Factorial

A

O(n!)

163
Q

What is the time complexity of an algorithm with constant time?

A

The time complexity is independent of the input size

164
Q

How does an algorithm with logarithmic time complexity behave?

A

It halves the number of items being processed in each iteration.

165
Q

What is the worst-case scenario for an algorithm with linear time complexity?

A

It needs to go through each item once.

166
Q

Which sorting algorithm has a linear logarithmic time complexity?

A

Merge sort.

167
Q

What types of loops are present in algorithms with polynomial time complexity?

A

Algorithms with O(n^2) have a loop inside a loop, while O(n^3) has a loop inside a loop inside a loop.

168
Q

What does it mean for an algorithm to have exponential time complexity?

A

It becomes intractable and cannot be solved within a useful amount of time.

169
Q

What type of problem is associated with factorial time complexity?

A

Problems like the Travelers problem or the explorers problem.

170
Q

What is the difference between tractable and intractable problems?

A

Tractable problems can be solved within a useful period of time, while intractable problems cannot be solved efficiently.

171
Q

What are heuristic methods used for?

A

They provide approximate solutions to intractable problems that are more useful than not having a solution.

172
Q

What is the Halting problem?

A

It is the problem of determining if another algorithm will finish with a given input, and it demonstrates that some problems cannot be solved algorithmically.

173
Q

What is the time complexity of an algorithm with a quadratic time complexity?

A

The algorithm has a nested loop structure, where each iteration increases the number of operations exponentially. O(n^2)

174
Q

What is the time complexity of an algorithm with a cubic time complexity?

A

The algorithm has three nested loops, resulting in a significant increase in the number of operations as the input size grows.

175
Q

What is the time complexity of an algorithm with factorial time complexity?

A

The algorithm’s runtime increases factorialy with the input size, making it highly inefficient for large inputs

176
Q

What are the different cases used to analyze time complexity?

A
  • Best-case time complexity refers to the minimum time an algorithm takes
  • Average-case time complexity represents the expected time
  • Worst-case time complexity indicates the maximum time an algorithm can take.
177
Q

What is the time complexity of an algorithm with log-linear time complexity?

A

The algorithm’s runtime grows in a logarithmic manner relative to ‘n’ and linearly relative to the size of the input.
O(nlog(n)

178
Q

What are the components of a Turing Machine?

A

A Turing Machine consists of a finite state machine, a read/write head, and an infinitely long tape divided into cells.

179
Q

How does a Turing Machine execute its input?

A

A Turing Machine reads symbols from the tape using its read/write head and transitions between states based on defined rules.

180
Q

What is the purpose of the halting state in a Turing Machine?

A

The halting state indicates the end of the Turing Machine’s execution and is reached once all input data has been processed.

181
Q

How does the power of Turing Machines compare to finite state machines?

A

Turing Machines are more powerful than finite state machines as they can process a broader range of languages and have an infinitely long tape.

Computer Science A level (9 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions