Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Computer Science > Data Structures & Algorithms > Flashcards

Data Structures & Algorithms Flashcards

1
Q

What two factors contribute to an algorithms efficiency?

A

Running Time & Memory Space

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

What are some reasons we don’t use standard time units for measuring time efficiency of an algorithm?

A
  • Dependance on the speed of the computer
  • Dependance on the quality of the program implementing the algorithm
  • Dependance on the quality of the compiler used to generate the executable
  • Difficulty of clocking the time precisely
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the worst case scenario for an algorithm?

A

The longest an algorithm could possibly take to run. For example in a linear search, the desired item being in the last spot.

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

What is the best case scenario for a algorithm?

A

The quickest an algorithm could possibly take to run. For example in insertion sort, if the list is already sorted it will be best case.

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

What is the average case scenario for a algorithm?

A

The average case scenario of an algorithm refers to the expected performance of the algorithm when it is run on typical inputs. It is a more realistic than best and worst case scenarios for estimating an algorithms efficiency.

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

What are the three types of asymptotic analysis?

A

O notation, omega notation and theta notation

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

What notation uses t(n) ≤ cg(n), ∀n ≥ n0

A

O notation

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

What notation uses t(n) ≥ cg(n), ∀n ≥ n0

A

Ω notation (omega)

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

What notation uses t(n) > cg(n), ∀n ≥ n0

A

ω notation (small omega)

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

What notation uses c1 g(n) ≤ t(n) ≤ c2 g(n), ∀n ≥ n0

A

Θ notation (theta)

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

What is O notation

A

O notation uses mathematical notation like O(f(n)) to represent the upper bound of the growth rate of the function as the input size changes.

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

What is Omega Notation

A

Omega notation uses mathematical notation like Ω(f(n)) to represent the lower bound of the growth rate of the function as the input size changes.

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

What is Theta Notation?

A

Theta notation uses mathematical notation like Θ(f(n)) to represent the tight bound of the growth rate of the function as the input size changes.

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

What theta notation does T(n) = T(n-1) + x have?

A

A theta notation of n * x, for example T(n-1) + 1 = Θ(n), T(n-1) + log n = Θ(n log n)

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

What theta notation does T(n) = 2T(n-1) + x have?

A

A theta notation of log 2^n * x, for example 2T(n-1) + 1 =Θ(2^n), T(n-1) + log n = Θ(2^n log n)

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

What is a linear and nonlinear structure?

A

Linear structures have a unique first and last element, and every component apart from the first has a unique predecessor, and every component apart from the last has a unique successor. If a structure doesn’t have any of those properties it is nonlinear.

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

What are Sequential and Direct Access structures?

A

In a linear data structure, a sequential structure is when to access an item you have to access all items before it, and a direct access structure is when you can access an item directly

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

What are the properties of an array?

A

A linear data structure that provides direct access but has a fixed size. They are a collection of a components of the same type, and a set of indexes is used to access the data stored in the array.

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

What are the properties of a list?

A

A list is a linear structure that provides sequential access to its elements, lists have a head and tail that point to the first and last element of the list. They don’t have a fixed size and only store elements of the same time.

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

What are linked lists?

A

Linked lists use dynamic allocation, where is consists of a collection of records called nodes containing at least one item in the list and then the location of the next node in the list, meaning it doesn’t have to be stored contiguously in memory.

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

What are the advantages and disadvantages on linked lists?

A

Pos:
- Fair use of memory
- Size does not need to be declared in advance
- Common operations are cheaper
Neg:
- Algorithms are more complex, harder to read and harder to debug
- Allocation and de-allocation of memory space will slightly decrease the performance of the algorithm

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

What are circular linked lists?

A

A variation of a linked list where the last node points to the first node instead of to null. This means the initial pointer can point to any node.

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

How can linked lists be stored in arrays?

A

An array of nodes to simulate memory and a Boolean array which keeps track of free space in the memory

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

What are doubly linked lists?

A

