Algorithm Analysis
What are two resources used by algorithms in general?
time and memory
Write an algorithm to preform binary search
int binarySearch(int arr[], int size, int key) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid; // Key found at index mid
else if (arr[mid] < key)
left = mid + 1; // Search right half
else
right = mid - 1; // Search left half
}
return -1; // Key not found
}
What is the difference between array and linked lists?
arrays require contiguous memory while linked lists do not because their nodes have pointers point to the next one
describe how the stack data structure works
last in, first out
describe how a queue data structure works
first in, first out
What is the number of primitive operations?
for(int i = 0; i < n; i++) {
k++
}
5n+2
What is the difference between delete and delete []
delete only deletes a single dynamically allocated object, delete [] deletes a dynamically created array
write the size method to compute the number of elements in a linked list
If _Next != NULL {
return (*_next).size() + 1
}
else {
return 1;
}
what are the two ways we learned to implement stacks?
arrays and linked list
What are the the queue exceptions?
underflow, overflow, full, empty
what is the number of primitive operations?
for(int i =0; i <n; i++) {
for(int j = 0; j < n; j++) {
k++;
}
}
5n2+5n+2
Write the c++ definition for stack data structure
Private:
DT* info
stack* down
Public:
peek
push(DT)
pop
size
stack
~stack
operator =
write the method to overload [] in a linked list, such that LinkedList[i] returns _info at location i
T& operator[](int index) {
Node<T>* current = head;
int count = 0;
while (current != nullptr) {
if (count == index)
return current->info;
count++;
current = current->next;
}
throw std::out_of_range("Index out of bounds");
}
}
Convert the following expression:
Infix to Postfix: A * B * C / E - F + G - H / K
AB * C * E / F - G + H - K /
what type of sorting uses queues?
radix sort
what is the number of primitive operations?
int sum = 0
for(int i = 0; i <n; i++) {
if(i % 2 == 0) {
sum += i
}
}
6n + 3
Write the code for merge sort
void mergeSortedArrays(int a[], int sizeA, int b[], int sizeB, int result[]) {
int i = 0, j = 0, k = 0;
// Merge until one array is exhausted
while (i < sizeA && j < sizeB) {
if (a[i] < b[j]) {
result[k++] = a[i++];
} else {
result[k++] = b[j++];
}
}
// Copy remaining elements of a[]
while (i < sizeA) {
result[k++] = a[i++];
}
// Copy remaining elements of b[]
while (j < sizeB) {
result[k++] = b[j++];
}
}
write the c++ definition of a linked list
private:
DT info
node<DT>* next
node<DT>* head
public:
LinkedList(); // Constructor
~LinkedList(); // Destructor
void append(T value); // Add to end
void prepend(T value); // Add to front
bool remove(T value); // Remove by value
bool isEmpty() const; // Check if empty
int size() const; // Return number of elements
void clear(); // Remove all elements
T& operator[](int index); // Overload [] operator
const T& operator[](int index) const; // Const version
Convert the following expression:
A B C * / E / F - K *
(A / (B * C) / E - F) * K
what is the time complexity of radix sort? describe each variable
O(D x max(N, 10)
D = number of digits in largest number
N = number of elements to be sorted
10 = size of digit base (optional)
what is the number of primitive operations?
int sum = 0
int i = 0
while(i < n) {
i++
if(i % 2 == 0) {
sum += i
}
}
6n + 3
Name the 6 ways a matrix can be stored
Row Order, Column Order, C++, Array of Arrays, Sparse Matrix Representation, Compressed Sparse Matrix
Which of the following statements is true regarding the comparison between the array and linked list implementations of a queue?
The array queue uses connected memory and size, while linked list queue uses pointers. or The array implementation must keep track of the size to as to not go out of bounds. The LinkedList implementation can have the last node simply point back to the first. Most methods in the LinkedList will have to be recursive.
write the c++ definition of a stack data strucure
protected:
DT* info
int size
Public:
push(DT)
pop
empty
stack
~stack
peek
operator =
given the following set of numbers, perform radix sort with an array of queues, show all steps
429, 98, 99, 428, 218, 91, 104, 92, 215, 112
first pass: 91, 101, 91, 92, 112, 104, 215, 98, 428, 218, 429, 99
second pass: 101, 104, 112, 215, 218, 428, 429, 91, 91, 92, 98, 99
final pass: 91, 91, 92, 98, 99, 101, 104, 112, 215, 218, 428, 429