Brainscape's Knowledge GenomeTM

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


See full index

COSC90 Algo Midterms > Identification > Flashcards

Identification Flashcards

1
Q

An algorithm known for its sorting method that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

A

Bubble Sort

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

A type of algorithmic paradigm involves breaking down a problem into smaller subproblems, solving each subproblem, and combining the solutions.

A

Divide and Conquer

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

A sorting algorithm has an average and worst-case time complexity of O(n log n) and is based on the divide-and-conquer strategy.

A

Merge Sort

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

A searching algorithm works by repeatedly dividing the search range in half; requires the array to be sorted in order to efficiently search for an element by repeatedly dividing the search interval in half.

A

Binary Search

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

An algorithmic approach involves solving a problem by solving smaller instances of the same problem and combining their solutions.

A

Recursion

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

A data structure operates on a Last In, First Out (LIFO) principle.

A

Stack

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

This algorithm is known for its efficiency in sorting small data sets and is an in-place, comparison- based sorting algorithm.

A

Insertion Sort

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

A sorting algorithm that repeatedly selects the maximum element and puts it at the end of the list in each iteration.

A

Selection Sort

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

It is a step-by-step procedure or a set of rules designed for solving a specific problem or accomplishing a particular task.

A

Algorithm

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

It is a way of organizing and storing data to perform operations efficiently.

A

Data Structure

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

This is a simple search algorithm that sequentially checks each element of the list until it finds the desired element.

A

Linear Search

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

It does not necessarily find the shortest path in a graph. It explores as far as possible along each branch before backtracking.

A

Depth-First Search (DFS)

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

It uses a queue data structure for traversal, not a stack. This ensures that nodes are visited in the order of their distance from the starting node.

A

Breadth-First Search (BFS)

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

These are algorithms used to systematically visit every vertex and edge in a graph, typically starting from a specified vertex.

A

Graph Traversal Algorithms

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

When evaluating an algorithm’s performance about the size of the input data it processes, which concept are you primarily concerned with?

A

Algorithm Complexity

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

Which concept measures how the running time of an algorithm grows with the size of the input?

A

Time Complexity

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

What term refers to the memory requirements of an algorithm as a function of the input size?

A

Space Complexity

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

Which term describes step-by-step procedures or formulas for solving problems?

A

Algorithms

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

What programming technique involves a function calling itself to solve smaller instances of the same problem?

A

Recursion

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

Which strategy involves breaking a problem into smaller subproblems, solving them independently, and then combining their solutions to solve the original problem?

A

Divide and Conquer

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

Which approach makes locally optimal choices at each step in the hope that the overall solution will be globally optimal?

A

Greedy Algorithm

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

What technique breaks a problem into overlapping subproblems, solves each subproblem only once, and stores the solutions to subproblems in a table to avoid redundant computations?

A

Dynamic Programming

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

Which method exhaustively searches through all possible solutions and selects the one that satisfies the problem constraints?

A

Brute Force

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

What approach systematically searches through all possible solutions by making choices and backtracking when a choice leads to a dead end?

A

Backtracking

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

In a scenario where you want to implement an algorithm that offers a degree of unpredictability while ensuring good performance, which option would you most likely consider?

A

Randomized Algorithm

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

You’re tasked with solving problems related to graphs. Which type of algorithm would you choose for this purpose?

A

Graph Algorithms

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

Imagine you need to address issues concerning flow in networks, such as identifying maximum flow or minimum cut. Which algorithm category would you explore?

A

Network Flow Algorithms

28
Q

When describing how a function behaves as its input approaches infinity, which notation would you use?

A

Asymptotic Notation

29
Q

In determining the maximum amount of resources an algorithm requires for any input of a given size, what complexity concept would you examine?

A

Worst-Case Complexity/Worse-Case Complexity

30
Q

When discussing the average amount of resources an algorithm necessitates over all possible inputs of a given size, which complexity term would you refer to?

A

Average-Case Complexity

31
Q

In a system where elements can only be inserted or deleted at one end, what data structure would you employ?

A

Stack

32
Q

If you need a structure where items are inserted at one end and deleted at the other, what type of list would you utilize?

