Laboratory for ICS 51 - Winter
2005
Course webpage:
People:
Shannon Tauro (Instructor office hours:
Tu-Th 10-11 at CST2 102)
Ersin
Uzun (TA office hour: Wed 11.00-12.00 at CST TA room)
Rabia
Nuray (TA office hour: Mon 2.30 -3.30 at CST TA room)
Basic information to familiarize yourself
with the lab environment. This includes information on submission procedures.
PLEASE read this before starting work on
your lab assignments.
Announcements
PLEASE check at least once a week.
Resources:
Assignment 1 DUE Date: 01/26/2005
(testing
file used in grading, to test the extras remove the indicated lines)
Implementation information, also provided to you
in comments inside lab1.c. The numbers will be provided to you in registers
eax, ebx. Find the GCD and put it into the register edx. Write your code ONLY
inside the marked block. The remaining code takes care of the details of
parameter passing- DO NOT modify. To test your code, look at
comments inside lab1-testing.c
Hint:
A really beautiful and easy algorithm to find the
GCD of two given integers is given below. You can use the same idea and
reimplement it in assembly.
Gcd(int a, int b, int
*result){
while(a!=b){
if(a
> b)
a
= a - b;
else
b = b - a;
}
*result
= a;
}
Assignment2
DUE Date: 02/02/2005 (testing file used in grading)
In this lab you are asked to implement a function that counts the number of
vowels in a given string. Implementation information, also provided to you in
comments in the lab2.c.
Recall: Write your code ONLY inside the marked block. the
remaining code takes care of the details of parameter passing -- DO NOT modify.
Tester of your function is in lab2-testing.c.
Assignment3 DUE Date: 02/10/2005 (testing
file used in grading)
In this lab you will implement a binary search in assembly. Definition of
binary search is searching a sorted array by repeatedly dividing the search
interval in half. Begin with an interval covering the whole array. If the value
of the search key is less than the item in the middle of the interval, narrow
the interval to the lower half. Otherwise narrow it to the upper half.
Repeatedly check until the value is found or the interval is empty.
Note: Please read the comments in the given code before
starting implementation. Write your code
ONLY inside the marked block. The remaining code takes care of the details of
parameter passing -- DO NOT modify. Tester of your function is in
lab3-testing.c.
Assignment4 DUE Date: 02/23/2005
The goal of this lab assignment is to learn how to
deal with the stack in assembly. For this purpose you will write a simple
program to evaluate the reverse Polish notation formulas.
Reverse polish notation is
the ideal notation for evaluating formulas on a computer with stack. The
formula consists of n symbols, each one either an operand or an operator. The
algorithm for evaluating the reverse Polish notation formula using stack is
simple; Scan the reverse Polish string from left to right. When an operand is
encountered; push it onto the stack. When an operator is encountered; pop
needed number of operands from the stack, execute the corresponding instruction
and push the result onto the stack.
Example :
The
formula (b) is the reverse polish notation of the formula (a).
(8 + 2 x 5)/(1 + 3 x 2 - 4) (a)
8 2 5 x + 1 3 2 x + 4 -/ (b)
In this assignment you will given an integer array
containing both operators and the operands. Operators are encoded with the negative
integers. So, you're supposed to run your program on non-negative integers.
ADD : -1
SUB : -2
MULTIPLY by 2: -3
DIVISION by 2: -4
AND : -5
OR : -6
XOR : -7
NOT -8
Beware that the MULTIPLY,DIVISION, and NOT
operations are unary, takes one argument.
Assignment5 DUE Date: 03/11/2005
The Goal of this lab assignment is to learn how to
deal with function calls and recursion in assembly. You will implement a
recursive quicksort algorithm.
The quick sort is an
in-place, divide-and-conquer, massively recursive sort. Below is the
implementation in high level language.
void quickSort(int
numbers[], int array_size)
{
q_sort(numbers, 0,
array_size - 1);
}
void q_sort(int
numbers[], int left, int right)
{
int pivot,
l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left <
right)
{
while
((numbers[right] >= pivot) && (left < right))
right--;
if (left !=
right)
{
numbers[left] = numbers[right];
left++;
}
while
((numbers[left] <= pivot) && (left < right))
left++;
if (left !=
right)
{
numbers[right] =
numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left <
pivot)
q_sort(numbers, left,
pivot-1);
if (right >
pivot)
q_sort(numbers,
pivot+1, right);
}
The
framework is prepeared according to the sample code above, so what you need to
do is basically porting this implementation into assembly. You are restricted
to use stack while passing the function parameters. Good Luck!