Brainscape's Knowledge GenomeTM

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


See full index

Algorithms > Everything > Flashcards

Everything Flashcards

1
Q

What is an algorithm?

A

a set of instructions for accomplishing a task

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

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

A

True

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

State briefly how the binary search works.

A

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

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

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?

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

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.

A

log2n

n

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

Binary search runs in _______ time

A

logarithmic

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

What’s the Big O for a linear search?

A

O(n)

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

What’s the Big O for a binary search?

A

O(logn)

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

What does the Big O notation tell you?

A

How fast an algorithm is. The worst case.

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

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

A

True

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

Big O establishes a _____-case runtime

A

worst

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

How does a selection sort algorithm work?

A

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.

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

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

A

O(n2)

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

What’s the Big O of the Quicksort Algorithm?

A

O(nlogn)

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

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

A

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

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

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

A

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

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

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

A

Random access and Sequential Access

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

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

A

Sequential Access

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

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

A

False. Only sequential access

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

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

A

Random Access

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

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

A

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

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

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

A

False.

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

Every recursive function has two parts. What are they?

A

The base case and the recursive case.

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

True or false? Quicksort is faster than selection sort

A

True

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

What is the Big O for quicksort?

A

O(nlogn)

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

Selection sort has a Big O of _____.

A

O(n2)

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

Generally speaking, how does Divide and Conquer work?

A

By breaking a problem down into smaller and smaller pieces.

28
Q

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

A

empty

one

29
Q

What is a hash function?

A

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

30
Q

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

A

maps

31
Q

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

A

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

32
Q

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.

A

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

33
Q

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.

A

True

34
Q

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

A

hash table

35
Q

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

A

True

36
Q

Python has hash tables; they’re called __________.

A

dictionaries

37
Q

A hash table maps _____ to ______.

A

keys to values

38
Q

What are collisions in hash tables?

A

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.

39
Q

What’s a simple way to avoid collisions?

A

Start a linked list at that slot

40
Q

What’s the Big O for searching hash tables?

A

O(1)

41
Q

O(1) is called ______ time.

A

constant

42
Q

True or false? Constant time means instant.

A

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

43
Q

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.

A

True

44
Q

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

A

True

45
Q

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

A

correct

46
Q

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

A

solves

47
Q

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

A

data structure

48
Q

What type of algorithm is this?

A

Insertion sort

49
Q

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

A

Analyzing

50
Q

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.

A

True

51
Q

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

A

running time

52
Q

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

A

sum

53
Q

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.

A

best

worst

54
Q

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

A

upper

55
Q

Recursive algorithms typically follow a ____ ___ _______ approach

A

divide-and-conquer

56
Q

What do divide and conquer algorithms do?

A

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.

57
Q

How does merge sort work?

A

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.

58
Q

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.

A

1

1

59
Q

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

A
60
Q

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

A

divide and conquer

61
Q

How does the divide and conquer algorithm work?

A

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.

62
Q

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

A

True

63
Q

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

A

recursive

64
Q

Describe how the binary search algorithm works.

A

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.

65
Q
A

Algorithms (1 decks)

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