Author: mattchung

Earlier this morning, before starting the work week, I took my first linear algebra exam at the nearby Northgate Testing center.  The proctored exam covered the first four modules in the course, topics including:

• Gaussian elimination (row echelon)
• Gaussian Jordan elimination (row reduced echelon)
• Adding, subtracting, multiplying matrices
• Calculating the inverse of matrices (using identity matrices)
• LU Factorization

I felt well prepared (thanks again to Khan Academy and 3Blue1Brown). Going into the exam, I worked (and reworked) the suggested exercises in the textbook.  Honestly, I think if I hadn’t attempted the exercises, my mind would’ve tricked me into believing that I understood the material. But that obviously wasn’t the case because the different math problems had me fumbling around, furiously scribbling pencil all over my notebook paper followed by vigorous strokes of erasing. Anyways, 1 exam down — 2 more to go.

Next topic: calculating the determinant of a matrix (at this present moment, I have no idea what that means)

 

About a year has passed since I took computer organization and I’m a bit disappointed of how much of the material faded from my memory. I only realized this while reading about Exception Control Flow (ECF) in the book Computer Systems: A programmer’s perspective, when the authors mentioned:

As with a procedure call, the processor pushes a return address on the stack before branching to the handler

Section 8.1 Exceptions

I had to pause for a moment because despite a handful of assembly programs — one of them where I implemented quicksort — I totally forgot how, in assembly, how the return address gets handled. But after reviewing my own assembly program that I wrote earlier this year, I realized that the syscall directs the processor to store the PC value into the ra (return address) register.  Then, it’s the callee’s responsiblity to then save that value on the stack and after its routine finishes, call jr (jump return).

Here’s some sample code

main:
	la $a0, numbers		# Load the address numbers into $a0, the first argument
	li $a1, 0		# Load 0 into $a, the second argument
	lw $t0, length		# Load the length of the array into temporary register $t0
	sub $a2, $t0, 1		# Subtract 1 from the length of the array and store into $a3, the first argument
	jal quicksort
	li $v0, 10
	syscall

quicksort:

quicksort_if:

	bge $a1, $a2, quicksort_end_if	# CHeck if low < high

quicksort_body:
	addi, $sp, $sp, -24	# Update the stack pointer, allocating enough room for savin the 6 registers
	sw $ra, 0($sp)		# Store return address on the stack
	sw $s0, 4($sp)		# Store $s1 on the stack
	sw $s1, 8($sp)		# Store $s2 on the stack
	sw $s2, 12($sp)		# Store $s3 on the stack
	sw $s3, 16($sp)		# Store $s3 on the stack
	sw $s4, 20($sp)		# Store $s3 on the stack
	move $s0, $a0		# Store $a0 (address of array) into $s0
	move $s1, $a1		# Store $a1 (low) into $s1
	move $s2, $a2		# Store $a2 (high) into $s2
	jal partition		# Call the subprogram partition
	move $s4, $v0		# Store pivot -1 into $a2
	move $a0, $s0		# Store $s0, array, into $a0
	move $a1, $s1		# Store $s1, low, into $a1
	move $a2, $s4		# Store pivot position in $a2
	sub $a2, $a2, 1		# Subtract 1 from $a2 (i.e. pivot - 1)
	jal quicksort		# First call to quicksort (i.e. quickSort(array, low, pivotPosition - 1)
	move $a0, $s0		# Store array into $a0
	move $a1, $s4		# Move pivot into $a1
	add $a1, $a1, 1		# Add 1 to $a1 (i.e. pivot + 1)
	move $a2, $s2		# Move high (i.e. $s2) into $a2
	jal quicksort		# Second call to quicksort (i.e. quickSort(array, pivotPosition + 1, high)
	lw $ra, 0($sp)		# Restore the return address from the stack and back into $ra
	lw $s0, 4($sp)		# Restore $s0 from the stack
	lw $s1, 8($sp)		# Restore $s1 from the stack
	lw $s2, 12($sp)		# Restore $s2 from the stack
	lw $s3, 16($sp)		# Restore $s2 from the stack
	lw $s4, 20($sp)		# Restore $s2 from the stack
	addi $sp, $sp, 24	# Pop the call frame

I’ve been sharpening my C programming skills because I’m now working on a team (i.e. EC2 Networking) within Amazon Web Services that requires skills in lower level software development. And I must say, I’m truly rusty. A noob. On top of that, my only experience with C in the past has been fairly superficial, me dabbling here and there in the K & R book, long before I had taken any computer science courses.  But since taking computer organization and data structures, I have a tight understanding of pointers and their practical uses.

But I digress.

I’m currently working through a book written by Zed Shaw, the book titled “Learn C the hard way.” I had picked up the book at the local library in Seattle, stumbling upon it while I was running my fingers along the spines of books in the computer science section. This book has mixed reviews. Some websites strongly dissuade readers from reading anything published by this particular author.  But others recommend it. So, I’m taking their advice with a grain of salt and forming my own opinion.

At the end of every chapter, the author recommends some extra credit exercises.  In one of these exercises, the author suggests implementing a stack data structure in C.  Now, there are two popular implementations when building a stack: using an array and using a linked list. So, I took this exercise as an opportunity to write a simple stack data structure using linked lists (you gotta love them C pointers).

Here’s the program output:

./stack_linked_list

Stack is empty. Pushing 10 to the top of stack
Stack is not empty. Pushing 20 to the top of the stack
Stack is not empty. Pushing 30 to the top of the stack
Popped item: 30
Peeking at next item: 20
Peeking at next item: 20
Peeking at next item: 20
Popped item: 20
Popped item: 10
Popped item: -1

And the corresponding code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct Node {
    int value;
    struct Node * next;
};

struct Stack {
    int count;
    struct Node * top;
};


bool isEmpty(struct Stack * stack)
{
    return stack->top == NULL;
}

void push(struct Stack * stack, int item)
{
    /*
     * Edge case: first item to push
     */

    struct Node * node = (struct Node *) malloc(sizeof(struct Node));
    node->value = item;

    if (stack->top == NULL){
        printf("Stack is empty. Pushing %i to the top of stack\n", item);
        stack->top = node;
    } else {
        printf("Stack is not empty. Pushing %i to the top of the stack\n", item);
        node->next = stack->top;
        stack->top = node;
    }

    stack->count++;
    return;

}
int pop(struct Stack * stack)
{
    if (isEmpty(stack)){
        return -1;
    }

    struct Node * node = stack->top;
    stack->top = node->next;

    return node->value;
}

int peek(struct Stack * stack)
{
    if (isEmpty(stack)){
        return -1;
    }

    return stack->top->value;
}


int main(int argc, char * argv[])
{
    struct Stack stack;
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    printf("Popped item: %i\n", pop(&stack));
    printf("Peeking at next item: %i\n", peek(&stack));
    printf("Peeking at next item: %i\n", peek(&stack));
    printf("Peeking at next item: %i\n", peek(&stack));
    printf("Popped item: %i\n", pop(&stack));
    printf("Popped item: %i\n", pop(&stack));
    printf("Popped item: %i\n", pop(&stack));
    return 0;
}