# Lab 4
Name: SUDDULA VINEETH RAGHAVENDRA
Roll No.: CS22B045

---
## Question 1
**Code**

.data
array: .word 1 2 3 4 5 6 7 8 9 10 11
str: .string " "
str1: .string "after updation of the array"
str2: .string "\n"
base: .word 0x10000000

.text
lw x21,base
addi x21,x21,40 #we storing the last element address in the x21.
lw x22,base
li x3,3
li x2,-1
li x11,11
li x9,10
li x5,0
loop:
    beq x2,x9,print
    addi x9,x9,-1
    lw x10,0(x21)
    addi x10,x10,3
    sw x10,0(x21)
    addi x21,x21,-4
    j loop
print:
    beq x5,x11,exit
    lw x6,0(x22)
    li a7,1
    mv a0,x6
    ecall
    li a7,4
    la a0,str
    ecall
    addi x5,x5,1
    addi x22,x22,4
    j print
exit:
    li a7,4
    la a0,str2
    ecall
    la a0,str1
    ecall

**Observation:**
* 4 5 6 7 8 9 10 11 12 13 14
after updation of the array

---
## Question 2
**Code**

.data
array: .word 2,6,4,1
base: .word 0x10000000
str1: .string "true"
str2: .string "false"
str3: .string "\n"

.text
lw x20,base
li x2,0 # for the iterator
li x9,9 # size
li x6,3
li x4,0   # checking zero
li x3,0 # count
li x5,1 # for doing and operation.
loop:
    beq x2,x9,print
    addi x2,x2,1
    lw x10,0(x20)
    and x22,x10,x5
    bne x22,x4,count
    beq x3,x6,print1
    li x3,0
    addi x20,x20,4
    j loop
    
count:
    addi x3,x3,1
    addi x20,x20,4
    j loop
print1:
    li a7,4
    la a0,str1
    ecall
    j exit
print:
    li a7,4
    la a0,str2
    ecall
    j exit
exit:
    li a7,4
    la a0,str3
    ecall
    
    

**Observation:**
* false

---
## Question 3
**Code**

# This is one approach taking extra space.
.data
array: .word 1,2,3,4,4,3,2,1
base: .word 0x10000000
base1: .word 0x20000000
str: .string " "
str1: .string "after updation"
str2: .string "\n"

.text
li x8,8 #size
lw x20,base
lw x22,base1
lw x23,base1
li x4,4
li x2,0
li x3,0
addi x21,x20,16
loop:
    beq x2,x4,print
    addi x2,x2,1
    lw x10,0(x20)
    lw x11,0(x21)
    sw x10,0(x22)
    addi x22,x22,4
    sw x11,0(x22)
    addi x22,x22,4
    addi x20,x20,4
    addi x21,x21,4
    j loop
print:
    beq x3,x8,exit
    lw x10,0(x23)
    li a7,1
    mv a0,x10
    ecall
    li a7,4
    la a0,str
    ecall
    addi x23,x23,4
    addi x3,x3,1
    j print
exit:
    li a7,4
    la a0,str2
    ecall
    la a0,str1
    ecall
    
    
    
    
    
#This is second approach just printing the elements.
.data
array: .word 1,2,3,4,4,3,2,1
base: .word 0x10000000
str: .string " "
str1: .string "after updation"
str2: .string "\n"

.text
li x8,8 #size
lw x20,base
li x4,4
li x2,0
li x3,0
addi x21,x20,16
loop:
    beq x2,x4,exit
    addi x2,x2,1
    lw x10,0(x20)
    lw x11,0(x21)
    li a7 1
    mv a0 x10
    ecall
    li a7 4
    la a0 str
    ecall
    li a7 1
    mv a0 x11
    ecall
    li a7 4
    la a0 str
    ecall
    addi x20,x20,4
    addi x21,x21,4
    j loop
exit:
    li a7,4
    la a0,str2
    ecall
    la a0,str1
    ecall

**Observation:**
* 1 4 2 3 3 2 4 1
after updation

---
## Question 4
**Code**

#leet code Question Number 268 Missing Number.

.data 
array: .word 9,6,4,2,3,5,7,0,1
base: .word 0x10000000
str: .string "missing value : "
.text
li x2,0     # iterator
li x3,0     # value
li x10,10   # size of 0 to 9 elements =10.
li x9,9     # size
lw x20,base
loop:
    beq x2,x10,loop1
    add x3,x3,x2
    addi x2,x2,1
    j loop
loop1:
    beq x9,x0,print
    addi x9,x9,-1
    lw x11,0(x20)
    sub x3,x3,x11
    addi x20,x20,4
    j loop1
print:
    li a7 4
    la a0 str
    ecall
    li a7 1
    mv a0 x3
    ecall

**Observation:**
* missing value : 8

---
## Question 5
**Pseudo Code**
First we have to create a intialize a node with the null . If we want to append any element then we have to allocate memory to that particular node. At the time of append we will check is the root node is equal to null or not. If it is equal to null then we will set head as the newnode.We will update the value of the address. For traversing we will check each node by updating the value of the address, is the value which is stored in the node is not equal to the null(zero) or not. If we reach null then we have to exit the traversal.Otherwise jump to the traversal again.

# Reading source internet.
# Assume registers x4, x5, x6 are used for parameters and temporary storage
# Assume a node structure with two fields: data and next

# Initialize an empty linked list
initList:
    li x4, 0        # Set x4 to null, indicating an empty list
    jr ra           # Return

# Allocate memory for a new node
allocNode:
    li x4, 8
    la x5, 9
    ecall
    jr ra

#append new Node.
addNode:
    la x6, allocNode #we are allocating the memory.
    jal ra, x6
    sw x5, 0(x4)
    sw x4, 4(x4)

    beqz x4, setHead # checking if x4 is 0.
    la x6, traverse
    jal ra, x6
    sw x4, 4(x4)
    jr ra

setHead:
    mv x4, x5

traverse:
    beqz x4, exit # if x4 becomes zero then end the traversal.
    lw x5, 4(x4)
    beqz x5, endTraverse
    mv x4, x5
    j traverse

exit:
    jr ra

---
## Question 6
(Reading Source internet)
When we ask memory using the malloc function, it will give us a larger memory than we asked for, by calling sbrk with a bigger size. Before providing us with the memory address, it keeps track of that memory in a special list (for now we assume it as usein list), along with the size you asked for. It also keeps track of the remaining available space with its starting point in another list (for now we assume it as available list).

At a later stage if we want to use free ,to return the memory, the function checks if the memory address you're freeing is in the "usein" list. If it is, it removes that entry from the "usein" list and adds it to the "available" list. Here, the free function might internally use brk or sbrk to manage the available memory.

But now the problem is we may lead to small pieces of unused memory scattered around, known as fragmentation. To handle this problem, we have to do like this.

Whenever we free some memory, it should also check if the adjacent memory is also free. If it is also free,then the two pieces are combined into one using brk or sbrk,so this reduces fragmentation. So by this we will be getting good performance and memory efficiency.