Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Data Structures and Algorithms > Dannys Cards > Flashcards

Dannys Cards Flashcards

1
Q

What is the time complexity of Counting Sort?

A

O(n)

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

What is a Sequential Structure?

A

We can only access an element after we have accessed all the elements before it

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

Whats the difference between Direct Access and Hash Tables?

A

Direct Access: key “k” is stored in slot k

Hash Table: key “k” is stored in hash(k)

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

How does Counting Sort work?

A

Creates array to store count of all elements

Changes the array so the count also adds all the elements prior

Iterates through main list and takes count number and places it in new list with index of the count number

Repeat until done, -1 from count when used

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

Why do collisions happen in Hash Tables?

A

Because we’re mapping elements to normally smaller domain of slots, collisions are likely to happen

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

How does MSD radix sort work?

A

Unlike LSD radix sort, it starts from left most (most significant) digit groups those together, then goes to next digit on the right and groups those together in sub groups, then groups the next digits on the right in sub sub groups and so on.

540,330,545,350,333,578,570

First grouping of digit of 100s
Eg. 330,350,333 540,545,570,578

2nd grouping of 10’s

330,333 350 540, 545 570,578

3rd and final grouping of 1’s to make completed list

330,333,350,540,545,570,578

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

What is a Circular List?

A

The link member of the last node points to the first node

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

What are the rules of Binary Search Trees?

A

the value of left node must be smaller than the parent node, and the value of right node must be greater than the parent node

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

What is the benefit of a Balanced Tree?

A

Increases efficiency of searching

If a tree is balanced we can perform most operations in O(log n)

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

How does Quicksort work?

A
  1. Pick an item, is called the “pivot”
  2. Sort the other elements so that smaller elements are on its left and bigger are on its right
  3. Now you have two piles of items repeat this until each pile has 1 card
  4. Once sorted add all piles together
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a Direct Access Structure?

A

Any element of the structure can be accessed directly

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

How long does a Simple Step take in RAM?

A

1 time step

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

How do Lists differ from Arrays?

A

They don’t have a fixed size, but like arrays then can only store elements of the same type

-> Homogenous Structure

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

Explain O(n^2) time

A

Quadratic

Relatively efficient for non large input sizes

Typical of algorithms that have to analyse all pairs of element of the input

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

Define an edge

A

A connection between 2 nodes

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

What is an Insertion Sort?

A

Builds the final sorted array one element at a time by inserting elements into their correct positions

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

Define a leave

A

Nodes that have no children

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

What is the Bernoulli Process?

A

A series of executions of Bernoulli trials

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

What type of algorithm is Quick Sort?

A

Divide and Conquer

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

How does Merge Sort work?

A

Splits list into separate lists then merges the lists back together in order

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

Define a Dense Graph?

A

graph with a large number of edges in relation to the number of vertices, and the number of edges is close to the maximum possible number

E is close to V^2

E = O(V^2)

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

Explain O(n^3) time

A

Cubic

Not very efficient but still polynomial

Example is Matrix Multiplication

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

Explain O(n) time

A

Linear, algorithms that are forced to pass through all elements of the input, a number of times

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

What is the worst case of an Insertion Sort?

A

O(n^2)

