Brainscape's Knowledge GenomeTM

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


See full index

CSIT203 Algorithms & Data Structures > Exam > Flashcards

Exam Flashcards

1
Q

What is a peak in an array of numbers?

A

A peak is a number greater than or equal to its neighbors. The first and last number can be a peak if greater than or equal to its only neighbor.

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

What is meant by a ‘neighbour’ in the context of peak finding?

A

A neighbour is a number immediately next to the current number

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

Is the largest value in an array always a peak?

A

Yes

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

What’s the downside of finding the max in a large array?

A

It looks at every element in the array. This can be inefficient if n is large.

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

How does the sequential search algorithm find the maximum in an array?

A

It iterates through the array, comparing each value to the current maximum and updating the maximum when a larger value is found.

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

In the sequential search, what do “values” and “position” represent?

A

“values” represents the array (like a shopping list). “position” stores the index of the current maximum.

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

Is the maximum always the only peak in an array?

A

No. A peak is a local maximum. There can be multiple peaks.

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

What does the linear search algorithm look for?

A

It looks for the first value which is greater than or equal to its neighbors, which defines a peak.

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

How efficient is the linear search for peaks?

A

Efficiency depends on the peak’s position.
Best case: 1 comparison. Worst case: n comparisons.

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

What’s the key concept behind binary search for finding peaks?

A

It divides the array, focusing on the midpoint, to find a peak by comparing with its neighbors.

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

What’s the difference between the binary search and binary search with termination?

A

Binary search with termination stops when ‘start’ is greater than or equal to ‘end’

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

In an array of length 6, is the first position indexed as 0 or 1?

A

This depends on the context. In most programming languages, arrays start at index 0, but the given pseudo-code starts at 1.

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

In a 2D table, how is a peak defined?

A

A peak is a number greater than or equal to all of its up to 4 neighbours: left, right, above, and below.

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

How does the Steepest Ascent algorithm work?

A

It compares an arbitrary element to its neighbours. If smaller, select the largest neighbour and repeat. Otherwise, a peak is found.

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

What’s the basic idea behind 2D peak finding in the middle column?

A

Find the largest element in the middle column. Compare with left and right. Throw away half based on comparison till a peak is found.

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

How efficient is the 2D peak finding algorithm?

A

Each iteration eliminates half the data. Worst case: Work down to a single column. It takes m*log2n operations.

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

What are the considerations when determining the “best” algorithm?

A

Speed, size, generality, and understandability

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

What is meant by the complexity of an algorithm?

A

It refers to the rate of growth in the number of operations as the problem size grows.

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

What is the complexity class of finding the first name in a phone book regardless of its size?

A

Constant

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

What is the complexity of finding a phone number in a directory where the numbers aren’t sorted?

A

Linear

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

When searching for a specific name in an alphabetically sorted phone book, what is the complexity?

A

Logarithmic

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

What is the complexity of the quicksort algorithm?

A

Linearithmic

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

In the quicksort example, what value is selected as the pivot initially?

A

4

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

What is the complexity of covering extra zeros in n phone books with n entries each?

A

Quadratic

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

Which complexity class grows as 2^n?

A

Exponential

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

What is meant by an algorithm having factorial complexity?

A

The number of iterations grows as n!, where n! = 1x2x3x…xn.

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

When comparing algorithms, what do we usually use to refer to the problem size?

A

n.

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

What’s an informal way to think about problem size?

A

How many things the problem contains, like the number of items to be sorted.

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

What is the main property that a number must have to be considered a peak?

A

It must be greater than or equal to its neighbors.

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

How do we informally compare the speed of algorithms?

A

By looking at how many operations they perform. More operations typically mean longer execution time.

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

What is the time complexity of a linear search for peak finding?

A

O(n).

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

Name a common method to compare algorithms

A

Big O notation

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

What does O(1) represent

A

Constant time complexity

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

Define P in complexity classes

A

It represents the class of problems that can be solved in polynomial time

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

What is a 2D peak in a matrix

A

