Brainscape's Knowledge GenomeTM

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


See full index

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
Q

Define a Graph?

A

Collection of vertices(nodes) and edges (arcs)

G = (V,E)

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

What is the best and worst case of Hash Search?

A

Worst case: O(n)

Best case: O(1) (and average case)

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

What is a Forest?

A

A collection of trees

Disjoint

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

What is the worst case of Quicksort?

A

O(n^2)

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

What structure is a Stack and what structure is a Queue

A

Stack: Last-In-First-Out (LIFO)

Queue: First-In-First-Out (FIFO)

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

Are loops and subroutines considered simple operations?

A

NO, they’re considered the composition of many simple step operations

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

What is the worst case for Bubble Sort?

A

O(n^2)

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

What is the worst case for Selection Sort?

A

O(n^2)

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

What is Big O notation used for?

A

Primarily used for worst case or upper bound of the growth rate of a function

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

Define a Stable Sort?

A

Sorting method is said to be stable if it preserves the relative order of the items with duplicated keys on the list

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

What is a Heap (binary tree)?

A

Special kind of binary tree structure where each node is smaller (or larger) than its children

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

What is 1 advantage or disadvantage of an array?

A

Provides direct access to elements

BUT has fixed size

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

What are weak and strong connected Directed Graphs?

A

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

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

Explain O(1) time

A

Constant time

39
Q

What is the worst case for Merge Sort?

A

O(nlog n)

40
Q

What is considered:

a) exponential

b) polynomial

A

a) K^x where k is constant

b) x^k where k is constant

41
Q

What is Big Omega (Ω) notation used for?

A

Represents the best-case performance of an algorithm (lower bound of an algorithm as lower bound is less time)

42
Q

Explain O(log(n)) time

A

Logarithmic, common in searching and in same tree algorithms

43
Q

How do you search a Hash Table?

A
  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
Q

What is a Bernoulli Trial?

A

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
Q

What is a Priority Queue?

A

An abstract data type where items are removed based on their priority (highest to lowest)

46
Q

What is different about traversal in a Directed Graph?

A

Edges have directions which makes traversal of a graph slightly different

47
Q

How does LSD Radix Sort work?

A

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
Q

What is an AVL tree?

A

*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
Q

What is a Min Heap and a Max Heap Trees?

A

Min Heap: parent node is smaller than children

Max Heap: parent node is larger than children (most common)

50
Q

What is a M-ary Tree?

A

Entire tree has a maximum of m children and the tree is ordered

Binary tree is a 2-ary tree

51
Q

Define a nan- terminal

A

Node with at least one child

52
Q

What algorithm was proposed by Tony Hoare?

A

Quick Sort Algorithm

53
Q

Define an Edge

A

Connects Nodes

normally dont have properties (values) but they may have if its a weighted graph

54
Q

What is Heap Sort? (priority queue sorting)

A

Turn list into heap

Then remove elements systematically to get list ordered from big to small

55
Q

What is a Linked List?

A

Where nodes each contain one member that gives the location of the next node in the list

56
Q

Define a Vertice

A

Vertices(v) are objects that have properties associated with them

57
Q

What is Reverse Polish Notation?

A

Eliminates need for brackets- simpler and better for computers

5 8* = 40

141 12/ = 11.75

58
Q

Explain O(n^k log n) time

A

Polylogarithmic

Typical of algorithms that use divide and conquer

59
Q

Explain O(2^n) time

A

Exponential

Bad as testing all possible answers to problem

When algorithms fall into this catagory designers go in search of approximation algorithms

60
Q

What is Order Preservation in Hash Tables?

A

Given an ordering of keys to be hashed from:

k1 < k2 < k3<… <kj

then we should expect that

hash(k1) < hash(k2) < hash(k3) <… M hash(kj)

When you hash the keys the hashes should follow the same hierarchy in size

61
Q

What is Dijkstras Algorithm?

A

Finding shortest path between nodes in a graph

62
Q

What are the 4 rotation types?

A

Single Right

Single Left

Double Right

Double Left

63
Q

What is Big Theta (θ) notation used for?

A

Represents average case of the growth rate of a function

64
Q

Define a Sparse Graph

A

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
Q

What are the cons of Quick Sort?

A

Its recursive (more costly)

Is O(n^2) in worst case

Its fragile

66
Q

What is a Doubly Linked List?

A

every node includes a link to the next node and previous node

<>node1<->node2<->node3<->node4<>

node1 and node 4 also connected

67
Q

Define a Simple Path

A

A path where no node is repeated

68
Q

For the average case what is Radix Sort’s time complexity

A

O(n)

69
Q

How does the Selection Sort work?

A

Finds the index of the minimum element each time and puts it at the start until list is sorted

70
Q

What is the worst case of Quicksort using Recurrence?

A

O(n^2)

T(n) = O(n) + T(n-1)

71
Q

When are Tree Rotations used?

A

When the tree becomes unbalanced. They depend on balanced factors and on the location where the tree is unbalanced

72
Q

What are the disadvantages of Linked Lists (Dynamic Lists)?

A

Algorithms are more complex, harder to read and debug

Allocation and deallocation of memory space requires extra resources (overhead)

73
Q

What is the time complexity cost of rebalancing a tree?

A

O(log n)

74
Q

Which recurrence relation yields a running time of O(log n)?

A

T(n) = T(n/2) + 1

75
Q

What are the advantages of Linked Lists (dynamic lists)?

A

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
Q

Define a Node?

A

An object that has a name and normally info

77
Q

Why is the worst case of Merge Sort O(n log n)?

A

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
Q

What makes a good Hash Function?

A

One that satisfies the assumption of uniform hosting

Meaning each key is equally likely to hash any of the m slots available

79
Q

Define a Tree

A

A non-empty collection of nodes and edges which may carry properties

80
Q

Define a Complete Graph

A

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
Q

What is the best case analysis of Quicksort?

A

T(n) = 2T(n/2) + O(n)

Which equals O(n logn)

82
Q

What are the pro’s of the Quicksort?

A

Not difficult to implement

Works in variety of situations - good general purpose

Works at O(n log n) at average case

83
Q

What is a Multilist?

A

A linked list whos nodes contain multiple link fields that form independant linked lists

84
Q

What are Algorithms?

A

Specific instructions for getting answers

85
Q

Define a Spanning Tree?

A

A connected subgraph that contains all nodes of the graph but has no cycles or loops

86
Q

What is a Graph?

A

When one or more path exists between any pair of nodes its a graph

87
Q

Define a Cycle

A

a path that starts from a given vertex and ends at the same vertex is called a cycle

88
Q

What is the master theorem for Divide and Conquer?

A

T(n) = 2T(n/2) + O(n)

89
Q

How to heapify a Tree?

A

4 ways

Bottom Up:

Systematically swim/ sink nodes in reverse level-order traversal

Top Down:

Systematically swim/sink nodes in level-order traversal

90
Q

Define a Path?

A

A sequence of adjacent nodes connected by edges

91
Q

What is algorithm efficiency split into?

A

Running Time

Memory Space

92
Q

Define a Balanced Tree?

A

Where no leaf is more than a certain amount further from the roots of any other to keep efficiency

93
Q

What is the worst case for Radix Sort?

A

O(n log n)

94
Q

What is a Balance Factor?

A

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.
© 2024 Bold Learning Solutions. Terms and Conditions