CSE338--Assignment 1 Solved

QUESTION 1. In this program you are required to count number of occurrences of characters in a given string. Your procedure must ignore the non-alphabetic characters including numbers, punctuations etc. Upper and lower case letters must be counted as same character. Given the following string as an input, output must be printed as on the table with sorted character list and number of occurrences.

An example run:

Enter the String: This is Computer Organization course!

Program output must be:

 Character          Occurence        o          4 t 3 i        3 s 3 r        3

c                      2

u                      2

e                      2

a                      2

n                      2

h                      1

m                     1

p                      1

g                      1

z                      1

 

 

QUESTION  2. In this procedure, the input character list contains ASCII characters representing single-digit or multi-digit decimal numbers, separated by spaces. You are required to sort these numbers (from smaller to larger) separated by one space character and store the sorted list in the output_list argument. (The numbers may be negative, which means that there may be minus sign as the first character of a number.)

An example run:

Input: 1 6 23 -5 18

Output: -5 1 6 18 23

Note: Multi-digit decimal numbers must be converted from ascii representation and number of digits might vary up to the 32 bit data size limits. For example -98625 can be also given as an integer.

 

QUESTION 3. Write a MIPS assembly program to calculate the num_prime(N) function,  which is the number of prime numbers less than N. Use the sieve of Eratosthenes method to generate prime numbers in the interval [2,N]. Suppose that maximum value of N can be 1,000,000. Here is an example tabulation of num_prime(N):

Please enter an integer number for num_prime(N):

10

prime(10) is 4.

Please enter an integer number for num_prime(N):

100

prime(100) is 25.

Please enter an integer number for num_prime(N):

1000000 prime(1000000) is 78498.

 

QUESTION 4. Write a MIPS assembly program to construct Huffman Code tree [1].

Huffman code is used to compress data by assigning the shorter binary strings for more occurring characters in a string.  As can be seen from the sample run given below, there will be two input strings. Your program will accept the first string to construct Huffman code tree (Hint: You can use Question 1 which counts the occurrences of characters in a string). The second input will be a string to be coded using the constructed Huffman Code. The output of the program will be binary compressed string. Assume that in the second input string there will be no characters that do not exist in the first string. Note that spaces will be ignored from both input strings and will not be printed on output strings.

An example run:

Enter the string to construct Huffman Code: AABBBCCBBDDDDEFFFFFBC

Enter the string to be converted using Huffman Code: ABC Output:111110110

Output can be constructed using the Huffman code tree[1]. Following figure illustrates the Huffman tree for given string.

 

 Character          Occurence         Binary Code (After Running Huffman Coding) 
A                     2
1111
B                     6
10
C                     3
110
D                     4
00
E                      1
1110
F                      5
01
 

MENU  : Your program should support a Menu including all questions above. A sample execution scenario given below:

Welcome to our MIPS project!

Main Menu:

1.Count Alphabetic Characters

2.Sort Numbers

3.Prime (N)

4.Huffman Coding

5.Exit

Please select an option: 1

 These options must be printed inside a loop until “Exit” option is selected. 

 When the user select option 1, you should print the followings:

Enter the String: This is Computer Organization course! Character Occurrence

o 4 t 3 i 3 s 3 r 3

c 2 u 2 e 2 a 2 n 2

h 1 m 1 p 1 g 1 z 1

Main Menu:

1.Count Alphabetic Characters

2.Sort Numbers

3.Prime (N)

4.Huffman Coding

5.Exit

Please select an option: 2

Input: 1 6 23 -5 18

Output: -5 1 6 18 23 Main Menu:

1.Count Alphabetic Characters

2.Sort Numbers

3.Prime (N)

4.Huffman Coding

5.Exit

Please select an option:  3

Please enter an integer number for prime(N):100 prime(100) is 25.

Main Menu:

1.Count Alphabetic Characters

2.Sort Numbers

3.Prime (N)

4.Huffman Coding

5.Exit

Please select an option: 4 Please enter the string to construct Huffman Code: 

AABBBCCBBDDDDEFFFFFBC Please enter the string to be converted using Huffman Code: 

ABC

Output:111110110

Main Menu:

1.Count Alphabetic Characters

2.Sort Numbers

3.Prime (N)

4.Huffman Coding

5.Exit

Please select an option: 5

Program ends. Bye :)