# Lab 4
Name:Allu Sai Kowshik
Roll No.: CS22B004

---
## Question 1

**Code**

.data
array: .word 1,2,3,5,6,7,8,9,10,11,4
str: .string " "

.text
la t0 array
la t1 array
addi t2 zero 3
addi t3 zero 11
addi t0 t0 40
addi t4 zero 0

Loop:
lw t5 0(t0)
add t5 t5 t2
sw t5 0(t0)
addi t0 t0 -4
addi t4 t4 1
blt t4 t3 Loop

la t1 array
addi t4 zero 11

PrintLoop:
lw t6 0(t1)
add a0 t6 zero
li a7 1
ecall

la a0 str
li a7 4
ecall

addi t1 t1 4
addi t4 t4 -1
bne t4 zero PrintLoop

## Question 2
**Code**

.data
data_array: .word 3,5,7,2,4
true_msg: .string "true"
false_msg: .string "false"
exit_msg: .string "exited with code 0"
newline_msg: .string "\n"

.text
la s0 data_array
addi s1 zero 7
addi s2 zero 1
addi s3 s1 -2
addi s4 zero 0

check_loop:
      lw s5 0(s0)
      lw s6 4(s0)
      lw s7 8(s0)
      and s5 s5 s2
      and s6 s6 s2
      and s7 s7 s2
      and s5 s5 s6
      and s7 s7 s6
      and s5 s7 s5
      beq s5 s2 print_true
      addi s0 s0 4
      addi s4 s4 1
      beq s4 s3 print_false
      j check_loop  
print_true:
      la a0 true_msg
      li a7 4
      ecall
      j exit_program
print_false:
      la a0 false_msg
      li a7 4
      ecall
      j exit_program
exit_program:
      la a0 newline_msg
      li a7 4
      ecall
      la a0 exit_msg
      li a7 4
      ecall

## Question 3
**Code**

.data
newArray: .word 10 20 30 40 50 60 70 80
newShuffle: .word 0 0 0 0 0 0 0 0
str: .string " "

.text
la t0 newArray
la t1 newShuffle
la t2 newShuffle
addi t3 x0 0 
addi t4 x0 4 
addi t5 x0 8 

Loop:
    lw t6 0(t0)
    sw t6 0(t1)
    lw t6 16(t0)
    sw t6 4(t1)
    
    addi t0 t0 4 
    addi t1 t1 8
    addi t3 t3 1 
    beq t3 t4 print 
    j Loop
    
print:
    lw t6 0(t2)
    addi a0 t6 0
    li a7 1
    ecall
    
    la a0 str
    li a7 4
    ecall
    
    addi t2 t2 4
    addi t5 t5 -1
    beq t5 x0 exit
    j print
    
exit:
    li a7 10
    ecall

## Question 4
question 169
Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

**Code**

.data
nums:       .word 3, 2, 3
numsSize:   .word 3
output:     .string "Majority element: "

.text
.globl _start

_start:
    la a0, nums
    lw a1, numsSize

    call majorityElement
    
    la a0, output
    li a7, 4
    ecall

    mv a0, t2
    li a7, 1
    ecall

    li a7, 10
    ecall

majorityElement:
    li t1, 0
    lw t2, 0(a0)
    addi t0, a0, 4

loop:
    lw t3, 0(t0)
    beqz t1, set_candidate
    beq t2, t3, increment_count
    addi t1, t1, -1
    j end_loop

set_candidate:
    mv t2, t3
    li t1, 1
    j end_loop

increment_count:
    addi t1, t1, 1
    end_loop:
    addi t0, t0, 4
    addi a1, a1, -1
    bnez a1, loop

    ret

## Question 5
Define the structure of a node:

Each node in the linked list will contain two fields: a data field to store the value, and a pointer field to point to the next node in the list.
Define constants:

Define constants to represent the offsets of the data field and the next pointer field within each node.
Implement functions:

Implement functions to perform various operations on the linked list:
initialize_list: Initializes the linked list by setting the head pointer to null.
insert_front(data): Inserts a new node with the given data at the front of the linked list.
insert_end(data): Inserts a new node with the given data at the end of the linked list.
delete(data): Deletes the node containing the given data from the linked list.
search(data): Searches for a node with the given data in the linked list.
traverse: Traverses the linked list and prints the data of each node.
reverse: Reverses the linked list.
Handle memory management:

Implement functions to allocate and deallocate memory for nodes as needed.
Ensure proper error handling:

Handle cases where the list is empty or when performing operations such as deletion or searching for data that does not exist in the list.

## Question 6

The malloc function allocates memory by calling sbrk, which can be expensive. To minimize calls to sbrk, we can allocate more memory than needed. When malloc is called, we keep track of allocated memory using a hashmap, along with the remaining available space. The free function releases allocated memory. It looks up the memory address in the hashmap, removes the entry, and adds it to another hashmap representing available space. Fragmentation issues may occur due to loading and unloading processes in memory, causing fragmented space. To address this, we can combine adjacent free spaces when calling free, reducing overhead.