Arrays, LL and recursion

Question 1

How does insertion and removal happen in Arrays?

Answer 1

To remove, you store the onject that you want to remove, start your for loop from the position of that object and start overwriting it’s position with elements towards its right, decrease the size

Question 2

Give the psuedo-code for the insertion sort

Answer 2

0. loop from 0 to -1 the number of elements in the array
1. while j >0 (to control the j– and to continue looping in case we missed some) && arr[j-1] >arr[j]
2. have a local variable j be initialized to i.
3. while j > 0 and arr[j-1] > arr[j] // while the one before is greater
4. store that element
5. set arr[j] = arr[j-1] // not the other way around because we do not want to overwrite the value of arr[j-1]
6. set arr[j-1] = stored
7. j–

Question 3

What is a Position ADT?

Answer 3

A unified way of viewing a single element stored in a data structure like a node of a LL or a cell of an array

Question 4

What two parts do nodes store in a SLL?

Answer 4

An element and a link to the next node

Question 5

T/F most operations in a SLL run in O(1) time?

Answer 5

True

Question 6

Why is it a hassle removing at the tail of a SLL?

Answer 6

> You have to iterate through all the nodes up until your next is the tail, set current.next = null, tail = current. Because we have to go through almost all the nodes, say n nodes till we reach the one before the tail. This makes its runtime complexity to be O(n)

Question 7

Give an algorithm for insertion at the tail as well as it’s runtime complexity

Answer 7

1. Create a new node, set its next to null\
2. Set the “tail’s” next to be the new node (IMPORTANT)
3. make the new node the tail
4. increment the size

Question 8

(T/F) The head of a SLL cannot store any elements. It is simply a reference to the beginning of the list and nothing else.

Answer 8

False, the head can store an element as well as the tail

Question 9

Which operation of a SLL has O(n) complexity?

And which one of a DLL has O(n) complexity?

Answer 9

SLL : removal at the tail

DLL: none

Question 10

What are experimental studies and what are 3 of their drawbacks?

Answer 10

Experimental studies are a method of measuring the efficiency of an algorithm by examining how much time it takes to execute that particular algorithm

1. You have to execute the whole algorithm to find out how efficient it is but this is time consuming
2. You have to test with all different types of input, but this is sometimes not possible
3. You have to run the algorithm on the same hardware and software that it was originally tested on to get similar results