DSA 1 Midtern 2

What is the purpose of templates in C++?

 

Code re-use for different data types

What is not true about templates?

Using function templates is the only method to allow a function to work with different data types

Match the ADT use case with the best implementation.

Both Array and linked List

Match the ADT use case with the best implementation.

Linked List

Match the ADT use case with the best implementation

Linked List

Match the ADT use case with the best implementation.

Linked List

A linked-list is a typical ADT with interface defined and details hidden.

False

In order to convert the following Stack data structure to a Queue, which additional private instance variable can be added to make the implementation more efficient to push or pop from different ends?

class MyStack {

    private:

        Node* head;

...

}

Node* tail

 

Which of the following sorting algorithm has a different upper bound (big O) on average case and worst case?

Quicksort

Which of the following is not a comparison based sorting algorithm?

Radix

Is O(nlog(n)) sorting algorithms always faster than O(n²) algorithms?

False: Faster means absolute time. It is not always true.

What is the best sorting algorithm for linked-list among the following algorithms when working with large problem size?

 

Merge sort

Which of the sorting algorithm has the worst space complexity?

 

Merge sort

How many recursive calls in the recursive top-down merge sort algorithm are required for a list of 2048 elements? (Find the closest value.)

 11

Given a list (1, 101, 2244, 156), how many rounds of bucket collections will a Radix sort require?

4

Given the list 1, 2, 3, 4, 5; an efficient hashing algorithm would be f(x) = (x * 2) % 5.

By "efficient" above, I mean that no collisions occur on the data given.

True

Given the following quadratic hash function and probing sequence formula and the starting state of the hash buckets below, what bucket does Insert(12) go into?

h1(x) = key % 10
Quadratic probing sequence = (h1(x) + 2 * i * i) % 10, i = 0, 1, 2, ...

4

If a set S is implemented as a hash table with key and no value value, searching for an element e in the set S is the same as lookup a value in a hash table. This action can be done in O(_____) expected time.

1

Given the list 1,2,3,4,5; an efficient hashing algorithm would be

 f(x) = (x * 2) % 7

Efficient means that no collisions occur on the data given.

True

Quick sort is a fast, stable, and general-purpose sort.

False(Quick Sort is not Stable)

You must specify the base type when calling a function template.

True

False

True

No, not for function templates. Base type will be inferred by the compiler.

Some ADT may have all methods required by another ADT. Which of the following ADT can be used as a Stack without any problem?

Deque

Given the following quadratic hash function and probing sequence formula and the starting state of the hash buckets below, what bucket does Insert(12) go into?

const int SIZE = 10;
h1(x) = key % SIZE
quadratic probing sequence = (h1(x) + i + i * i) % SIZE, i = 0, 1, 2, ...

4

5

6

8

6, 2, 7, 8, 9

 

What is the correct order of the algorithms with known complexity? From the fastest to the lowest.

Complexity:

Merge sort
Hash map lookup
Insertion sort
Linear search

Hash map lookup, Linear search, Merge sort, Selection sort

Fill in the blanks below. Remember that C++ passes by value by default.

T&

T&
T

value1

Write an array comparison function template that compares two arrays for equality. This function should be named as compare. The function should work for various base types of data. It will take two arrays and two int-typed sizes as parameters and return a bool value as the result of comparison. Assuming that the base type can be compared using == and !=. Two arrays are identical only when they have identical sizes and identical items in the same order.

Note: Functions that are not templates cannot receive full credit.

Image

C++

#include <iostream>
using namespace std;

// solution
template <class T>
bool compare(T *arr1, int size1, T *arr2, int size2) {
  if (size1 != size2)
    return false;
  for (int i = 0; i < size1; i++)
    if (arr1[i] != arr2[i])
      return false;
  return true;
}

// for testing
int main() {
  int a1[] = {1,2,3,4};
  int a2[] = {1,2,3,4};
  int a3[] = {1,2,3,3};

  if (compare(a1, 4, a2, 4))
    cout << "Identical\n";
  else
    cout << "Different\n";
  if (compare(a1, 4, a3, 4))
    cout << "Identical\n";
  else
    cout << "Different\n";

  return 0;
}

Write the C++ code to implement the Queue (doubly-linked-list based) and its corresponding Node classes. Do not add any functionality that is not required below. Much fewer points will be given for implementations that do not use the required doubly-linked list data structures.

