CC4 - Finals

Question 1

• Aka Last-In-First-Out (LIFO)
• Top – entry/exit point

Answer 1

Stacks

Question 2

– Insert or push some item “x” onto the stack.
* Before this operation, the stack if often checked if it has enough capacity to accommodate the new item
* If stack is full, an overflow would occur

Answer 2

Push (x)

Question 3

• – Removing the most recent item or element from the stack.
• Must ensure that the stack is not empty before this operation
• If stack contains no item, popping would cause an underflow error

Answer 3

Pop( )

Question 4

• – Returns the copy of the item or element at the top of the stack.
• The item itself is not removed from the stack
• This operation is also called peek

Answer 4

Top( )

Question 5

• – It will return true if the stack is empty, false otherwise.
• Normally applied before the pop operation to avoid stack undeflow

Answer 5

IsEmpty( )

Question 6

• • – It will return true if the stack is full, false otherwise.
• Normally applied before the push operation to avoid stack overflow
• Not used when dynamic memory allocation is used

Answer 6

IsFull()

Question 7

• generates an empty stack object and reserves necessary storage space

Answer 7

Create

Question 8

– removes all elements from the stack and releases memory allocated to stack

Answer 8

Destroy

Question 9

Array Implementation

Answer 9

• the top of the stack is at the beginning of the array, which is inefficient due to the need to shift elements
• the top is at the end, which is* more efficient as it only requires constant time* for push and pop operations.
• uses an array to store data, with a variable “top” tracking the current position of the top element, and the array size defining the maximum capacity, where the top is incremented on push and decremented on pop.

Question 10

Disadvantage of Array Implementation of Stacks

Answer 10

• Size of stack needs to be specified at compile time
• If an application requires less space than the array size, storage space will be wasted
• The program will crash if application requires more storage space at runtime

Question 11

• uses a pointer to track the top of the list, with elements added and removed only at that top, ensuring a Last-In, First-Out data structure.

Answer 11

Linked-List Implementation

Question 12

Push

Answer 12

1. Create a new node
2. Copy element to the new node
3. Link pointer of new node is set to point to pre-existing front node
4. Head pointer is re-set to point to the new node

Question 13

Pop

Answer 13

1. Topmost element is copied for removal
2. A new pointer is created to point to front mode
3. Head pointer is reset to point to the next node
4. Using the new pointer, front node is deleted

Question 14

: inserts an element on the front of the list

Answer 14

* insertFront(x)

Question 15

: returns and removes the element at the front of the list

Answer 15

* removeFront()

Question 16

: inserts an element on the back of the list

Answer 16

* insertBack(x)

Question 17

: returns and removes the element at the end of the list

Answer 17

* removeBack()

Question 18

: inserts an element on the front of the list.
1) Allocate a new node
2) Have new node point to old head
3) Update head to point to new node

Answer 18

insertFront(x)

Question 19

: returns and removes the element at the front of the list.
1) Update head to point to next node in the list.
2) Return element of previous head and delete the node.

Answer 19

removeFront()

Question 20

: inserts an element on the back of the list.
1) Allocate a new node
2) If tail is NULL, update head and tail to point to the new node; otherwise.
* Have the old tail point to the new node.
* Update tail to point to new node.

Answer 20

insertBack(x)

Question 21

: returns and removes the element at the end of the list.
1) No efficient way of doing.
2) Typically would not use a linked-list if this operation is commonly used

Answer 21

removeBack()

Question 22

• Most programming languages use stacks to manage subroutine calls by storing necessary information like return addresses, parameters, and local variables in an activation record on the stack, which is then popped off when the subroutine returns.

Answer 22

Recursion Implementation

Question 23

O(N) vs O(1)

Answer 23

• O(N) represents linear time complexity, where the time taken by an algorithm grows proportionally to the size of the input data (N),
• O(1) represents constant time complexity, meaning the time taken remains the same regardless of the input size.

Question 24

