(5/5)

Objectives 3

In this lab activity and assignment, we will sharpen our programming skills with array oper- ations and sorting.

2 Introduction

Perhaps some of you have read Carl Sagan’s superb Sci-Fi novel “Contact”. In the novel

“An alien tells the main character (Ellie Arroway) that certain megastruc- tures in the universe were created by an unknown advanced intelligence that left messages embedded inside transcendental numbers. To check this, Arroway writes a program that computes the digits of π in several bases, and eventually finds that the base 11 representation of π contains a sequence of ones and zeros that, when properly aligned on a page, produce a circular pattern.”1

Indeed, there may be fascinating hidden patterns in π, and waiting to be discovered!2

In this assignment, we will do our own pattern hunting, and look for palindromes among the digits of π. Palindromes are words or numbers (which are our focus in this assignment)

1https://math.stackexchange.com/questions/1104660/patterns-in-pi-in-contact 2https://theconversation.com/pi-might-look-random-but-its-full-of-hidden-patterns-55994

That are same when we read backwards or forwards. For example, “22” or “14941” are palindrome numbers.

Palindromes have interesting scientific and engineering applications, such as in genetic sequencing technologies [1] or robotics [2].

3 Programming Assignment

The programming assignment is as follows:

1. Download the file pi 50m.zip containing the first 50 million decimal digits of π (the file is a zipped ordinary text file, so you need to unzip it after downloading, the actual filename you should read the digits is pi 50m.txt).

2. Write a C program that will

Read the digits of π from the file pi 50m.txt, (See Appendix A for an example of reading a file character-by-character).3

Search and count the number of palindromes of increasing length starting from the 2-digit long ones, record the digit distances between each successive palindromes until reaching a length that no palindrome of that length is detected.

For example, first two successive 2-digit long palindromes of π and the distance between them are as follows:

3.14159265358979323846264338327950288419.....

^--9-dig--^ distance

So, our “digit distance” definition is the number of digits sandwiched between the beginning of the first palindrome to the beginning of the second one. In our example above, first palindrome is 33 and the second is 88. I count 9 digits as the digit distance.

Sort the digit distances recorded separately for each palindrome length, then find the median distance.4

Report the findings on the terminal window exactly in the following format:

Palindrome

Length Number of

Palindromes Median Digit

Distance

2 XX..XX P..P

3 Y..YY Q.QQQ..Q

4 ZZZ..ZZ R..R.R

. . .

. . .

N 0 -

Where, N is the palindrome length that no palindromes are found.

3We will cover the details of standard I/O soon, but for the purpose of this lab and assignment, you can use the code provided in the appendix.

4Reminder: “Median is the middle number in a sorted list of numbers. To determine the median value in a sequence of numbers, the numbers must first be sorted, or arranged, in value order from lowest to highest or highest to lowest. If the list has odd number of elements, the middle one is selected. Otherwise, you must choose the smaller one of the numbers that are ‘in the middle’.” For example, this sorted list has even number of elements: (1, 2, 3, 4, 5, 6, 8, 9). You must report the smaller of (4, 5) as the median, which is 4.

3. Rename your program as ece2071 asg1.c, and submit as a single .c file containing only ASCII text characters (no other formats will be accepted). Do not submit any other files. Please read carefully the submission rules and marking procedure provided in Appendix B.

A Sample C Program for Reading a File Character-by-Character

The following example shows how to read a file one character at a time (for further details, you can refer to Chapter 11 of the textbook [3]).

1 #include <stdio.h>

/*

Compile with:

gcc -std=c17 -pedantic -Werror ece2071_asg1.c -o ece2071_asg1 -lm

*/

int main(void)

{

10 int c;

unsigned int count = 0;

/* Do NOT change the filename! Otherwise your assignment will fail. */ FILE *file = fopen("pi_50m.txt", "r");

if (file == 0) {

printf("I can’t open the file for reading.\n"); return -1;

}

20 while ((c = fgetc(file)) != EOF) {

/* Your palindrome number hunting routines could start here */ count++;

}

printf("The file is %d characters long.\n", count); fclose(file);

return 0;

}

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of