Basics

Question 1

Can the Fibonacci sequence be implemented Iteratively?

Answer 1

Yes

Question 2

Can a function to find a Factorial n! be implemented Iteratively?

Answer 2

Yes

Question 3

Which functions of Binary Search Trees can be implemented Iteratively?

Answer 3

search(), insert(), delete()

Question 4

Can the value of a Binomial Coefficiant be found using an Iterative algorithm?

Answer 4

Yes

Question 5

Can the Towers of Hanoi problem be solved Iteratively?

Answer 5

No

Question 6

Which functions of a Binary Search Tree must be implemented Recursively, and why?

Answer 6

Traversals and size, because the algorithm needs to see the entire tree

Question 7

What are the key goals of a Constraint Satisfaction problem?

Answer 7

Finding no solution, or one/more solutions

Question 8

What are the key goals of a Constraint Optimization problem?

Answer 8

Maximizing or minimizing something

Question 9

How many comparisons are there in a Brute Force approach to sorting a collection of n items?

Answer 9

n!(n-1) comparisons

Question 10

What is a basic Brute Force approach to sorting a collection of n items?

Answer 10

Generate all possible sequences of the n items, check linearly if sorted by comparing adjacent pairs

Question 11

With an algorithmic sorting approach, what is the Worst Case Big-O, and what algorithms fall in this category?

Answer 11

O(n^2), Bubble, Selection, Insertion, Quick

Question 12

With an algorithmic sorting approach, what is the Best Case Big-O, and what algorithms fall in this category?

Answer 12

O(n logn), Quick, Merge, Heap

Question 13

In a Binary Search Tree, how are the children arranged?

Answer 13

Left child is always smaller than the parent, right child is always larger than the parent

Question 14

In a Binary Search Tree, how do you find a parent’s successor?

Answer 14

The next alphabetically: Smallest value in right subtree, or largest value in left subtree

Question 15

What happens if the root of a Binary Search Tree is deleted?

Answer 15

It is replaced with its successor, and the other branches are moved up in the case of gaps

Question 16

What is the sum of integers from 1 to n?

Answer 16

n(n+1)/2

Question 17

What is the sum of EVEN integers from 2 to 2n?

Answer 17

n(n+1)

Question 18

What is the sum of ODD integers from 1 to 2n-1?

Answer 18

n^2

Question 19

What is the sum of a Geometric Series?

Answer 19

[a^n+1 - 1]/[a - 1]

Question 20

What is the common form of a Geometric Series?

Answer 20

1 + a + a^2 + a^3 + … + a^n

Question 21

What is log(m) + log(n)?

Answer 21

log(m - n)

Question 22

What is log(m) - log(n)?

Answer 22

log(m/n)

Question 23

What is log(m^n)?

Answer 23

n log(m)

Question 24

What is log_c(m)/log_c(A)?

Answer 24

log_A(m)

Question 25

What is A^[log_A(m)]?

Answer 25

m

Question 26

What is A^m + A^n?

Answer 26

A^[m +n]

Question 27

What is A^m / A^n?

Answer 27

A^[m - n]

Question 28

What is [A^m]^n ?

Answer 28

A^[nm]

Question 29

What is (AB)^m ?

Answer 29

A^m B^m

Question 30

What is A^-m?

Answer 30

1/A^m

Question 31

What is A^[m/n]?

Answer 31

root_n(A^m)

Question 32

What is a full tree?

Answer 32

A tree where each node has either 0 or 2 children

Question 33

What is a perfect tree?

Answer 33

A full tree where every internal node has two children

Question 34

How many internal and leaf nodes does a perfect tree have?

Answer 34

x-1 internal nodes, and x leaf nodes

Question 35

How many internal and leaf nodes are there in a decision tree?

Answer 35

n! - 1 internal nodes, and n! leaf nodes, where n is the number of variables