WGU C949 Essentials FREQUENTLY TESTED QUESTIONS WITH CORRECT ANSWERS | BRAND NEW!

What are the 6 Characteristics of an Algorithm?

Unambiguity

Finiteness -finite number of steps, defined endpoint or output

Well-defined inputs

Effectiveness & Feasibility - doable and practicable.

Language independence

Well-defined outputs

what are the 8 Factors of an Algorithm?

Modularity

Correctness

Maintainability

Functionality

Robustness

User-friendly

Simplicity

Extensibility

What is a straightforward type of algorithm that exhaustively tries all possible solutions?

Brute Force Algorithm

What algorithm method breaks a problem into smaller, similar subproblems and applies itself recursively?

Recursive Algorithm

Which type of algorithm is used to transform data into a secure, unreadable form using cryptographic techniques?

Encryption Algorithm

Which type of algorithm explores potential solutions by undoing choices when they lead to an incorrect outcome?

Backtracking Algorithm

Which type of algorithm is designed to find a specific target within a dataset?

Searching Algorithm

Which type of algorithm aims to arrange elements in a specific order?

Sorting Algorithm

Which type of algorithm converts data into a fixed-size hash value for rapid access in hash tables?

Hashing Algorithm

Which algorithm breaks a complex problem into smaller subproblems and combines their solutions?

Divide and Conquer Algorithm

Which type of algorithm makes locally optimal choices at each step in the hope of finding a global optimum?

Greedy Algorithm

Which type of algorithm stores and reuses intermediate results to enhance efficiency in solving complex problems?

Dynamic Programming Algorithm

Which type of algorithm utilizes randomness in its steps to achieve a solution?

Randomized Algorithm

What uses asymptotic notation to determine the algorithm's time and space complexity before its run?

Priori analysis

What is an analysis that measures the speed of an algorithm by running and timing it?

Posteriori analysis

What are the three main asymptotic notations in asymptotic analysis, and what do they calculate?

Big O Notation - worst case

Omega Notation - best case

Theta Notation - average case

What is merge sort's method and time complexity?

Recursively divides the list into halves down to one element, then sorts as it merges them.

O(n log⁡ n) for all cases.

What is quick sort's method and time complexity?

Partitions a section of the unsorted list into a left part and a right part, based on a chosen element within the list called the pivot.

O(n log n) average, O(n^2) worst

How do you determine the midpoint for quicksort?

middle value - round down if list is even

What is a heap sort's method and time complexity?

Uses a heap data structure to repeatedly extract the maximum (or minimum) element and rebuilds the heap

O(n log n) all cases

What is a radix sort's method and time complexity?

Places integers into buckets based on the least significant digit's value then repeating

O(n) in all cases

What is a selection sort's method and time complexity?

The selection sort algorithm searches the unsorted part of the array for the smallest element and swaps it to the sorted part.

O(n^2) in all cases

What is a insertion sort's method and time complexity?

Takes an element from the unsorted part and repeatedly swaps with the element next to it until it is in the sorted part.

O(n^2) in all cases apart from O(n) if already sorted

What is a bubble sort's method and time complexity?

Iterates through a list, comparing and swapping adjacent elements

O(n^2) in all cases

What is a bucket sort's method and time complexity?

Distributes elements into buckets for numerical values in a specific range and sorts each bucket individually, then concatenates buckets together

O(n^2) worst case, O(n) average case

What is a shell sort's method and time complexity?

Uses gap values to determine number of interleaved lists then sorts each list individually with a variant of the insertion sort. It finishes by performing a standard insertion sort on the entire array.

O(n^2) worst case, O(n^1.5) average case, O(n log n) best case

What are the main 7 Big O notations?

1. O(1) - Constant Time

2. O(log n) - Logarithmic Time

3. O(n) - Linear Time

4. O(n log n) - Log-Linear Time

5. O(n^2) - Quadratic Time

6. O(2^n) - Exponential Time

7. O(n!) - Factorial Time

What is a data structure that stores subitems, often called fields, with a name associated with each subitem?

Record

What is a data structure that stores an ordered list of items, where each item is directly accessible by a positional index.

Array

What is a data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node?

Linked List

What is a data structure in which each node stores data and has up to two children, known as a left child and a right child?

Binary Tree

What is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array?

Hash Table

What is a tree data structure that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys?

Max-heap

What is a tree data structure that maintains the simple property that a node's key is less than or equal to the node's childrens' keys?

Min-heap

What is a data structure for representing connections among items?

Graph

What are a set of problems for which no known efficient algorithm exists?

NP-complete problems

What are 3 characteristics of NP-complete problems?

No efficient algorithm has been found to solve one

No one has proven that an efficient algorithm to solve one is impossible.

If an efficient algorithm exists for one, then all can be solved efficiently.

What is the underlying structure of a tuple?

dynamic array

What is the underlying structure of a list?

array or linked list

What is the underlying structure of a dynamic array?

array

What is the underlying structure of a stack?

linked list

What is the underlying structure of a queue?

linked list

What is the underlying structure of a deque?

linked list

What is the underlying structure of a bag?

hash table, array or linked list (add & remove easily)

What is the underlying structure of a set?

hash table or binary search tree (checks if distinct)

what is the underlying structure of a priority queue?

heap

what is the underlying structure of a dictionary?

hash table, binary search tree

ADT for holding ordered data.

list

ADT for holding ordered data and allowing indexed access

dynamic array

ADT in which items are only inserted on or removed from the top

stack

ADT in which items are inserted at the end and removed from the front

queue

ADT in which items can be inserted and removed at both the front and back

deque

ADT for storing items in which the order does not matter and duplicate items are allowed.

bag

ADT for a collection of distinct items

set

ADT where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority

priority queue

ADT that associates (or maps) keys with values

dictionary

When is an array better than a linked list?

fast access to elements by index

data size is relatively static

when is a linked list better than an array?

frequent insertions/deletions

grows and shrinks as needed

don't require random access to elements

what is an underlying data structure for hash table with chaining?

doubly linked list

How do you calculate the starting point for a binary search?

middle or round down if even number