Advantages & Disadvantages of Stacks

Answer 24

Advantages of Stacks
* Helps manage the data in particular way (LIFO) which is not possible with Linked list and array.
* When function is called the local variables are stored in stack and destroyed once returned. Stack is used when variable is not used outside the function.
* It gives control over how memory is allocated and deallocated.
* Stack frees you from the burden of remembering to cleanup(read delete) the object
* Not easily corrupted (No one can easily inset data in middle)

Disadvantages of Stacks
* Stack memory is limited.
* Creating too many objects on the stack will increase the chances of stack overflow
* Random access not possible

Question 25

is a legal combination of operands and the operators.

Answer 25

algebraic expression

Question 26

is the quantity (unit of data) on which a mathematical operation is performed.
- may be a variable or a constant

Answer 26

Operand

Question 27

is a symbol which signifies a mathematical or logical operation between the operands. Example of familiar operators include +,-,*, /, ^

Answer 27

Operator

Question 28

the expressions in which operands surround theoperator, e.g. x+y, 6*3 etc this way of writing the Expressions is called ___________

Answer 28

infix notation

Question 29

Postfix notation are also Known as

Answer 29

Reverse Polish Notation (RPN)

Question 30

They are different from the infix and prefix notations in the sense that in the postfix notation, operator comes after the operands, e.g. xy+, xyz+* etc.
 - is another way of writing arithmetic expression.

Answer 30

Postfix notation

Question 31

Prefix notation also Known as _____________

Answer 31

Polish notation

Question 32

operator comes before the operands, e.g. +xy, *+xyz etc.

Answer 32

Prefix notation

Question 33

• When an operand lies between two operators that have the same priority, the operand associates with the operator on the left. (a + b – c) (a * b / c / d)

Answer 33

Tie Breaker

Question 34

• Sub expression within delimiters is treated as a single operand, independent from the remainder of the expression. [(a + b) * (c – d) / (e – f)]

Answer 34

Delimeters

Question 35

is normally implemented by placing necessary information about the subroutine (including the return address, parameters, and local variables) onto a stack.

Answer 35

subroutine call

Question 36

A subroutine call is normally implemented by placing necessary information about the subroutine (including the return address, parameters, and local variables) onto a stack.

This information is called an ________.

Answer 36

activation record

Question 37

is special type of LinkedList.
- FIFO (First-in, First-out) data structure. That is, the first element to be added awill be the first element to be removed, and so forth.
- Like a stack, a it does not support removal of element in the middle; it only supports deletion from the head of the queue and insertion at the end of the queue.

Answer 37

Queue

Question 38

Three main operations

Answer 38

Enqueue - a list-like structure that provides restricted access to its elements.
- may only be inserted at the back
Dequeue - removed from the front
Peek – returns the top value

Question 39

Comparison of Array-Based and Linked Queues

Answer 39

• All member functions for both the array-based and linked queue implementations require constant time.
• The space comparison issues are the same as for the equivalent stack implementations.
• Unlike the array-based stack implementation, there is no convenient way to store two queues in the same array, unless items are always transferred directly from one queue to the other.

Question 40

• Given a list of data find the location of a particular value or report that value is not present

Answer 40

Searching

Question 41

• If items are sorted then we can divide and conquer
• dividing your work in half with each step
• generally a good thing

Answer 41

Searching in a Sorted List

Question 42

• A fundamental application for computers
• Done to make finding data (searching) faster

Answer 42

Sorting

Question 43

– The data collection to be sorted is kept in the main memory.

Answer 43

Internal Sorting

Question 44

– The sorting of data stored on secondary devices. Data is sorted in the main memory and written back to the secondary device.

Answer 44

External Sorting

Question 45

• an iterative sorting algorithm that repeatedly steps through the list, comparing adjacent elements and swapping them if they are in the wrong
• 1 order, gradually moving the largest elements to the end of the list until the entire list is sorted.

Answer 45

Bubble Sort

Question 46

