Analysis of Algorithms

Question 1

What makes a bad unit test

Answer 1

Insufficient - More tests are needed to ensure code quality
Inappropriate - Some tests violate fundamental unit testing rules

Question 2

Rank function from slowest growing to fastest

Answer 2

Constant
Logarithm
Polynomial by increasing power
Exponential

Question 3

Adjacency list

Answer 3

Node is stored almost like an index where all it’s connections are stored as a list. I.e 0 -> 1->2->4

Question 4

Boyer-moore

Answer 4

RT: nm(simplified) n+m(original)
case: worst

Question 5

KMP

Answer 5

RT: n+m
case: worst

Question 6

Rabin karp

Answer 6

n+m
case: worst

Question 7

Minimum spanning tree

Answer 7

RT: m log n for a connected grpah
case: worst

Question 8

Dijkstra

Answer 8

RT: m+nlogn
Case: worst

Question 9

Graph traversal: dfs, bfs, in order, preorder, postorder

Answer 9

RT: n+M
Case: worst

Question 10

Sorting: comparison based

Answer 10

RT nlogn
Case: worst
C

Question 11

When to use Boyer-Moore

Answer 11

Boyer-Moore’s algorithm is efficient for long patterns and large texts, especially when the pattern is repetitive or the text has many similar substrings.
This makes it well-suited for searching in English, which has high repetition and redundancy.

Question 12

When to use KMP

Answer 12

Knuth-Morris-Pratt’s algorithm is efficient for short patterns and can quickly find a pattern in unprocessed text.
This makes it well-suited for short pattern/text searches where the text is not pre-processed.