CSCI 151 Introduction to Computer Science



CSCI 152 Introduction to Computer Science II

Assignment 2

The due date is Friday, March 16, 2007

*************************************************************Do your own work. Programs which are written in groups are easily identified and will earn grades of 0 for all participants.

************************************************************************

Skill set for this assignment:

• One-Dimensional Arrays, Two-Dimensional Arrays, Strings

****************************************************************

Assignment 2 Instructions

• Create a subdirectory Assign2 in your CSCI152 directory: while you are in your home directory, do the following:

cd CSC152

mkdir Assign2

• Create a separate file (source file) for each program that you have in Assignment 2, you will have 5 programs, which you can call your files prog1.c, prog2.c, ...

or you can choose use other names of your choice. I will assume that the programs are called prog1.c, prog2.c, ...

• Before you submit your assignment, compile and run each program and

make sure that the program doesn't have any compilation or logical errors,

and the program produces the correct result.

• In order to compile the first program do the following: gcc -o prog1.c prog1

• This command will create an executable file prog1 for your first program

• You can run the executable file as follows: prog1

• Compile and run all 5 programs before you go the next step- Submission

Submission of the Assignment 2:

Send the source file for each program by e-mail to yanako@cs.widener.edu

Problem 1 (20 points):

• Write a function void changeString (char s[ ]), that accepts string parameter and exchange each appearance of letter A in the string by letter B, and each appearance of letter a in the string by letter b. The rest of the characters remain without change.

• Write a C program that reads a string and changes A by B and a by b using function changeString. The program should print an original input string and the string that was obtained after changes. For example, if the input was: I like a song of ABBA, the output should be:

Original string is: I like a song of ABBA

The string after changes is: I like b song of BBBB

• Define a size of string using #define statement

• To read a string you can use one of the possibilities that was shown in the lab – using scanf, using gets or using getchar

Problem 2 (20 points):

• Write a program that will perform a statistical analysis of the integer data. The program will read one-dimensional array of 10 integers, and finds median, mode and mean using the appropriate functions that you wrote. The program prints an input array and median, mode and mean with appropriate message.

• Definitions:

o Median - the value that will be in the middle in the sorted array

o Mode - the most frequent value

o Mean - average of the elements of the array

• To solve the problem you would need to write the following functions:

o void ReadArray (int A[ ] , int size) – reads an array A

o void PrintArray (int A[ ] , int size) – prints an array A

o int mode(int A [ ] , int size) – finds and returns mode of A

o int mean(int A [ ] , int size) – finds and returns mean of A

o double median(int A [ ] , int size) –finds and returns a median of A

• If you think, that sorting will help you to solve the problem, you can sort an input array by using any sorting algorithm that we learned in the lecture. You don’t need to write the sorting function by yourself, you can use one from the course website.

• Define the size of array using #define statement.

Program 3 (20 points):

• Write a program that reads one-dimensional array of 10 integers and sorts the input array using Selection Sort. Use SelectionSort function to do sorting. Your program should print the input array and the sorted array with an appropriate message.

• Definition: Selection Sort works as follows: first find the largest element in the array and exchange it with the element in the last position, then find the second largest element and exchange it with the element in the position one before last, and continue in this way until the entire array is sorted.

• You would need to write the following functions:

• int max(int A[ ], int num_elements) - finds and returns the position of the maximal element in array A, where num_elements is the size of the array.

• void SelectionSort(int A [ ], int num_elements) - sorts the array A using Selection Sort algorithm

• void ReadArray (int A[ ] , int num_elements) - reads an array A

• void PrintArray (int A[ ] , int num_elements) - prints an array A

Problem 4 (20 points):

Write a function void read_array (int A[ ] [COL], int num_row, int num_col) that reads a two dimensional array, COL - is the number of columns in array A. Write a C program that reads an array of 5 rows and 7 columns and finds and prints the sum of the elements in each row and finds and prints the row (its numeric value) with the maximal sum.

