60-140

Introduction to Algorithms and Programming I

Dr. Christie Ezeife

Lab. Exercises #1 Solution (Lab Date: Week 3 of Classes)

Objectives are to:

1. Learn basic Unix commands for preparing a source C program file, compiling a C program and executing a C program with input data from the keyboard. Also, learn how to use script file for handing in record of source program file, compilation and execution of programs.

2. Practise on concepts taught in chapter 1 of text including how to present solutions to simple problems in the form of an algorithm (or program), how to identify the necessary input and output data of a problem. Also, practise on conversions of numeric values from one number base to another, and character data from character to ASCII code and vice versa.

Que. 1. Type, compile and run the C program of Figure 1.15 in the course book. This program computes and prints the binary number equivalent of any given positive decimal number. Hand in or show your source program file, the input data and the output of your run. Use the following set of input data:

52

300

436

16

98

Solution to Que 1

/* Given a decimal number, convert it to its binary equivalent. We are also including <math.h> to use math built functions, but must compile with the -lm option to link in math library with command cc file.c -lm */

#include <stdio.h>

#include <math.h>

/* Given a decimal number, convert it to its binary equivalent. For example, given 52, it returns 110100. Note though that we can only work with integer numbers and we need to find a way to present our output binary number like 110100 correctly as an integer. */

int main (void)

{

int num_d; /*input number */

int num_b; /* output number with only digits 1 and 0 */

int decimalnum, quotient, remainder, power2; /* other variables */

/* Now sequence of instructions for solving the problem */

printf("Type the decimal number you want to convert to binary:\t");

scanf ("%d", &num_d); /*read decimal number */

power2 = 0; /* we set the bit position as least significant */

num_b = 0; /* set the current binary number to 0 */

/* compute its binary equivalent */

decimalnum = num_d; /* make a copy of the decimal number */

step5: quotient = num_d / 2;

remainder = num_d % 2;

num_b = num_b + (remainder * pow (10, power2));

if (quotient != 0) {

num_d = quotient;

power2 = power2 + 1;

goto step5; /* this repetition is better done with while

loop instruction but kept this way for simplicity */

}

/* print the number and its binary equivalent */

printf ("Binary equivalent of %d is %d.\n", decimalnum, num_b);

return 0;

}

Que. 2. Compile and run the same program of Figure 1.15 of text and show the source code, compilation, execution, program input and output data in a script file.

Solution to Que 2

A record of all Unix commands executed during a logon session or part of a logon session can be saved in a script file by simply initiating the recording with the Unix script command and ending the recording when completed, with an exit command as follows.

i. Open a Unix terminal window and type:
script lab01_scriptfile <Enter>
[The general command is script filename, our script file here is lab01_scrptfile]

ii. Now display your source program file with the Unix cat command as:
cat lab01.c <Enter>
[The command cat filename is used to display contents of filename on the screen]

iii. Now compile the program by typing:
cc lab01.c <Enter>

iv. Now Run the program by typing:
a.out <Enter>

v. Now, the CPU is waiting for you to type in a positive decimal number as before.

You can re-run the program with the following decimal numbers.
52

300

436

16

98

vi. After the result of the program has been displayed, you must exit script session by typing:
exit <Enter>
[Failure to exit will prevent the script file from being saved and created.]

Que. 3. Practise with other Unix commands to list all the files in your directory, see the contents of your script file, send the script file to your GA, send your script file to your home computer so that you can print it.

Solution to Que 3

i. To see all files in the current directory including the script file, type:
ls <Enter>

ii. To see contents of the script file, type:
cat lab01_scriptfile <Enter> or
more lab01_scriptfile <Enter>

iii. To send a file like your script file lab01_scriptfile (which is currently on the server.uwindsor.ca) to your home computer so that you can print it, you need to use SSH file transfer program (SFTP) to transfer files from one computer (e.g., sol.cs.uwindsor.ca) to another (e.g., a PC or laptop). Note that you can only do this exercise when you have a PC or laptop and still connected to a Unix server. Thus, you can complete it at home to learn how to transfer your files and assignments. To use SFTP, follow the steps below:

a. From your home PC computer or any PC or laptop that has internet connection and already has the SSH client installed on it, launch the SSH client software to log on to a campus Unix server from PC. You can log on to sol.cs.uwindsor.ca or any new server name available at the time of doing this lab.

While the SSH terminal or window is used to issue any Unix command on the remote server, the SFTP terminal or window is used to transfer files between the two computers. Open up the SFTP terminal (the secure file transfer program) icon. This SFTP window looks like popular Windows explorer window. On the SFTP window, there are two panes where the left pane has a listing of files in the local computer (e.g., PC or laptop) and the right pane has a listing of files in the remote computer (e.g., the Unix server like sol.cs.uwindsor.ca).

b. Use the SFTP menu commands to download files from Unix server to PC and to upload files from PC to Unix server. You can also just drag and drop files from one computer (e.g., right pane) to another (e.g., left pane) the same way you would do it with Windows explorer.