Node class:

• You can either make all instance variables public or make them private and add getters/setters.

• Add constructor(s) as needed.

Queue class:

• A enqueue() function to take an int value as input and add a node before the first element in your list.

• A dequeue() function to return the int value of the last node in the list and remove that node from the list. It should return -1 if the queue is empty.

• A peek() function to return the int value of the last node. It should return -1 if the queue is empty.

• A isEmpty() function to check empty

• Add constructors as needed.

• Do not forget the destructor.

General requirements:

• Write frameworks first to get partial credits and fill in details.

• You can make your function implementation either inline or not inline.

• Only implement the class and methods used here, as well as anything required by these methods.

• Assume that you implement both classes in one .cpp file.

• Add include and using directives/statements as needed.

#include <iostream>
using namespace std;


class Node {
 public:
  int value;
  Node *prev;
  Node *next;
  Node(int value): value(value), prev(nullptr), next(nullptr) {}
};

class Queue {
  Node *head;
  Node *tail;
 public:
  Queue();
  ~Queue();
  bool isEmpty();
  void enqueue(int value);
  int dequeue();
  int peek();
};

Queue::Queue(): head(nullptr), tail(nullptr) {}

Queue::~Queue() {
  while (!isEmpty())
    dequeue();
}

bool Queue::isEmpty() {return head == nullptr;}

// enqueue at head
void Queue::enqueue(int value) {
  Node *node = new Node(value);
  if (isEmpty()) {
    head = node;
    tail = node;
    return;
  }
  head->prev = node;
  node->next = head;
  head = node;
}

// dequeue at tail
int Queue::dequeue() {
  if (isEmpty())
    return -1;
  Node *secondLast = tail->prev;
  int value = tail->value;
  delete tail;
  tail = secondLast;
  if (tail == nullptr)  // if second last does not exist, the queue is empty
    head = nullptr;
  else
    tail->next = nullptr;
  return value;
}

// peek at tail
int Queue::peek() {
  if (isEmpty())
    return -1;
  return tail->value;
}

// this is not part of the solution, just to test run
int main() {
  Queue myQ;
  cout << "pushing 1" << endl;
  myQ.enqueue(100);
  cout << "pushing 2" << endl;
  myQ.enqueue(200);
  cout << "peek 1 " << myQ.peek() << endl;
  cout << "pop 1 " << myQ.dequeue() << endl;
  cout << "pop 2 " << myQ.dequeue() << endl;
  cout << "pop 3 " << myQ.dequeue() << endl;
}

Merge Sort time and space complexity

• Best case time: $O(n \times \log(n))$\n- Average case time: $O(n \times \log(n))$\n- Worst case time: $O(n \times \log(n))$\n- Worst-case auxiliary space: $O(n)$

Quick Sort time and space complexity

• Best case time: $O(n \times \log(n))$\n- Average case time: $O(n \times \log(n))$\n- Worst case time: $O(n^2)$\n- Worst-case auxiliary space: $O(\log(n))$ average stack space ($O(n)$ worst-case stack space)

Insertion Sort time and space complexity

• Best case time: $O(n)$ (when already sorted)\n- Average case time: $O(n^2)$\n- Worst case time: $O(n^2)$\n- Worst-case auxiliary space: $O(1)$

Selection Sort time and space complexity

• Best case time: $O(n^2)$\n- Average case time: $O(n^2)$\n- Worst case time: $O(n^2)$\n- Worst-case auxiliary space: $O(1)$

Radix Sort time and space complexity

• Best case time: $O(d \times (n + k))$\n- Average case time: $O(d \times (n + k))$\n- Worst case time: $O(d \times (n + k))$\n- Worst-case auxiliary space: $O(n + k)$\n(where $n$ is the number of keys, $d$ is key digit length, and $k$ is the bucket radix)

Condition under which Quick Sort degrades to its worst-case runtime of $O(n^2)$

Consistently highly unbalanced partitioning, which occurs when the pivot chosen is repeatedly the extreme element (minimum or maximum), such as with an already sorted array under a naive first- or last-element pivot selection.

Reason Insertion Sort achieves $O(n)$ best-case time complexity while Selection Sort requires $O(n^2)$

Insertion Sort only performs a single comparison per element when the array is already sorted and terminates inner loops immediately, whereas Selection Sort must scan every remaining unsorted position to find the minimum element regardless of initial ordering.