A

Queues

33
Q

When representing each element of a data object in a cell or node, what list structure would you use?

A

Linked List

34
Q

In the context of arranging records in a particular order, what process would you employ?

A

Sorting

35
Q

Which sorting algorithm compares adjacent elements and swaps them if they’re in the wrong order?

A

Bubble Sort

36
Q

What algorithm repeatedly selects the minimum element from an unsorted region and swaps it with the first element of the unsorted region?

A

Selection Sort

37
Q

Which algorithm builds a sorted array one element at a time by inserting each element into its correct position within the sorted region?

A

Insertion Sort

38
Q

Which divide-and-conquer algorithm selects a pivot element, partitions the array into two sub-arrays, and recursively sorts the sub-arrays?

A

Quick Sort

39
Q

What non-linear data structure organizes data in a hierarchical structure?

A

Trees

40
Q

Which search algorithm finds the position of a target value within a sorted array or list?

A

Binary Search

41
Q

What term defines a particular way of organizing and storing data efficiently?

A

Data Structure

42
Q

What is a collection of elements, each identified by an index or a key?

A

Arrays

43
Q

What term refers to the process of repeating a set of instructions or steps in a systematic way?

A

Iteration

44
Q

An algorithm must terminate after a finite number of steps.

A

Finiteness

45
Q

Each step of the algorithm must be precisely defined.

A

Definiteness

46
Q

An algorithm should have zero or more inputs.

A

Input

47
Q

An algorithm should produce one or more outputs.

A

Output

48
Q

Every step in an algorithm should be doable using basic operations.

A

Effectiveness

49
Q

These are basic data structures that directly operate upon the machine instructions.

A

Primitive Data Structures

50
Q

These are high-level data structures that model real-world entities and operations.

A

Abstract Data Structures

51
Q

A contiguous block of memory elements, each element is identified by an array index.

A

Arrays

52
Q

Elements are stored in nodes, each node pointing to the next node in the sequence.

A

Linked Lists

53
Q

Elements are stored in nodes, each node pointing to the next node in the sequence.

A

Linked Lists

54
Q

A Last In, First Out (LIFO) data structure where elements are inserted and removed from the same end.

A

Stacks

55
Q

A First In, First Out (FIFO) data structure where elements are inserted at the rear and removed from the front.

A

Queues

56
Q

It provides an upper bound on the growth rate of a function.

A

Big O Notation (O)

57
Q

It provides a lower bound on the growth rate of a function.

A

Omega Notation (Ω)

58
Q

It provides both upper and lower bounds, indicating tight bounds on the growth rate of a function.

A

Theta Notation (Θ)

59
Q

A data structure that implements an associative array abstract data type, where keys are mapped to values.

A

Hash Tables

60
Q

A specialized tree-based data structure that satisfies the heap property.

A

Heaps

61
Q

These are self-balancing tree data structures that maintain sorted data and are commonly used in databases and file systems for efficient insertion, deletion, and searching operations.

A

B- Trees and B+ Trees

62
Q

This is a data structure used to keep track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It supports two main operations: finding which set a particular element belongs to and merging two sets.

A

Disjoint Set/Union Find

63
Q

Also known as a prefix tree, is a tree-like data structure used to store a dynamic set of strings where the keys are usually strings. It supports efficient prefix-based searching and insertion operations.

A

Trie

64
Q

This is a tree data structure used for storing intervals or segments of data. It allows querying and updating the segments efficiently, often used in problems involving range queries and updates.

A

Segment Tree

65
Q

Also called a binary indexed tree, is a data structure that supports efficient prefix sum queries and updates over an array of numbers. It’s particularly useful when dealing with cumulative frequency tables.

A

Fenwick Tree

66
Q

These are data structures used for efficiently storing and querying the suffixes of a string. Suffix arrays are arrays of the starting positions of suffixes sorted lexicographically, while suffix trees are trees that represent all suffixes of a string in a compressed form.

A

Suffix Array and Suffix Tree

67
Q

Systematically searches for an optimal solution by exploring the entire search space and pruning branches using bounding functions.

A

Branch and Bound

COSC90 Algo Midterms (2 decks)

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