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