Data Structures Exam 1 (Complexity Analysis; Stacks, Queues, LLs; Recursion)

Which order is correct for the following runtime complexity functions from smallest to largest?
- 10000 < logn < n^2 < nlogn < 2^n
- 10000 < logn < nlogn < 2^n < n^2
- logn < nlogn < n^2 < 10000 < 2^n
- 10000 < logn < nlogn < n^2 < 2^n

10000 < logn < nlogn < n^2 < 2^n

What is the run-time complexity of the following program segment?
for(int i = 1; i

O(n)

What is the run-time complexity of the following program segment?
for(int i = 1; i

O(logn)

Express the following runtime complexity function using big O notation:
T(n) = (1/2)n^3 + 1000n^2

O(n^3)

Express the following runtime complexity function using big O notation:
T(n) = 4n + logn + 42

O(n)

What is the run-time complexity of the following program segment?
for(int i = 1; i

O(n^2)

What is the run-time complexity of the following program segment?
for(int i = 1; i

O(nlogn)

What's the worst-case runtime complexity for the following function?

in foo(int n)
{
int product = 1;
for(int i = 2; i < n; i++)
product = product * i;
return product;
}

O(n)

What's the best-case runtime complexity for the following function?

int foo(int n)
{
int product = 1;
for(int i = 2; i < n; i++)
product = product * i;
return product;
}

Note: We have to assume n is arbitrarily large. We cannot just assume n = 0 or n = 1

O(n)

Which of the following statements are true? You can select more than 1 choice.

- n^2 = O(n)
- m^3 = O(2^m)
- 3 = O(logk)
- 4n + 2 = O(1)
- 12000 = O(1)
- 100m + mlogm = O(mlogm)
- n^2.8 = O(n^2)

m^3 = O(2^m), 3 = O(logk), 12000 = O(1), 100m + mlogm = O(mlogm)

Given a node as prevNode, insert a new node after the given node in a Doubly Linked List.

void insertAfter(Node* prevNode, int newData)
{
if(prevNode == NULL)
cout << "The given previous node cannot be NULL" <<
endl;
return;

Node* newNode = new Node(); //creating a new object
newNode->data = newData; //intializing new object as the
user input

newNode->next = prevNode->next; //the next pointer
is updated using the prevNode

prevNode->next = newNode; //the prevNode should
now refer to the newNode
newNode->prev = prevNode; //updating the prev node
of the newNode

if(newNode->next != NULL)
_____________________________________
}

newNode->next->prev = newNode;

Fill in the missing piece of code.

bool Stack::push(char item)
{
if(__________)
{
cout << "Stack overflow";
return false;
}
else
{
top++;
exp[top] = item;
return true;
}
}

top >= MAX-1

Fill in the missing piece of code.

bool Stack::push(char item)
{
if(top >= MAX-1)
{
cout << "Stack overflow";
return false;
}
else
{
top++;
_______________;
return true;
}
}

exp[top] = item

Fill in the missing piece of code.

bool __________________
{
if(top >= MAX-1)
{
cout << "Stack overflow";
return false;
}
else
{
top++;
exp[top] = item;
return true;
}
}

Stack::push(char item)

Fill in the piece of missing code.

char ______________
{
if(top == -1)
{
cout << "Stack underflow";
return 0;
}
else
{
char x = exp[top];
top--;
return x;
}
}

Stack::pop()

Fill in the piece of missing code.

char Stack::pop()
{
if(________)
{
cout << "Stack underflow";
return 0;
}
else
{
char x = exp[top];
top--;
return x;
}
}

top == -1

Fill in the piece of missing code.

char Stack::pop()
{
if(top == -1)
{
cout << "Stack underflow";
return 0;
}
else
{
__________;
top--;
return x;
}
}

char x = exp[top]

Fill in the piece of missing code.

int isMatchingPair(char character1, char character2)
{
if(character1 == '(' && character2 == ')')
return 1;
else if(_________________________)
return 1;
else if(character1 == '{' && character2 == '}')
return 1;
else
return 0;
}

character1 == '[' && character2 == ']'

Fill in the piece of missing code.

int isMatchingPair(__________________)
{
if(character1 == '(' && character2 == ')')
return 1;
else if(character1 == '[' && character2 == ']')
return 1;
else if(character1 == '{' && character2 == '}')
return 1;
else
return 0;
}

char character1, char character2

Fill in the piece of missing code.

int areParenthesisBalanced(char exp[ ])
{
___________________;
int i = 0;

while(exp[i])
{
if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{')
s->push(exp[i]);
if(exp[i] == ')' || exp[i] == ']' || exp[i] == '}')
{
if(s->top == -1)
return 0;
else if(!isMatchingPair(s->pop(), exp[i]))
return 0;
}
i++;
}

if(s->top == -1)
return 1;
else
return 0;
}

Stack* s = new Stack()

Fill in the piece of missing code.

int areParenthesisBalanced(char exp[ ])
{
Stack* s = new Stack();
int i = 0;

while(____________)
{
if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{')
s->push(exp[i]);
if(exp[i] == ')' || exp[i] == ']' || exp[i] == '}')
{
if(s->top == -1)
return 0;
else if(!isMatchingPair(s->pop(), exp[i]))
return 0;
}
i++;
}

if(s->top == -1)
return 1;
else
return 0;
}

exp[i]

Fill in the piece of missing code.

int areParenthesisBalanced(char exp[ ])
{
Stack* s = new Stack();
int i = 0;

while(exp[i])
{
if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{')
s->push(exp[i]);
if(exp[i] == ')' || exp[i] == ']' || _____________)
{
if(s->top == -1)
return 0;
else if(!isMatchingPair(s->pop(), exp[i]))
return 0;
}
i++;
}

if(s->top == -1)
return 1;
else
return 0;
}

exp[i] == '}'

Fill in the piece of missing code.

int areParenthesisBalanced(___________)
{
Stack* s = new Stack();
int i = 0;

while(exp[i])
{
if(exp[i] == '(' || exp[i] == '['|| exp[i] == '{')
s->push(exp[i]);
if(exp[i] == ')' || exp[i] == ']'|| exp[i] == '}')
{
if(s->top == -1)
return 0;
else if(!isMatchingPair(s->pop(), exp[i]))
return 0;
}
i++;
}

if(s->top == -1)
return 1;
else
return 0;
}

char exp[ ]

Fill in the piece of missing code.

int areParenthesisBalanced(char exp[ ])
{
Stack* s = new Stack();
int i = 0;

while(exp[i])
{
if(exp[i] == '(' || exp[i] == '['|| exp[i] == '{')
s->push(exp[i]);
if(exp[i] == ')' || exp[i] == ']'|| exp[i] == '}')
{
if(s->top == -1)
return 0;
else if(!isMatchingPair(__________________))
return 0;
}
i++;
}

if(s->top == -1)
return 1;
else
return 0;
}

s->pop(), exp[i]

Fill in the piece of missing code.

int areParenthesisBalanced(char exp[ ])
{
Stack* s = new Stack();
int i = 0;

while(exp[i])
{
if(exp[i] == '(' || exp[i] == '['|| exp[i] == '{')
s->push(exp[i]);
if(exp[i] == ')' || exp[i] == ']'|| exp[i] == '}')
{
if(s->top == -1)
return 0;
else if(!isMatchingPair(s->pop(), exp[i]))
return 0;
}
i++;
}

if(___________)
return 1;
else
return 0;
}

s->top == -1

This is a recursive function that calculates the sum 1^1 + 2^2 + 3^3 + ... + n^n, given an integer value of n in between 1 and 9.

What is missing in this code?

int crazySum(int n)
{
if(n == 1)
return 1;
else
return ________________;
}

crazySum(n-1)+Power(n, n)

Select all correct sentences

- Arrays elements are contiguous in memory.
- Linked list elements should be contiguous in memory.
- Arrays have O(1) access to the nth element.
- Linked lists have O(1) access to the nth element.
- Insertion and deletion at arbitrary positions in the linked list doesn't
require us to shift elements all over the place.
- In a single linked list, each element has 2 pointers. One pointing to the
previous element and one pointing to the next element.
- Stacks and Queues both follow First in First out (FIFO) order.

Arrays elements are contiguous in memory;
Arrays have O(1) access to the nth element;
Insertion and deletion at arbitrary positions in the linked list doesn't require us to shift elements all over the place.

A stack has the following elements:
2, 3, 1

2, 3

A queue has the following elements:
1, 2, 3

5, 4, 1

What would be the time complexity of the push and pop operation of a stack implemented using a singly linked list of n elements?

Push: O(1)
Pop: O(1)

What would be the time complexity of the enqueue and dequeue operations of a queue of n elements implemented using a singly linked list of n elements?
(Assume it has front and rear pointers)

Enqueue: O(1)
Dequeue: O(1)

Data

Any information that's stored in or used by a computer

How do you store, organize, and process data efficiently?

Data structures

Data structures can be described as

Logical models: Abstract Data Types
Implementation of Abstract Data Types

Abstract Data Types

A logical model for data types, defines data and operations but no implementation

For designing a proper data structure for soling a problem, we need to study what?

Logical View, Operations, Cost of Operations, Implementation

What's the definition of an algorithm?

Step-by-step procedure to solve a problem

What are the components of a problem?

Input, Output, and the algorithm (or steps) in between them

Time complexity

The amount of time an algorithm takes in terms of the amount of input

Space complexity

The amount of memory (space) an algorithm takes in terms of the amount of input

Time Complexity Function

Any function that maps the positive integers to the nonnegative reals
Shows the number of basic operations of an algorithm based on input size

Big-O notation can be described as

an upper bound for a complexity function

What is the Big-O notation of f(n) = n^2 + 5n + 1000?

O(n^2)

What is the Big-O notation of f(n) = n^3 + 40n^2 + nlogn + 2?

O(n^3)

What is the Big-O notation of f(n) = n^1.999 + 100n?

O(n^1.999)

What is the Big-O notation of f(n) = nlogn + n?

O(nlogn)

What is the Big-O notation of f(n) = 12n + logn?

O(n)

Big-O Notation: Given a function g(n), we denote O(g(n)) to be the set of functions

{ f(n) | there exists positive constants c and n0 such that 0 ≤ f(n) ≤ c g(n) for all n ≥ n0}

Big-Ω Notation: Given a function g(n), we denote Ω(g(n)) to be the set of functions

{ f(n) | there exists positive constants c and n0 such that 0 ≤ c g(n) ≤ f(n) for all n ≥ n0}

Big-Θ Notation: Given a function g(n), we denote Θ(g(n)) to be the set of functions

{ f(n) | there exists positive constants c1, c2 and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥n0}

What is the asymptotic complexity of this algorithm?

sum = 0;
for (i = 0; i < n; i++)
sum = sum + a[i];

O(n)

Worst Case Analysis

the input parameters are considered such that our algorithm takes the most number of operations to run

Best Case Analysis

the case is found such that our algorithm takes the least number of operations to run

Average Case Analysis

the average number of steps are considered for running the algorithm

What is the running time complexity of this algorithm?

for (int x = n; x >= 0; x--) {
cout << x << endl;
}

O(n)

What is the running time complexity of this algorithm?

for (int i = 0; i < 5; i++) {
for (int j = 0; j < 10; j++) {
cout << j << endl;
}
}

O(1)

What is the running time complexity of this algorithm?

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << j << endl;
}
}

O(n^2)

What is the running time complexity of this algorithm?

for (int i = 0; i < n; i++) {
for (int j = 0; j < n*n; j++) {
cout << "tricky!" << endl;
}
}

O(n^3)

What is the running time complexity of this algorithm?

while (n > 1) {
n /= 2;
}

O(logn)

What is the running time complexity of this algorithm?

for (int i = 1; i

O(nlogn)

What is the running time complexity of this algorithm?

for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
sum += 5;
}
}

O(n^2)

What is the running time complexity of this algorithm?

for (int i = 0; i < a; i++) {
for (int j = 0; j < i; j++)
sum += 5
for (int k = 0; k < b; k++)
sum++;
}
note: a and b are not constants

O(a^2 + ab)

What is the running time complexity of this algorithm?

for (int i = 0; i < a; i++) {
for (int j = 0; j < i; j++)
{
sum += 5
for (int k = 0; k < b; k++)
sum++;
}
}

O(a^2b)

What do the if statements represent in this recursive code?

int fib(int n) {
if (n == 1)
return 0;
if (n == 2)
return 1;

return fib(n - 1) + fib(n - 2);
}

base cases

Fill in the piece of missing code.

int binarySearch(int arr[ ], int low, int high, int x)
{
if (high >= low) {
int mid = low + (high - I) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return ___________________;

return binarySearch(arr, mid + 1, high, x);
}

return -1;
}

binarySearch(arr, low, mid - 1, x)

Fill in the piece of missing code.

int binarySearch(______________)
{
if (high >= low) {
int mid = low + (high - l) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);

return binarySearch(arr, mid + 1, high, x);
}

return -1;
}

int arr[ ], int low, int high, int x

Fill in the piece of missing code.

int binarySearch(int arr[ ], int low, int high, int x)
{
if (high >= low) {
int _______________;

if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);

return binarySearch(arr, mid + 1, high, x);
}

return -1;
}

mid = low + (high - l) / 2

What is the recurrence relation for this algorithm?

int binarySearch(int arr[ ], int low, int high, int x)
{
if (high >= low) {
int mid = low + (high - I) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);

return binarySearch(arr, mid + 1, high, x);
}

return -1;
}

T(n) = 2T(n/2) + n

What is the computational complexity for this algorithm?

int count = 0;
for (int i = 1; i

O(n)

What is the running time complexity of the following function which finds the kth smallest integer in an unordered array.

int selectkth(int a[ ], int k, int n) {
int i, j, mini, tmp;
for (i = 0; i < k; i++) {
mini = i;
for (j = i+1; j < n; j++)
if (a[j] < a[mini])
mini = j;
tmp = a[i];
a[i] = a[mini];
a[mini] = tmp;
}
return a[k-1];
}

O(n^2) or O(kn)

If we assume that the input array is always sorted, how can we rewrite this function to return the kth smallest element of the sorted array? What would be the running time complexity in that case?

int selectkth(int a[ ], int k, int n) {
int i, j, mini, tmp;
for (i = 0; i < k; i++) {
mini = i;
for (j = i+1; j < n; j++)
if (a[j] < a[mini])
mini = j;
tmp = a[i];
a[i] = a[mini];
a[mini] = tmp;
}
return a[k-1];
}

int selectkth(int a[ ], int k) {
return a[k];
} ==> Running time: complexity: O(1)

Linked List

a data structure consistent of nodes that are linked together with pointers; length is dynamic

Arrays

fixed in size; contiguous in memory

What would be the time complexity of the get() operation of a singly linked list implementation?

O(n)

What would be the time complexity of the insertLast() operation of a singly linked list implementation?

O(n)

What would be the time complexity of the remove() operation of a singly linked list implementation?

O(n)

What would be the time complexity of the insertAt() operation of a singly linked list implementation?

O(n)

What would be the time complexity of the insertBeg() operation of a singly linked list implementation?

O(1)

What would be the time complexity of the replace() operation of a singly linked list implementation?

O(n)

Fill in the piece of missing code.

void insertBeg(Node** headRef, int newData)
{
_________________________;

newNode->data = newData;

newNode->next = (*headRef);

(*headRef) = newNode;
}

Node* newNode = new Node()

Fill in the piece of missing code.

void insertBeg(Node** headRef, int newData)
{
Node* newNode = new Node();

___________________________;

newNode->next = (*headRef);

(*headRef) = newNode;
}

newNode->data = newData

Fill in the piece of missing code.

void insertBeg(Node** headRef, int newData)
{
Node* newNode = new Node();

newNode->data = newData;

___________________________;

(*headRef) = newNode;
}

newNode->next = (*headRef)

Fill in the piece of missing code.

void insertBeg(Node** headRef, int newData)
{
Node* newNode = new Node();

newNode->data = newData;

newNode->next = (*headRef);

________________________;
}

(*headRef) = newNode

Fill in the piece of missing code.

void insertBeg(__________________)
{
Node* newNode = new Node();

newNode->data = newData;

newNode->next = (*headRef);

(*headRef) = newNode;
}

Node** headRef, int newData

Fill in the piece of missing code.

void insertAfter(Node* prevNode, int newData)
{
if (prevNode == NULL)
{
cout<

prevNode->next = newNode

Fill in the piece of missing code.

void insertAfter(Node* prevNode, int newData)
{
if (prevNode == NULL)
{
cout<

newNode->next = prevNode->next

Fill in the piece of missing code.

void insertAfter(Node* prevNode, int newData)
{
if (prevNode == NULL)
{
cout<

newNode->data = newData

Fill in the piece of missing code.

void insertLast(Node** headRef, int newData)
{
Node* newNode = new Node();

Node *last = *headRef;

newNode->data = newData;

_____________________;

if (*headRef == NULL)
{
*headRef = newNode;
return;
}

while (last->next != NULL)
{
last = last->next;
}

last->next = newNode;
return;
}

newNode->next = NULL

Fill in the piece of missing code.

void insertLast(Node** headRef, int newData)
{
Node* newNode = new Node();

Node *last = *headRef;

newNode->data = newData;

newNode->next = NULL;

if (*headRef == NULL)
{
__________________;
return;
}

while (last->next != NULL)
{
last = last->next;
}

last->next = newNode;
return;
}

*headRef = newNode

Fill in the piece of missing code.

void insertLast(Node** headRef, int newData)
{
Node* newNode = new Node();

Node *last = *headRef;

newNode->data = newData;

newNode->next = NULL;

if (*headRef == NULL)
{
*headRef = newNode;
return;
}

while (___________________)
{
last = last->next;
}

last->next = newNode;
return;
}

last->next != NULL

Fill in the piece of missing code.

void insertLast(Node** headRef, int newData)
{
Node* newNode = new Node();

Node *last = *headRef;

newNode->data = newData;

newNode->next = NULL;

if (*headRef == NULL)
{
*headRef = newNode;
return;
}

while (last->next != NULL)
{
_________________;
}

last->next = newNode;
return;
}

last = last->next

Fill in the piece of missing code.

void insertLast(Node** headRef, int newData)
{
Node* newNode = new Node();

Node *last = *headRef;

newNode->data = newData;

newNode->next = NULL;

if (*headRef == NULL)
{
*headRef = newNode;
return;
}

while (last->next != NULL)
{
last = last->next;
}

___________________;
return;
}

last->next = newNode

Fill in the piece of missing code.

void printList(______________)
{
while (node != NULL)
{
cout<

Node *node

Fill in the piece of missing code.

void printList(Node *node)
{
while (_____________)
{
cout<

node != NULL

Fill in the piece of missing code.

void printList(Node *node)
{
while (node != NULL)
{
cout<

node->data

Fill in the piece of missing code.

void printList(Node *node)
{
while (node != NULL)
{
cout<

node = node->next

Advantages of Doubly Linked List over Singly Linked List

- can be traversed in both forward and backward direction
- the delete operation is more efficient if ptr to the node to be
deleted is given
- a new node can be quickly inserted before a given node

Disadvantages of Doubly Linked List over Singly Linked List

- all operations require an extra pointer previous to be
maintained

In a Circular Linked List how do you know you are in the end of the list?

the last element should point to the head instead of NULL

Queue ADT

store the same type of elements; follow the First-In First-Out (FIFO) order