Assignment 5 1

Course: Algorithms (MSIT 5214-01)

Instructor: Prof. Syed Mohsin

Date:12/14/2022

Week 5

Assignment 5

This study source was downloaded by 100000894591670 from [Link] on 12-15-2024 06:39:32 GMT -06:00

[Link]
 Assignment 5 2

Part 1

Illustrate the result of each operation in the sequence PUSH(S, 4), PUSH(S, 1), PUSH(S,3),

POP(S), PUSH(S, 8), and POP(S) on an initially empty stack S stored in array S[1… 6]. When

you begin, the stack is empty. You will need to draw a diagram of the stack showing the result

after each operation.

Let’s see the outcome in-depth as follows:

First, we know that the array is empty.

So, whenever a push is performed the item will be pushed into the stack.

Then, let’s perform PUSH(S,4). When we perform that item 4 will be pushed into the stack.

Therefore, the stack is

4, and top points towards 4.

Next let’s PUSH(s,1), and the stack will look like the below.

4Â Â Â 1

Then the top points towards 1

After that, we need to perform PUSH(S,3) and the stack will look like the below where the top
points towards 3.

4Â Â Â Â 1Â Â Â Â Â Â Â 3

Then when we perform POP(S), item 3 will be there even if the top points towards 1

4Â Â Â Â Â 1Â Â Â Â Â Â 3

Next is PUSH(S, 8), Where the stack looks like the below and, obviously the top points towards
8

4Â Â Â Â Â 1Â Â Â Â Â Â 8

Then, lastly POP(S), element 8 is popped, and the top points towards 1

This study source was downloaded by 100000894591670 from [Link] on 12-15-2024 06:39:32 GMT -06:00

[Link]
 Assignment 5 3

4Â Â Â Â Â Â 1Â Â Â Â Â Â 8

Diagram of the stack showing the result after each operation.

Empty array

1 2 3 4 5 6

Step 1 PUSH (S, 4)

1 2 3 4 5 6

Step 2 PUSH (S, 1)

4 1

1 2 3 4 5 6

Step 3 PUSH(S,3)

4 1 3

1 2 3 4 5 6

Step 4 POP(S),

4 1

1 2 3 4 5 6

Step 5 PUSH (S, 8),

4 1 8

This study source was downloaded by 100000894591670 from [Link] on 12-15-2024 06:39:32 GMT -06:00

[Link]
 Assignment 5 4

1 2 3 4 5 6

Step 5 POP(S)

4 1

Part-2:

Implement a stack using a singly linked list L in Python or Java.

 Do the operations PUSH and POP take O(1) time? Why?

Yes, push and pop are also O(1) since they merely work with one end of the data structure
- the top of the stack which can be implemented simply and effectively.

Test your code with PUSH(10), PUSH(30), POP(), PUSH(80), and POP

 To create as many nodes as possible the elements will always get installed in the memory.
 First, we need to create the node
 Put the address of the first node of the above linked in the linked part of the node
 Update the top pointer and make it point to the node of the linked list.

Implementation

This study source was downloaded by 100000894591670 from [Link] on 12-15-2024 06:39:32 GMT -06:00

[Link]
 Assignment 5 5

This study source was downloaded by 100000894591670 from [Link] on 12-15-2024 06:39:32 GMT -06:00

[Link]
 Assignment 5 6

This study source was downloaded by 100000894591670 from [Link] on 12-15-2024 06:39:32 GMT -06:00

[Link]
 Assignment 5 7

The outcome should look like this:

10 -> 30 ->
Top element is 30
10 -> 80
Top element is 80
Code source: [Link]

PUSH(10), PUSH(30), POP(), PUSH(80), and POP

Part-3:

Implement a queue by a singly linked list L in Python or Java.

 Do the operations ENQUEUE and DEQUEUE take O(1) time?

Obviously, one dequeue () operation takes O(1) time. And remove N elements from the
queue will take O(N) time (in total). Just simply, One enqueue () operation takes O(1) time.

Test your code with ENQUEUE(4), ENQUEUE(1), ENQUEUE(3),

This study source was downloaded by 100000894591670 from [Link] on 12-15-2024 06:39:32 GMT -06:00

[Link]
 Assignment 5 8

This study source was downloaded by 100000894591670 from [Link] on 12-15-2024 06:39:32 GMT -06:00

[Link]
 Assignment 5 9

Code source:[Link]

Reference

cathyatseneca. (n.d.). Data structure animations using [Link].

This study source was downloaded by 100000894591670 from [Link] on 12-15-2024 06:39:32 GMT -06:00

[Link]
Powered by TCPDF ([Link])