In addition to the head of a linked list, a tail pointer is also added to the node. This makes some operations easier at the cost of extra overhead.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What are the properties of stacks?
Stacks follow a last in first out rule, meaning there are only two operations for editing the stack, pop to remove the top item of the stack, and push to push an item to the top of the stack. It is a linear sequential list of values of the same type.
26
What are the properties of queues?
Queues follow a first in first out rule meaning it has two main operations enqueue and dequeue. It requires two references at the front and end of the queue. It is a linear sequential list of values of the same type.
27
What is a stable sorting method?
A sorting method is said the be stable if it preserves the relative order of the items with duplicated keys on the list. This means if we have a list of lists then it will sort by the first item, then sort the duplicates of the first item by the second item.
28
How does selection sort work?
It finds the biggest element in the list and places it at the end of the list, then finds the second biggest element in the list, and places it second last etc. It is a simple algorithm, however inefficient for large values of n. The worst case scenario is Θ(n^2), and it is an unstable sorting algorithm.
29
How does insertion sort work?
It works by creating a sorted subarray in the array .It starts of on the first element, compares with second element and swaps if needed. It then checks third element with second and first if needed and swaps if needed, and does this for every element until its a fully sorted array. The worst case scenario is Θ(n^2), and it is a stable sorting algorithm.
30
How does bubble sort work?
Bubble sort works by passing through the array a number of times and swaps the element with the one next to it if needed. Once it is fully sorted it does another pass through to check.
31
What are the 3 cases for the master theorem with dividing functions with equation T(n) = aT(n/b) + Θ(n^k * log^p n)
Case 1: if log b(a) > k then Θ = n ^ log b(a) Case 2: if log b(a) = k then Θ = n^k * log^p+1 n Case 3: if log b(a) < k then Θ = n^k * log^p n
32
What are the elementary sorting algorithms?
Selection, Insertion, Bubble
33
How does Quicksort work?
Quicksort is a divide and conquer algorithm, where it divides a list into two sublists around a pivot, where all items lower than the pivot go in one, and all higher go in the other. It then uses recursion to do this until all items are in their own lists and it is fully sorted. It works at O(n^2) at worst case.
34
How does Radix Sort work?
Radix sort is a sorting algorithm that works by sorting the elements of an array of numbers based on their individual digits. Radix sort can be implemented using either a least significant digit (LSD) or most significant digit (MSD) approach. LSD radix sort starts from the rightmost digit and moves towards the left, while MSD radix sort starts from the leftmost digit and moves towards the right. It has time complexity O(n), or O(n log n) for large values of n.
35
How does Counting Sort work?
Counting sort needs the range of numbers in the array to work. It then generates a list of how many times each number and all the numbers below it appear. It then does through the original list and places the number at the index of the cumulative list value, then takes one of the value of the cumulative list. It repeats until sorted. It has an O(n) because it is not a comparison based sort. It is stable.
36
How does hashing and hash search work?
Hashing works by taking the data to be stored in the hash table and putting it through a function to get its location. This means it is easy to get the data from it as it is easy to access as you can get the location from the data. Hash search has a best/average case of O(1) and worst case of O(n).
37
What is the hash multiplication method?
h(k) = [m * kA mod 1] where m is the size of the hash table and A is a constant between 0 and 1.
38
What is the hash division method?
h(k) = k mod m where m is the size of the hash table.
39
How does separate chaining work?
Each slot of a hash tree is a pointer to a dynamic structure such as a linked list or binary search tree, and if there is a collision the item gets added to the end.
40
How does Linear Probing work?
If the position of hash(k) is occupied, try hash(k) + c, then hash(k) + 2c etc until an empty slot is found, this however suffers from primary clustering which decreases the performance of the hash table.
41
How does Quadratic Probing work?
If the position of hash(k) is occupied, try hash(k) + c, then hash(k) + c^2 etc until an empty slot is found, this however suffers from secondary clustering which decreases the performance of the hash table.
42
What is a graph?
A collection of vertices(nodes) and edges(arcs, links). Vertices are objects that have properties associated with them, while edges can have properties if they are weighted graphs.
43
What is a path?
A list of nodes from one node to another where successive nodes are connected in the graph.
44
What does it mean if a graph is connected?
If there is a path from every node to every other node in the graph it is connected.
45
What is a simple path?
A path in which no node is repeated.
46
What is a cycle?
A cycle is a path that is simple except that the first and last nodes are the same.
47
What is a Spanning Tree?
A connected subgraph that contains all the nodes of the graph but has no cycles, and only one path between any two vertices.
48
What is a sparse graph?
A graph where the amount of edges is a lot less than the amount of vertices squared.
49
What is a dense graph?
A graph where the amount of edges is close to the amount of vertices squared.
50
What is a complete graph?
A graph when there are the maximum amount of edges, V(V-1)/2.
51
What is Adjacency-list representation?
A way to represent sparse graphs, where each node has an array containing all the nodes than it shares an edge with.
52
What is Adjacency-matrix representation?
A way to represent dense graphs, where a matrix is used to show what nodes connect to each other. If a node shares an edge with another node then there is a 1 and if it does not share an edge there is a 0. This will always be symmetrical along the main diagonal if it is an undirected graph.
53
How does a Breadth-first Search work?
Starts off at a node, and adds it to the queue, it then adds all nodes connecting to that node to the queue then dequeues the initial node, it does this for all nodes, only adding the ones not already in the queue, until the entire graph is searched.
54
How does a Depth-first Search work?
Starts off at a node, and adds it to the stack, it then adds all nodes connecting to that node to the stack then pops the initial node, it does this for all nodes, only adding the ones not already in the stack, until the entire graph is searched.
55
What is a Minimum Spanning Tree and what is Prim's algorithm?
An undirected weighted graph that is a collection of edges connecting all nodes such that the sum of all the edges is the minimum possible. It is generated by Prim's algorithm which works by having a priority queue where the shortest path to a new node is always at the front, and new nodes and the quickest you can get to them are added to the queue every time a new node is discovered.
56
What is a Shortest Path Tree and what is Dijkstra's Algorithm?
A Shortest Path Tree is a tree from one node which shows the shortest path to each other node and it is generated by Dijkstra's algorithm. Dijkstra's algorithm works by having a priority queue where the shortest path to the original node is always at the front, and new nodes and the quickest you can get to them from the original node are added to the queue every time a new node is discovered.
57
What is a directed graph?
A graph where the edges have a direction.
58
What are weak and strong connections in directed graphs?
A weak connection is when the undirected version of the graph is connected. A strong connection is where their is a path between every pair of nodes.
59
How can Depth-First Search be adjusted for directed graphs?
The algorithm needs to be made to repeat itself starting from a new node if there are still undiscovered nodes in the graph.
60
How does a topological sort work?
It orders all the nodes in a directed graph so that everything a nodes function relies on being complete is completed by the time it gets to that function. We can do this efficiently by doing a dfs from a node, and every time a node is complete we add it to a stack and then print the stack and that will be the order.
61
What is a tree?
A tree is a non-empty collection of nodes and edges. There can be nore more than one path between any two nodes in a tree.
61
What is a tree?
A tree is a non-empty collection of nodes and edges. There can be nore more than one path between any two nodes in a tree.
62
What is a rooted tree?
A tree where one node is called the root of the tree which is at the top of the tree and everything stems out from that node. Every node will only have one parent node but have multiple child nodes.
63
What are leaves?
Nodes that have no children.
64
What are ordered trees?
Trees where the order in which children are defined are important.
65
What is a M-ary tree?
Where the maximum number of children is M and the tree is ordered. For example a binary tree where there can only be two children per parent.
66
How does pre order traversal work?
A depth-based traversal method where we first visit the root node, then recursively traverse the left subtree, and finally recursively traverse the right subtree. The order of visiting nodes is root-left-right.
67
How does inorder traversal work?
A depth-based traversal method where we first recursively traverse the left subtree, then visit the root node, and finally recursively traverse the right subtree. The order of visiting nodes is left-root-right.
68
How does postorder traversal work?
A depth-based traversal method where we first recursively traverse the left subtree, then recursively traverse the right subtree, and finally visit the root node. The order of visiting nodes is left-right-root.
69
How does level order traversal work?
We visit each level and search the nodes left to right, starting at the root.
70
What is a complete binary tree?
A binary tree where all levels except the last is full
71
What is a full binary tree?
A binary tree where all the nodes except the leaves have two children.
72
What is a Binary Search Tree?
Binary Trees where all the elements in the left subtree of a node are less than the node, all the elements in the right subtree of a node are greater than the node. There can be no repeated elements.
73
How do we search a Binary Search Tree?
Starting at the root check if the node is the node we are looking for, if it is not we go left if it is smaller than it and right if it is greater than it, we then repeat this process until found. Worst case for doing an operation on a binary search tree is o(n)
74
What is a balanced binary search tree?
A binary search tree in which the heights of the left and right subtrees of every node differ by at most one. This means that the worst case for a search is o(log n).
75
What is rebalancing a binary search tree?
A process of modifying a binary search tree to restore balance when it becomes unbalanced due to insertion or deletion operations. This takes o(n) to do meaning that it takes a bit longer to complete the process, however it means any searches after are o(log n).
76
What is an AVL tree?
A self-balancing binary search tree where the difference in heights of the left and right subtrees of any node is at most one. It maintains balance using rotations when inserting or deleting nodes. AVL trees have worst-case time complexity of O(log n) for search
77
What are balance factors in a tree?
The balance factor of a node is the difference between the height of the left and right subtrees.
78
How does a single left rotation work?
This rotation is performed when the right subtree of a node has a height greater than the left subtree by more than one. It involves rotating the node and its right child to the left.
79
How does a single right rotation work?
This rotation is performed when the left subtree of a node has a height greater than the right subtree by more than one. It involves rotating the node and its left child to the right.
80
How does a double right (right-left) rotation work?
This rotation is performed when the left subtree of a node has a height greater than the right subtree, but the left child of the node has a right child with a greater height than its left child. It involves first rotating the left child to the right and then rotating the node and its left child to the left.
81
How does a double left (left-right) rotation work?
This rotation is performed when the right subtree of a node has a height greater than the left subtree, but the right child of the node has a left child with a greater height than its right child. It involves first rotating the right child to the left and then rotating the node and its right child to the right.
82
What is a heap?
A binary tree where the value of a child can not be bigger than the parent.
83
How can you heapify a tree?
Use a bottom up approach where we sink all the internal nodes in the tree. The bottom up approach means reverse level order traversal.
84
How can you use BST to sort?
Given a set of n elements build a BST tree and print the elements inorder. Has best case O(n log n) and worst case O(n^2).
85
How does Heapsort work?
It makes a heap takes the first element, the re heapifies the tree and takes the first element again. It has worst case O(log n).
86
How does Mergesort work?
Mergesort is a divide and conquer algorithm, where it divides a list into two even sublists. It then uses recursion to do this until all items are in their own lists. It then sorts them as it merges the lists back together. It works at O(n log n) at worst case.

Computer Science (13 decks)

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