Everything

Question 1

What is an algorithm?

Answer 1

a set of instructions for accomplishing a task

Question 2

True or False? For binary search to work, its elements have to be sorted.

Answer 2

True

Question 3

State briefly how the binary search works.

Answer 3

With binary search, you guess the middle number and eliminate half the remaining numbers every time.

Question 4

Suppose you’re looking for a word in the dictionary. The dictionary has 240,000 words. In the worst case, how many steps do you think each search will take?

Simple Search?
Binary Search?

Answer 4

Question 5

In general, for any list of size n, binary search will take ______ steps to run in the worst case, whereas simple search will take __ steps.

Answer 5

log₂n

n

Question 6

Binary search runs in _______ time

Answer 6

logarithmic

Question 7

What’s the Big O for a linear search?

Answer 7

O(n)

Question 8

What’s the Big O for a binary search?

Answer 8

O(logn)

Question 9

What does the Big O notation tell you?

Answer 9

How fast an algorithm is. The worst case.

Question 10

True or false? Big O tells you how fast the algorithm grows.

Answer 10

True

Question 11

Big O establishes a _____-case runtime

Answer 11

worst

Question 12

How does a selection sort algorithm work?

Answer 12

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

Question 13

What’s the Big O of a selection sort algorithm?

Answer 13

O(n²)

Question 14

What’s the Big O of the Quicksort Algorithm?

Answer 14

O(nlogn)

Question 15

If you want to insert an element into the middle of a list, what’s better to use, arrays or linked lists?

Answer 15

Linked lists, since in arrays you would have to shift everything down.

Question 16

What if you want to delete an element from a list? Which is better? Array or Linked List.

Answer 16

Linked List. With arrays, you would have to shift all of the elements.

Question 17

When searching for elements, what are the two types of access?

Answer 17

Random access and Sequential Access

Question 18

_______ ________ means reading elements one by one, starting at the first element.

Answer 18

Sequential Access

Question 19

True or False? Linked lists can do random access or sequential access.

Answer 19

False. Only sequential access

Question 20

_______ _______ means you can jump directly to the 10th element.

Answer 20

Random Access

Question 21

True or false? Arrays are faster at reads than linked lists

Answer 21

True. Arrays allow for random access while linked lists only allow for sequential access

Question 22

True or false? There is a performance benefit to using recursion

Answer 22

False.

Question 23

Every recursive function has two parts. What are they?

Answer 23

The base case and the recursive case.

Question 24

True or false? Quicksort is faster than selection sort

Answer 24

True

Question 25

What is the Big O for quicksort?

Answer 25

O(nlogn)

Question 26

Selection sort has a Big O of \_\_\_\_\_.

Answer 26

O(n²)

Question 27

Generally speaking, how does Divide and Conquer work?

Answer 27

By breaking a problem down into smaller and smaller pieces.

Question 28

If you’re using D&C on a list, the base case is probably an \_\_\_\_\_ array or an array with ____ element.

Answer 28

empty one

Question 29

What is a hash function?

Answer 29

A hash function is a function where you put in a string and you get back a number.

Question 30

In technical terminology, we’d say that a hash function “\_\_\_\_\_\_\_\_\_\_ strings to numbers.”

Answer 30

maps

Question 31

If you feed an "apple" into the hash function, and you get back the number 3, what is the 3?

Answer 31

It can be the index location where you stored price of an apple.

Question 32

True or False? A hash function needs to be consistent. For example, suppose you put in “apple” and get back “4”. Every time you put in “apple”, you should get “4” back.

Answer 32

True. Without this, your hash table won’t work.

Question 33

True or false? The hash function knows how big your array is and only returns valid indexes. So if your array is 5 items, the hash function doesn’t return 100.

Answer 33

True

Question 34

Put a hash function and an array together, and you get a data structure called a _______ \_\_\_\_\_\_\_.

Answer 34

hash table

Question 35

True or false? Hash tables are sometimes referred to as hash maps, maps, dictionaries, and associative arrays.

Answer 35

True

Question 36

Python has hash tables; they’re called \_\_\_\_\_\_\_\_\_\_.

Answer 36

dictionaries

Question 37

A hash table maps _____ to \_\_\_\_\_\_.

Answer 37

keys to values

Question 38

What are collisions in hash tables?

Answer 38

Hash functions don't always give you a unique number when they're fed a string. Sometimes they give the same number to two different strings. That can overwrite elements in an array. That's called a collision: when two keys have been assigned to the same slot.

Question 39

What's a simple way to avoid collisions?

Answer 39

Start a linked list at that slot

Question 40

What's the Big O for searching hash tables?

Answer 40

O(1)

Question 41

O(1) is called ______ time.

Answer 41

constant

Question 42

True or false? Constant time means instant.

Answer 42

False. It means that the time will stay the same regardless of how long, for example, a hash table is.

Question 43

True or false? Tt doesn’t matter whether your hash table has 1 element or 1 billion elements—getting something out of a hash table will take the same amount of time.

Answer 43

True

Question 44

True or false? Because many programs use it as an intermediate step, sorting is a fundamental operation in computer science.

Answer 44

True

Question 45

An algorithm is said to be ______ if, for every input instance, it halts with the correct output.

Answer 45

correct

Question 46

We say that a correct algorithm ______ the given computational problem.

Answer 46

solves

Question 47

A ______ \_\_\_\_\_\_\_\_ is a way to store and organize data in order to facilitate access and modifications.

Answer 47

data structure

Question 48

What type of algorithm is this?

Answer 48

Insertion sort

Question 49

\_\_\_\_\_\_\_\_\_ an algorithm has come to mean predicting the resources that the algorithm requires.

Answer 49

Analyzing

Question 50

True or false? Insertion Sort can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are.

Answer 50

True

Question 51

The _______ \_\_\_\_\_\_ of an algorithm on a particular input is the number of primitive operations or “steps” executed.

Answer 51

running time

Question 52

The running time of the algorithm is the ___ of running times for each statement executed

Answer 52

sum

Question 53

In insertion sort, if a list is already sort in ascending order we get the ____ runtime result and the _____ case if the list is sorted in descending order.

Answer 53

best worst

Question 54

The worst-case running time of an algorithm gives us an _____ bound on the running time for any input.

Answer 54

upper

Question 55

Recursive algorithms typically follow a ____ \_\_\_ _______ approach

Answer 55

divide-and-conquer

Question 56

What do divide and conquer algorithms do?

Answer 56

they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem.

Question 57

How does merge sort work?

Answer 57

Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each. Conquer: Sort the two subsequences recursively using merge sort. Combine: Merge the two sorted subsequences to produce the sorted answer.

Question 58

In merge sort, recursion “bottoms out” when the sequence to be sorted has length \_\_\_, in which case there is no work to be done, since every sequence of length ____ is already in sorted order.

Answer 58

1 1

Question 59

Briefly illustrate how you would merge the elements in a merge sort.

Answer 59

Question 60

In computer science, ______ \_\_\_\_ ______ is an algorithm design paradigm based on multi-branched recursion

Answer 60

divide and conquer

Question 61

How does the divide and conquer algorithm work?

Answer 61

A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

Question 62

True or false? The divide-and-conquer paradigm often helps in the discovery of efficient algorithms.

Answer 62

True

Question 63

Divide-and-conquer algorithms are naturally implemented as ________ procedures.

Answer 63

recursive

Question 64

Describe how the binary search algorithm works.

Answer 64

In each step, the algorithm compares the input element x with the value of the middle element in array. If the values match, return the index of middle. Otherwise, if x is less than the middle element, then the algorithm recurs for left side of middle element, else recurs for right side of middle element.