Ch 2: Algorithm Analysis & Lists

Question 1

what is linear search?

Answer 1

a search algorithm that starts from the beginning of a list and checks each element until the search key is found or the end of the list is received
- will compare each element if the key is not found

Question 2

explain linear search algorithm

Answer 2

a single counter starts from the first item and compares it against the search key, if it matches the item is returned otherwise the counter moves to the next item and repeats. if the search key is not found then the counter will have compared each item and “null” is returned

Question 3

what is binary search?

Answer 3

a faster algorithm for searching a list if the list’s elements are sorted & directly accessible (array)

Question 4

explain binary search algorithm

Answer 4

first, the middle element of the list is checked, if the search key is found then it is returned. otherwise, if the search key is less than the middle, the middle of the first half of the list is checked for the search key or if the search key is more than the middle, the middle of the second half of the list is checked for the search key. continue to check middle by splitting the list in half

Question 5

what is the equation to find the middle

Answer 5

0+(N-1) / 2

Question 6

what are constant time operations?

Answer 6

an operation that for a given processor, always operates in the same amount of time, regardless of input value

Question 7

what is an example of a constant time operation?

Answer 7

multiplication because the same amount of numbers being multiplied will always have the same time
ex. 12 takes same time as 301000

Question 8

what is not an example of a constant time operation?

Answer 8

string concatenation because more characters must be copied for larger strings

Question 9

what affects CTO?

Answer 9

programming language and hardware running the code

Question 10

what is lower and upper bound?

Answer 10

• lower bound: a function f(N) that is <= the best case T(N) for all values N >= 1
• upper bound: a function f(N) that is >= the worse case T(N) for all values N >= 1

Question 11

what is an asymptotic notation?

Answer 11

classification of runtime complexity that uses functions that indicate the growth rate of a bounding function

Question 12

what are the three asymptotic notations that are commonly used in complexity analysis?

Answer 12

O notation: provides a growth rate for an algorithm’s upper bound
Ω notation: provides a growth rate for an algorithm’s lower bound
Θ notation: provides a growth rate that is both an upper and lower bound

Question 13

what are the rules for Big O notation?

Answer 13

1. if f(N) is a sum of several terms, the highest order term ( the one with tte fastest growth rate ) is kept and others are discarded
2. if f(N) has a term that is a product of several factors, all constants ( those that are not in terms of N ) are omitted

Question 14

explain the binary search recursive algorithm

Answer 14

outer function: takes in list
inner function: takes in list (subset), low, high, key
- base case: checks if the low is greater than high, then
- gets mid
- checks if the middle number is less than or greater than the key and makes recursive call with either first half or second half of list
- else returns the middle number

Question 15

what is a recurrence relation?

Answer 15

a function f(N) that is defined in terms of the same function operating on a value < N

Question 16

what is a recursion tree?

Answer 16

a visual diagram of an operation done by a recursive function, that separates operations done directly by the function and operations done by recursive calls

Question 17

explain the different parts of a recursion tree

Answer 17

• root node represents k operations inside the first function call
• recursive operations are represented below the node
• tree’s height corresponds to the number of recursive calls
• an algorithm that performs N operations and then 2 recursive calls will have N/2, continues to divide by 2 as more recursive calls occur

Question 18

what is a singly-linked list?

Answer 18

a data structure for implementing a list ADT, where each node has data and a pointer to the next node

Question 19

what is a positional list?

Answer 19

a list where elements contain pointers to the next and/or previous elements in the list

Question 20

explain append operation for a singly-linked list

Answer 20

• the node that is to be added is entered into the function
• the tails->next is set to the new node, then tail is set to the new node
• if head is null, then both head and tail point to the node

Question 21

explain prepend operation for a singly-linked list

Answer 21

• the node that is to be added is entered into the function
• new node->next is set to head, then head points to the new node
• if head is null, then head and tail point to the new node

Question 22

explain insertafter operation for a singly-linked list

Answer 22

• the node that is to be added is entered into the function
• if the new node is to be the first node, then prepend
• if new node is to be the last node, then append
• if new node is to be inserted in the middle, then a pointer to the node of the location before is created, then new node’s next is set to before pointer’s next, and before pointer’s next is set to the new node

Question 23

explain removeafter operation for a singly-linked list

Answer 23

• the node that is to be removed is entered into the function
• a pointer to the node before is created aka curNode, and a pointer to befores->next->next is created, aka sucNode
• if curNode is null then sucNode points to heads->next
• if sucNode is null then tail
• removing from middle: if curNode’s next pointer is not null, then sucNode points to curNode’s next->next node

Question 24