Now, download your scriptfile called lab01_scriptfile.

c. Print your scriptfile lab01_scriptfile with a printer connected to the PC or laptop. Once you have downloaded your scriptfile lab01_scriptfile onto your PC, you can open it up with Wordpad or Notepad and print the file so it can be handed in for marking later.

iv Practise with other Unix commands for creating and deleting directory, deleting file, changing directory, renaming a file, making a copy of a file and so on.

To create a new directory on Unix, use the mkdir command as:
mkdir dirname <Enter>

v. To change to a different directory on Unix, use the cd as:
cd dirname <Enter>
[Note that dirname stands for the entire path of the directory from root (/)or home directory (~)].

vi. To move up one directory, for example to the parent directory, use:
cd .. <Enter>

vii. Wherever you are, to go to your home directory, use:
cd ~ <Enter>

viii. To make a copy of lab01.c file and keep in lab01cp.c, use:
cp lab01.c lab01cp.c <Enter>

ix. To delete a file like delete lab01.c after making a copy, use:
rm lab01.c <Enter>

x. To rename a file from lab01.c to lab02.c, use:
mv lab01.c lab02.c <Enter>

Use the ASCII table in Appendix A of course text, for exercises involving ASCII conversion.

Que. 4. Here is a message coded in ASCII using eight bits per symbol. What does it say?

01001001 00100000 01110111 01101111 01110010 01101011

00100000 01101000 01100001 01110010 01100100 00101110

Solution to Que 4

01001001	=	73	=	I
00100000	=	32	=
01110111	=	119	=	w
01101111	=	111	=	o
01110010	=	114	=	r
01101011	=	107	=	k
00100000	=	32	=
01101000	=	104	=	h
01100001	=	97	=	a
01110010	=	114	=	r
01100100	=	100	=	d
00101110	=	46	=	.

Que. 5. Show how the following instructions are represented in binary using ASCII by writing the codes for the instructions.

Q /= 20;

a--;

Solution to Que 5

Q	=	01010001
/	=	00101111
=	=	00111101
20	=	00010100
;	=	00111011

a	=	01100001
-	=	00101101
-	=	00101101
;	=	00111011

Que. 6. Convert each of the following binary representations to its decimal form.

(a) 110100 (b) 1000000 (c.) 1111111

Solution to Que 6

a. 0110100 = 52

b. 1000000 = 64

c. 1111111 = 127

Que. 7. Convert each of the following decimal representations to its equivalent binary form.

(a) 21 (b) 53 (c.) 400

Solution to Que 7

a. 21  = 10101

b. 53  = 110101

c. 400 = 110010000

Que. 8. Name all the hardware components of the computer and identify the function of each component.

Solution to Que 8

Hardware Component	Function of Component
Input device	Used to accept input from user
Output device	Used to display computer output to the user
Memory	Used to store programs and data to be
Primary memory	processed by the computer.
Secondary memory
CPU (central processing unit)	Used to process program instructions.

Que. 9.What is an algorithm? What is a program?, What is a problem?, What are input and output data?

Solution to Que 9

An algorithm is a sequence of steps for transforming input data to a desired output data. A problem has some input data, some output data and needs an algorithm for transforming its input data to its output data.

A program is the version of an algorithm written in a Computer executable language like a computer high-level or low-level language

Que. 10. For each of the conversions you did in problems (4) to (7) above identify the input, output and algorithm.

Solution to Que 10

The coarse algorithms are:

Qu4:
  Input: numbers(representing binary equivalent of a character),
ASCII table
  Output: a string of characters
  Algorithm:
For each input number do:
read each eight digit integer number representing a binary number
convert this binary number to its to decimal equivalent
convert this decimal number to ascii character using the ASCII table
print out the ASCII character equivalent for the decimal number.
    repeat

Qu5:
  Input: string of characters, ASCII table
  Output: binary numbers
  Algorithm:
    For each input character do:
read each each input charact
      convert each character to decimal value using the ASCII table
      convert the decimal value to binary number
      print binary number
repeat

Qu6:
  Input: binary number (binary)
  Output: decimal number (dec)
Intermediate: powerof2 = 0, quotient, remainder
  Algorithm
    read in binary number
dec = 0
remainder = binary%10
quotient = binary/10
    while (quotient != 0) do:
      {
dec = dec + (remainder * (2 ^ powerof2))
powerof2 = powerof2 + 1
remainder = quotient % 10
quotient = quotient / 10
}
    print dec

Qu7:
  Input: decimal number (decimal)
  Output: binary number (binary)
Intermediate: powerof10 = 0, quotient, remainder
Algorithm:
read decimal number
    binary = 0
    remainder = decimal % 2
    quotient = decimal / 2
    binary = binary + (remainder * (10 ^ powerof2))
    while (quotient != 0) do
      {
      power2 = power2 + 1
      remainder = quotient % 2
      quotient = quotient / 2
      binary = binary + (remainder * (10 ^ powerof2))
}
print binary