1. What is a precondition?
Something that needs to be true before the use case is triggered is called a
precondition. For instance, "The user has accessed the website and wants to
buy a book" may be a prerequisite for the use case "Buy Book on WebSite".
2. What is a postcondition?
Something that needs to be true once the use case is complete is called a
post condition. For instance, the user's book purchase was successful.
3. Suppose that st is represented by a partially filled array. Draw the state of
the private instance variables of st after the above code is executed:
3. a) What is the time-complexity of the above code?
The for loop iterates from 1 to n, inclusive. The range of the loop is determined by
range(1, n + 1), which means the loop will execute n times.
Inside the loop, there is only a simple addition operation (total += i), which takes
constant time, O(1). time complexity of the function is O(n).
4. How time-complexity of the above code can be minimized? Justify your answer by
writing another program for the same problem. (Hint: Think of using some sort of
formula to sum up all the numbers.)
To minimize the time complexity of the code, we can use a
mathematical formula instead of looping through each [Link] of
numbers from 1 to n directly in constant time, O(1).
4. pseudocode
function reverseLinkedList(head):
previous = null
current = head
while current is not null:
nextNode = [Link]
[Link] = previous
previous = current
current = nextNode
head = previous
return head
5. Previous = null
current = A
Store nextNode = B ([Link]).
Reverse the link: [Link] = previous (null).
Move previous to current (A).
Move current to nextNode (B).
Store nextNode = C.
Reverse the link: [Link] = previous (A).
Move previous to current (B).
Move current to nextNode (C).
6. To visualize how a stack is used for nested function calls, we can show the
sequence of stack frames being pushed and popped as follows:
FUNCTION main()
PRINT "Inside main: Calling functionA"
CALL functionA()
PRINT "Back in main after functionA completed"
END FUNCTION
FUNCTION functionA()
PRINT "Inside functionA: Calling functionB"
CALL functionB()
PRINT "Back in functionA after functionB completed"
END FUNCTION
FUNCTION functionB()
PRINT "Inside functionB: Calling functionC"
CALL functionC()
PRINT "Back in functionB after functionC completed"
END FUNCTION
FUNCTION functionC()
PRINT "Inside functionC: Performing operations in functionC"
// functionC completes and returns control to functionB
END FUNCTION
#### Steps of Merge Sort:
1. *Divide the array into halves recursively until each subarray contains one
element:*
[56, 40, 30, 78, 23, 7, 9, 10, 12, 5]
→ [56, 40, 30, 78, 23] and [7, 9, 10, 12, 5]
→ [56, 40] and [30, 78, 23], [7, 9] and [10, 12, 5]
→ [56] and [40], [30] and [78, 23], [7] and [9], [10] and [12, 5]
→ [56], [40], [30], [78], [23], [7], [9], [10], [12], [5]
2. *Merge subarrays in sorted order:*
- Merge [56] and [40]: [40, 56]
- Merge [78] and [23]: [23, 78]
- Merge [12] and [5]: [5, 12]
3. *Continue merging:*
- Merge [40, 56] and [30]: [30, 40, 56]
- Merge [23, 78] and [30, 40, 56]: [23, 30, 40, 56, 78]
- Merge [7] and [9]: [7, 9]
- Merge [7, 9] and [5, 12]: [5, 7, 9, 12]
- Merge [5, 7, 9, 12] and [10]: [5, 7, 9, 10, 12]
4. *Final merge:*
- Merge [23, 30, 40, 56, 78] and [5, 7, 9, 10, 12]: [5, 7, 9, 10, 12, 23, 30,
40, 56, 78]
*Final sorted array:*
*[5, 7, 9, 10, 12, 23, 30, 40, 56, 78]*
#### (a) *Level-order Traversal (Breadth-First Search)*
Visit nodes level by level from left to right.
For Figure 6:
*Level-order traversal:* 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
---
#### (b) *In-order Traversal (Left-Root-Right)*
Visit the left subtree, root, and then the right subtree.
For Figure 6:
*In-order traversal:* 8, 4, 2, 5, 9, 1, 6, 10, 3, 7