An element greater than or equal to its adjacent elements both horizontally and vertically.

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

How does binary search help in peak finding

A

It reduces the problem size by half in each iteration

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

What does NP stand for in complexity classes

A

Nondeterministic Polynomial time

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

Which class represents problems for which answers can be verified in polynomial time?

A

NP

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

What does O(n^2) signify

A

Quadratic time complexity

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

What is an array in data structures

A

An array is a data structure consisting of a fixed number of data items of the same type.

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

How is any array element accessed?

A

Any array element is directly accessible via an index value.

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

Can arrays have more than one index?

A

Yes, those are called multidimensional arrays.

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

What special pointers are maintained in lists?

A

Head (and tail for doubly linked lists) to point to the first (and last) elements

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

How many operations does initializing an array of n elements take?

A

n operations

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

Describe a stack.

A

A stack holds multiple elements of a single type and follows the LIFO principle - Last In First Out.

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

What is the procedure to add an element to a stack?

A

‘push’

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

How can a stack be implemented?

A

With an array and an integer counter to indicate the current number of elements in the stack.

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

How do you remove an element from a stack?

A

Using the ‘pop’ procedure.

45
Q

Describe a queue

A

A queue holds multiple elements of a single type and follows the FIFO principle - First In First Out.

46
Q

How can a queue be implemented?

A

With an array and two integer counters to indicate the current start and next insertion positions.

47
Q

What is the procedure to add an element to a queue?

A

‘enqueue’

48
Q

What is a record?

A

A data structure consisting of a fixed number of items. Unlike arrays, the elements in a record may be of different types and are named.

48
Q

How can an array be used in relation to records?

A

An array may appear as a field in a record, and records may appear as elements in an array.

49
Q

How are records typically addressed?

A

As a pointer.

49
Q

How do you remove an element from a queue?

A

Using the ‘dequeue’ procedure.

50
Q

How are fields of a record accessed?

A

Via the field name.

50
Q

What are the key considerations for storing a large number of text strings

A

Minimum storage usage, quick and efficient access, and avoiding dynamic memory overhead.

51
Q

What are string pools?

A

Data structures are for storing large numbers of strings that vary widely in length.

52
Q

What is the fundamental difference between arrays and linked lists?

A

Arrays use contiguous memory, while linked lists use pointers to connect nodes.

52
Q

What are the advantages of string pools?

A

: They provide an attractive alternative for storing strings with varying lengths, offering efficiency in storage and access.

53
Q

How many iterations are required to sort a list of n numbers using insertion sort

A

n-1 iterations

53
Q

In which data structure are elements arranged in a sequence based on priority?

A

Priority Queue

54
Q

How many comparisons are typically required for insertion sort?

A

n-1 iterations

54
Q

How many comparisons are typically required for insertion sort?

A

n^2/2 comparisons.

55
Q

What is the unique approach of Merge Sort?

A

It uses a second array to hold the intermediate results and works recursively by dividing the unsorted array into two parts and merging them in order.

56
Q

In a hash table, what helps in quickly locating a data value given its search key?

A

A hash function.

56
Q

Name the two types of binary trees where values follow a specific order.

A

Binary Search Tree (BST) and Heap.

57
Q

What does a balanced tree mean in data structures?

A

A tree where the depth of two subtrees of every node never differs by more than

58
Q

What does the insertion sort start with?

A

The second element in the list

59
Q

How is the complexity of the SiftUp operation determined?

A

The complexity is log(n) because we only swap nodes on a single branch.

59
Q

What does the Siftdown operation do in a Min-Heap?

A

It moves the last node temporarily and ensures the correct order by swapping nodes as needed.

60
Q

How do you create a binary tree from an array?

A

Create a complete binary tree, keeping the nodes leftmost.

60
Q

How is a max-heap formed using siftdown?

A

Starting from a non-leaf node, elements are swapped with the largest child if they are not the largest in their subtree.

61
Q

What is a heap in data structures?

A