Dis/Advantages of Bubble sort

Answer 46

Advantage
* Easy to understand
* Easy to implement
* No demand for large amounts of memory
* Once sorted, data is available for processing

Disadvantage
1. Sorting takes a long time

Question 47

Best/Worst case of Bubble sort

Answer 47

Best-case O(n)
Worse-case O(n2) – reverse sorted

Question 48

• Slightly better performance
• Efficient than bubble sort
• O(n2) – both best- and worse-case complexity

Answer 48

Selection Sort

Question 49

Dis/Advantages of Selection sort

Answer 49

Advantage
* The main advantage of the selection sort is that it performs well on a small list.
* Because it is an in-place sorting algorithm, no additional temporary storage is required beyond what is needed to hold the original list.
* Its performance is easily influenced by the initial ordering of the items before the sorting process.

Disadvantage
1. The primary disadvantage of the selection sort is its poor efficiency when dealing with a huge list of items.
1. The selection sort requires n-squared number of steps for sorting n elements.
1. Quick Sort is much more efficient than selection sort

Question 50

Key Differences Between Bubble Sort and Selection Sort

Answer 50

1. In the bubble sort, each element and its adjacent element is compared and swapped if required. On the other hand, selection sort works by selecting the element and swapping that element with the last element. The selected element could be largest or smallest depending on the order i.e., ascending or descending.
2. The worst-case complexity is same in both the algorithms, i.e., O(n2), but best complexity is different. Bubble sort takes an order of n time whereas selection sort consumes an order of n2 time.
3. Bubble sort is a stable algorithm, in contrast, selection sort is unstable.
4. Selection sort algorithm is fast and efficient as compared to bubble sort which is very slow and inefficient.

Question 51

• Simple sorting algorithm
• Array is virtually split into a sorted and unsorted part

Answer 51

Insertion Sort

Question 52

Algorithm of Insertion Sort

Answer 52

To sort an array of size n in ascending order:
1. Iterate from arr[1] to arr[n] over the array.
2. Compare the current element (key) to its predecessor.
3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Question 53

Dis/Advantages of Insertion sort

Answer 53

Advantage
* The main advantage of the insertion sort is its simplicity.
* It also exhibits a good performance when dealing with a small list.
* The insertion sort is an in-place sorting algorithm, so the space requirement is minimal.

Disadvantage
1. The disadvantage of the insertion sort is that it does not perform as well as other, better sorting algorithms
1. With n-squared steps required for every n element to be sorted, the insertion sort does not deal well with a huge list.
1. The insertion sort is particularly useful only when sorting a list of few items

Question 54

Implementation of Insertion Sort

Answer 54

1. The first step is to create a method that takes in input the array to be sorted, sort arr as seen in line 3 in the code above.
2. The second step is to create an outer for loop which will iterate over each element of the array as shown in line 5.
3. The third step is to create a separate iterator, j which will check for the ascending order of elements in the list, as shown in line 7.
4. The fourth step is the inner while loop:
   a. As shown in line 9 the while loop must satisfy two conditions: the value of j must be greater than 0, and the value at index j-1, must be greater than the value at index j.
   b. If this condition holds true then, as shown from lines 11 to 14, the key is set to the value at index j.
   c. Then the values at j and j-1 are swapped.
   d. The value of j is reduced by 1 and the loop continues till one of the conditions breaks.
5. This continues for every iteration of the outer for loop till that also breaks.

Question 55

• Divide and conquer algorithm
• Merge() function – merging 2 halves

Answer 55

Merge Sort

Question 56

Dis/Advantages of Merge sort

Answer 56

Advantage
* It can be applied to files of any size.
* Reading of the input during the run-creation step is sequential ==> Not much seeking.
* If heap sort is used for the in-memory part of the merge, its operation can be overlapped with I/O

Disadvantage
1. Requires extra space »N
1. Merge Sort requires more space than other sort.
1. Merge sort is less efficient than another sort