what is a doubly-linked list?

Answer 24

a data structure for implementing a list ADT, where each node has data a pointer to the next node, and a pointer to the previous node

Question 25

what is list traversal?

Answer 25

an algorithm that visits all nodes in the list once and performs an operation on each node

Question 26

explain list traversal algorithm

Answer 26

a pointer first starts at the list’s head and performs the operation as long as it is not null, then the pointer moves onto the next node and performs operation again and repeats until the node is null

Question 27

explain insert sort for doubly-linked lists

Answer 27

Insertion sort for a doubly-linked list operates similarly to the insertion sort algorithm used for arrays. Starting with the second list element, each element in the linked list is visited. Each visited element is moved back as needed and inserted into the correct position in the list’s sorted portion. The list must be a doubly-linked list, since backward traversal is not possible in a singly-linked list.

Question 28

explain insert sort for singly-linked lists

Answer 28

Insertion sort can sort a singly-linked list by changing how each visited element is inserted into the sorted portion of the list. The standard insertion sort algorithm traverses the list from the current element toward the list head to find the insertion position. For a singly-linked list, the insertion sort algorithm can find the insertion position by traversing the list from the list head toward the current element.

Since a singly-linked list only supports inserting a node after an existing list node, the ListFindInsertionPosition algorithm searches the list for the insertion position and returns the list node after which the current node should be inserted. If the current node should be inserted at the head, ListFindInsertionPosition return null.

Question 29

what aspect of linked lists makes adapting array-based sorting algorithms to inked lists difficult?

Answer 29

elements in the list cannot be accessed by index

Question 30

what is a dummy node (header node)?

Answer 30

a node with an unused data member that always resides at the head of the list and cannot be removed

Question 31

explain the advantage of using dummy nodes

Answer 31

using dummy nodes simplifies the algorithms for linked lists because head and tail pointers are never null and so the algorithm does not need to account for when head and tail is null

Question 32

explain the advantage of using dummy nodes

Answer 32

using dummy nodes simplifies the algorithms for linked lists because head and tail pointers are never null and so the algorithm does not need to account for when head and tail is null

Question 33

explain the forward traversal recursive algorithm

Answer 33

Forward traversal through a linked list can be implemented using a recursive function that takes a node as an argument. If non-null, the node is visited first. Then, a recursive call is made on the node’s next pointer, to traverse the remainder of the list.

The ListTraverse function takes a list as an argument, and searches the entire list by calling ListTraverseRecursive on the list’s head.

Question 34

what is bubbly sort?

Answer 34

a sorting algorithm that iterates through a list, comparing and swapping adjacent elements if the second element is less than the first element

Question 35

explain the bubble sort algorithm

Answer 35

Bubble sort uses nested loops. Given a list with N elements, the outer i-loop iterates N - 1 times. Each iteration moves the largest element into sorted position. The inner j-loop iterates through all adjacent pairs, comparing and swapping adjacent elements as needed, except for the last i pairs that are already in the correct position,.

Question 36

why is bubble sort impractical for real-world use?

Answer 36

bubble sorts run time is very large, O(N^2) because of their nested for loops

Question 37

what is bucket sort?

Answer 37

a numerical sorting algorithm that distributes numbers into buckets, sorts each bucket with an additional sorting algorithm and then concatenates buckets together to build the sort result

bucket: a container for numerical values in a specific range

Question 38

explain bucket sort algorithm

Answer 38

Bucket sort first creates a list of buckets, each representing a range of numerical values. Collectively, the buckets represent the range from 0 to the maximum value in the array. For N buckets and a maximum value of M, each bucket represents M+1 / N values. Each array element is placed in the appropriate bucket. Then, each bucket is sorted with an additional sorting algorithm. Lastly, all buckets are concatenated together in order, and copied to the original array.

Question 39

what is the difference between a list data structure and a list node data structure?

Answer 39

a list data structure is a data structure containing the list’s head and tail, and may also include additional information, such as the list’s size, while a list node data structure always maintains the data for each list element, including the element’s data and pointers to the other list element

Question 40

is a list data structure required to implement a linked list?

Answer 40

it is not required

Question 41

why is a list data structure helpful when implementing linked lists?

Answer 41

a list data structure offers a convenient way to store the list’s head and tail

Question 42

what is a circular linked list?

Answer 42

a linked list where the tail node’s next pointer points to the head of the list, instead of null

Question 43

what is a circular linked list?

Answer 43

a linked list where the tail node’s next pointer points to the head of the list, instead of null

Question 44

when does a traversal of a circular linked list end?

Answer 44

ends after reaching the head node a second time instead of when reaching null