A heap is an essentially complete binary tree with an additional property of being either a max-heap or min-heap.

62
Q

Define Max-Heap.

A

A binary tree where the value in any node is less than or equal to the value in its parent node (except for the root node).

63
Q

How can a heap be stored?

A

A heap can be stored in an array where Heap[1] is the root of the tree, and Heap[i] has children Heap[2i] and Heap[2i+1].

64
Q

What is the purpose of the SiftUp operation?

A

To ensure the newly added element is in the correct position, maintaining the heap’s order.

65
Q

What is the sorted order for Max-Heap and Min-Heap?

A

Max-Heap sorts the list in ascending order, and Min-Heap sorts the list in descending order.

65
Q

Describe the Heapsort method briefly.

A

Convert an array to max-heap, remove the root element, place it at the end of the sorted array, and restore max-heap property using siftdown. Repeat until sorted.

66
Q

How is a heap stored in an array?

A

Heap[1] is the root, Heap[2] and Heap[3] are the children of Heap[1], and in general, Heap[i] has children Heap[2i] and Heap[2i+1].

67
Q

What’s the definition of a Binary Tree?

A

A data structure composed of nodes where each node has at most two children, organized hierarchically from a root node at the top to leaf nodes at the bottom

68
Q

What is the significance of using a second array in Merge Sort?

A

The second array holds intermediate results.

69
Q

How does Merge Sort work?

A

It divides the unsorted array into two parts recursively and merges them in order.

70
Q

How many levels are there in a merge sort for an array of n items?

A

log n levels

71
Q

How many operations does merge sort require

A

n * log n operations.

71
Q

How can you convert a non-heap into a heap?

A

By using the Makeheap/Heapify operation

72
Q

What are the children indices of Heap[i] in an array representation of a heap?

A

Heap[2i] and Heap[2i+1].

73
Q

How is the pseudocode representation of the merge sort algorithm structured?

A

It uses a temporary array, a main mergesort procedure that divides and calls itself recursively, and a merge procedure that merges two halves in order.

73
Q

What are the main steps in the Heapsort algorithm?

A

Convert the array to max-heap, repeatedly remove the root, and perform siftdown.

74
Q

How do you ensure that a heap remains a binary tree after adding a new element?

A

Add a new leaf to the end and then swap with the parents as needed to maintain the heap property.

74
Q

In the context of sorting, what is an “in-place” algorithm?

A

An algorithm that requires only a constant amount of additional space.

74
Q

Which sorting algorithm uses the divide-and-conquer strategy?

A

Merge Sort

75
Q

Which sorting algorithm is beneficial for nearly sorted data?

A

Insertion Sort

75
Q

Why is QuickSort considered efficient?

A

Because its average case time complexity is O(n log n) and it’s in-place.

75
Q

How does the Shell Sort improve upon Insertion Sort?

A

By comparing elements distant from each other and then progressively reducing the gap.

76
Q

What’s the difference between Max Heap and Min Heap?

A

In a Max Heap, every parent node has a value greater than or equal to its children. In a Min Heap, it’s the opposite.

76
Q

What are the key features of a vector?

A

It’s a dynamic array-like container, can resize automatically, allows element access using subscript, and has functions like size(), push_back(), and pop_back().

77
Q

What happens during the 1st and 2nd steps of Heapsort?

A

1st step: Makeheap requires roughly n operations. 2nd step: Siftdown requires roughly log n operations and is repeated n-1 times.

77
Q

How is the complexity of the Siftdown operation determined?

A

The complexity is log(n) because we only swap with numbers on one branch.

77
Q

How many operations does heapsort roughly require?

A

n + (n-1) x log n operations.

78
Q
A
78
Q
A
78
Q
A
79
Q
A
79
Q
A
80
Q
A
80
Q
A
80
Q
A
81
Q
A
81
Q
A
82
Q
A
83
Q
A
83
Q
A
84
Q
A
84
Q
A
84
Q
A
85
Q
A
85
Q
A

CSIT203 Algorithms & Data Structures (1 decks)

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