Problem 5 (20 points)

A square array of numbers is said to be a "magic square" if all the rows, columns, and diagonals add up to the same number. For example, here is a 3 ×3 magic square:

4 9 2

3 5 7

8 1 6

Each row, column, and diagonal of this square add up to 15.

Write a program that reads a two dimensional array of integers of size 5 (5 rows and 5 columns) and determines if it is a magic square.

Bonus part for this question: (10 points)

There is a straightforward algorithm that will generate a magic square whose width is an odd number. Begin with a 1 in the center of the bottom row, then fill in the remainder of the array by the following rules:

1. Try to place the next integer (one greater than the last one you placed) in the cell one slot below and one slot to the right of the last place filled. If you fall off the bottom of the array, go to the top row. If you fall off the right edge of the array, go to the leftmost column. If that cell is empty, write the next integer there and continue.

2. If the cell found above is full, go back to where you wrote the last integer and write the next integer in the cell directly above it.

Write a program that will build a magic square. The size of the magic square will be defined by user input. Assume that the maximum size is 11.

Bonus Problem 1 (20 points):

Write a program that defines a two-dimensional array 4x4 of integers and fill it with the random numbers between 0 and 2 (including 0 and 2). Perform 5 iterations on the array. Each iteration will change the elements as follows: each value will be replaced by the sum of the neighbors (not including the element itself). While doing summation you have to use “old” values of the array. See example below. Print out the input array and the resulting array that was obtained after each iteration. You should write the following functions that will help you to solve the problem:

• void fill_array_random(int A [ ][COL], int num_row, int num_col) - fills the array with random values between 0 and 2

• void play_game(int A[ ][COL], int num_row, int num_col, int num_iterations) - the function will perform num_iterations. Each iteration replaces the elements by the sum of the neighbors (not including the element itself and taking in account the “old” values)

• void write_array(int A[ ][COL], int num_row, int num_col) - prints the two dimensional array

Example:

Input Array:

|0 |2 |1 |1 |

|0 |1 |0 |0 |

|1 |1 |2 |0 |

|1 |0 |1 |2 |

First Iteration:

|3 |2 |4 |1 |

|(0+2+1) |(0+0+1+0+1) |(2+1+0+0+1) |(1+0+0) |

|5 |7 |8 |4 |

|(1+1+1+2+0) |(0+0+1+1+2+0+1+2) |(2+1+1+2+0+0+1+1) |(1+1+0+2+0) |

|3 |6 |5 |5 |

|(0+1+1+0+1) |(0+1+0+2+1+0+1+1) |(1+0+0+0+2+1+0+1) |(0+0+2+1+2) |

|2 |6 |5 |3 |

|(1+1+0) |(1+1+1+2+1) |(0+1+2+0+2) |(1+2+0) |

You need to continue this process. Your program should perform 5 iterations.

Bonus Problem 2 (20 points):

The Polybius’ Checkboard Cipher (205 – 123 B.C.) uses the form of substitution in which pairs of numbers substitute for letters. An adaptation of the Polybius’ Checkboard Cipher to the English alphabet is shown in the table below:

| |1 |2 |3 |4 |5 |

|1 |A |B |C |D |E |

|2 |F |G |H |IJ |K |

|3 |L |M |N |O |P |

|4 |Q |R |S |T |U |

|5 |V |W |X |Y |Z |

Each letter is substituted by the pair of numbers, where the first number is a numerical value of the corresponded row and the second number is the numerical value of the corresponded column. For example, A will be encrypted by 11, C will be encrypted by 13, and M will be encrypted by 32.

For example, text POLYBIUS produces the following encoded message (ciphertext)

3534315412244543

• Write a program that reads a string of characters and encrypt the input string using the Polybius’ Checkboard Cipher.

• Write a program that reads a string of integers that corresponds to the ciphertext that was produced using Polybius’ Checkboard Cipher. The program decipher the message and prints the original string of characters.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download