Same as selection sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Define a Graph?
Collection of vertices(nodes) and edges (arcs) G = (V,E)
26
What is the best and worst case of Hash Search?
Worst case: O(n) Best case: O(1) (and average case)
27
What is a Forest?
A collection of trees Disjoint
28
What is the worst case of Quicksort?
O(n^2)
29
What structure is a Stack and what structure is a Queue
Stack: Last-In-First-Out (LIFO) Queue: First-In-First-Out (FIFO)
30
Are loops and subroutines considered simple operations?
NO, they're considered the composition of many simple step operations
31
What is the worst case for Bubble Sort?
O(n^2)
32
What is the worst case for Selection Sort?
O(n^2)
33
What is Big O notation used for?
Primarily used for worst case or upper bound of the growth rate of a function
34
Define a Stable Sort?
Sorting method is said to be stable if it preserves the relative order of the items with duplicated keys on the list
35
What is a Heap (binary tree)?
Special kind of binary tree structure where each node is smaller (or larger) than its children
36
What is 1 advantage or disadvantage of an array?
Provides direct access to elements BUT has fixed size
37
What are weak and strong connected Directed Graphs?
Directed Graphs can be: Weakly Connected: there exists a path between every pair of nodes, regardless of the direction of the edges Strongly Connected: Same but there must be a path between every pair of nodes
38
Explain O(1) time
Constant time
39
What is the worst case for Merge Sort?
O(nlog n)
40
What is considered: a) exponential b) polynomial
a) K^x where k is constant b) x^k where k is constant
41
What is Big Omega (Ω) notation used for?
Represents the best-case performance of an algorithm (lower bound of an algorithm as lower bound is less time)
42
Explain O(log(n)) time
Logarithmic, common in searching and in same tree algorithms
43
How do you search a Hash Table?
1. Hash the target 2. Take the value of the Hash of the target and go to the slot. If the target exists it must be in that slot 3. Search in the list in the current slot using a Linear Search
44
What is a Bernoulli Trial?
The term is used to refer to an experiment on a random process that could have 2 possible outcomes * Success or failure * (Processes are independant)
45
What is a Priority Queue?
An abstract data type where items are removed based on their priority (highest to lowest)
46
What is different about traversal in a Directed Graph?
Edges have directions which makes traversal of a graph slightly different
47
How does LSD Radix Sort work?
Sorts numbers or strings one digit at a time starting from right most digit (least significant) and moving to left most digit (most significant)
48
What is an AVL tree?
*Each tree has a root node (at the top) *Every node has 0,1 or 2 child nodes *Value of left descendants are less than the right descendants
49
What is a Min Heap and a Max Heap Trees?
Min Heap: parent node is smaller than children Max Heap: parent node is larger than children (most common)
50
What is a M-ary Tree?
Entire tree has a maximum of m children and the tree is ordered Binary tree is a 2-ary tree
51
Define a nan- terminal
Node with at least one child
52
What algorithm was proposed by Tony Hoare?
Quick Sort Algorithm
53
Define an Edge
Connects Nodes normally dont have properties (values) but they may have if its a weighted graph
54
What is Heap Sort? (priority queue sorting)
Turn list into heap Then remove elements systematically to get list ordered from big to small
55
What is a Linked List?
Where nodes each contain one member that gives the location of the next node in the list
56
Define a Vertice
Vertices(v) are objects that have properties associated with them
57
What is Reverse Polish Notation?
Eliminates need for brackets- simpler and better for computers 5 8* = 40 141 12/ = 11.75
58
Explain O(n^k log n) time
Polylogarithmic Typical of algorithms that use divide and conquer
59
Explain O(2^n) time
Exponential Bad as testing all possible answers to problem When algorithms fall into this catagory designers go in search of approximation algorithms
60
What is Order Preservation in Hash Tables?
Given an ordering of keys to be hashed from: k1 < k2 < k3<...
61
What is Dijkstras Algorithm?
Finding shortest path between nodes in a graph
62
What are the 4 rotation types?
Single Right Single Left Double Right Double Left
63
What is Big Theta (θ) notation used for?
Represents average case of the growth rate of a function
64
Define a Sparse Graph
A graph in which the number of edges is much less than the possible number of edges E is much less than V^2 E = O(V)
65
What are the cons of Quick Sort?
Its recursive (more costly) Is O(n^2) in worst case Its fragile
66
What is a Doubly Linked List?
every node includes a link to the next node and previous node <>node1<->node2<->node3<->node4<> node1 and node 4 also connected
67
Define a Simple Path
A path where no node is repeated
68
For the average case what is Radix Sort's time complexity
O(n)
69
How does the Selection Sort work?
Finds the index of the minimum element each time and puts it at the start until list is sorted
70
What is the worst case of Quicksort using Recurrence?
O(n^2) T(n) = O(n) + T(n-1)
71
When are Tree Rotations used?
When the tree becomes unbalanced. They depend on balanced factors and on the location where the tree is unbalanced
72
What are the disadvantages of Linked Lists (Dynamic Lists)?
Algorithms are more complex, harder to read and debug Allocation and deallocation of memory space requires extra resources (overhead)
73
What is the time complexity cost of rebalancing a tree?
O(log n)
74
Which recurrence relation yields a running time of O(log n)?
T(n) = T(n/2) + 1
75
What are the advantages of Linked Lists (dynamic lists)?
their ability to efficiently handle insertions and deletions at any position within the list Size of the structure does not need to be declared in advance
76
Define a Node?
An object that has a name and normally info
77
Why is the worst case of Merge Sort O(n log n)?
Merge of a list size n requires O(n) comparisons Each time list is halved and halves are sorted recursively So divide and conquer recurrence applies: T(n) = 2T(n/2) + O(n)
78
What makes a good Hash Function?
One that satisfies the assumption of **uniform hosting** Meaning each key is equally likely to hash any of the m slots available
79
Define a Tree
A non-empty collection of nodes and edges which may carry properties
80
Define a Complete Graph
every pair of distinct vertices is connected by a unique edge so no vertices with no edges Maximum no. of edges ( E = V(V-1)/2)
81
What is the best case analysis of Quicksort?
T(n) = 2T(n/2) + O(n) Which equals O(n logn)
82
What are the pro's of the Quicksort?
Not difficult to implement Works in variety of situations - good general purpose Works at O(n log n) at average case
83
What is a Multilist?
A linked list whos nodes contain multiple link fields that form independant linked lists
84
What are Algorithms?
Specific instructions for getting answers
85
Define a Spanning Tree?
A connected subgraph that contains all nodes of the graph but has no cycles or loops
86
What is a Graph?
When one or more path exists between any pair of nodes its a graph
87
Define a Cycle
a path that starts from a given vertex and ends at the same vertex is called a cycle
88
What is the master theorem for Divide and Conquer?
T(n) = 2T(n/2) + O(n)
89
How to heapify a Tree?
4 ways Bottom Up: Systematically swim/ sink nodes in reverse level-order traversal Top Down: Systematically swim/sink nodes in level-order traversal
90
Define a Path?
A sequence of adjacent nodes connected by edges
91
What is algorithm efficiency split into?
Running Time Memory Space
92
Define a Balanced Tree?
Where no leaf is more than a certain amount further from the roots of any other to keep efficiency
93
What is the worst case for Radix Sort?
O(n log n)
94
What is a Balance Factor?
the height of the subtree rooted at its left child minus the height of the subtree rooted at its right child eg. +1, 0 ,-1

Data Structures and Algorithms (1 decks)

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