Assignment
Part I
In this assignment, you will be performing some important data-processing operations, specifically sorting a large database file. Sorting data is a very important operation in computing for many reasons. One of those reasons is that it makes the data more accessible to humans once it is printed (imagine trying to use a telephone directory in which the names do not appear in any particular order). Another reason is that it makes the data more quickly searchable by the computer.
There are many large data files to use for this assignment, but you will only need the first one until you get on to the advanced parts. They are all available on blackboard, and are named people1.txt, people2.txt, people3.txt, people5.txt, people10.txt, people20.txt, people30.txt, people50.txt, and people100.txt.
Look at the file "people1.txt" with a text editor. You will see that it contains data about a number of people. Each line contains exactly five items: a person's social security number, their first name, their last name, their date of birth, and state of residence. The five items are separated by spaces, but no item will ever contain a space. Here is a sample from the middle of thefile:
320990814 Arthur Farmer 19560424 NV
322230050 Eros Crandon 19250819 TX
324640114 Lusitania Lissom 19440104 IN
325400784 Rose Terwilliger 19260122 WI
327640597 Jeffrey Stone 19760801 DE
327950765 Mary Emmett 19290224 CO
328610085 Heironymous Inchworm 19661102 CA
329310410 William McCormick 19550819 WV
329320248 Nicola Birchmore 19230107 IA
330270343 Pauline McTaggart 19290402 MN
331130693 Jim Trombone 19411222 NE
331960453 Abraham Larch 19750901 WY
332040687 Trixie Underwood 19200516 UT
As you may have noticed, the date of birth is provided as a single integer, in the format yyyymmdd; Arthur Farmer was born on the 24th of April 1956. The 1 in the filename people1.txt indicates that it contains exactly one thousand lines.
1. Read the Data
Write a program that creates a list large enough to hold all the data, then reads all the data from the file into that list. Of course, it will have to be a list of structs that you will also need to define. Make your program close the file, then print out the first 10 items of data from the list, so that you can make sure everything was read correctly.
2. Basic Search
Make your program ask the user to enter a name. It should then search through the data in the list (don't read the file again), finding any entry with a matching name. Correct matches with either first or last name should be accepted. For every matching entry that is found, print out all four data items: the social security number, first and last names, and date of birth of each matching person.
Remember that if you use the == operator to compare strings, the test is case-sensitive. The user (i.e. you) will have to type the name exactly correctly, with capital letters in the right places.
Important: Good clean design will make this lab much easier. Write a separate function that searches the list, do not put all the work in main.
3. Find the Oldest
Modify your program so that after closing the file, instead of printing the first ten items of data, it searches through all of them to find the oldest person represented. It should print the social security number, first and last names, date of birth, and state of the oldest person found.
Important: As for part two, good clean design will make this lab much easier. Write a separate function that searches the list to find the oldest person, do not put all the work in main.
4. Promote the Oldest
For some unfathomable reason, the management wants the oldest person to occupy the first position in the list. Modify your program so that after finding the oldest person, it swaps his or her data with the data already occupying the first position in the list. Remember that the first position in a list is numbered zero, not one.
5. Now Promote the Second Oldest.
The management has now decided not only that the oldest person must occupy the first position in the list, but also that the second-oldest person must occupy the second position in the list. So, after searching for the oldest and moving their data to the front of the list, now search the remainder of the list (all except the first element), and move the oldest person you find (which must be the second oldest of all) into the second position of the list. Make sure you swap data, so that whoever was originally in the second position is not lost.
6. More of the Same.
The management are going to keep on adding requirements like this, next putting the third- oldest in the third position, then the fourth, then the fifth. There is no knowing when they will grow out of this petty obsession, so make things easier for yourself. Modify your search function so that it can be told how much of the list to search. That is, give it two int parameters (let's call them a and b); its job is now to search only the portion of the list between position a and position b, to find the oldest person therein. This makes it very easy to search the remainder of the list to find the second and third oldest.
7. The Ultimate Demand.
Now the management make their final demand. You are to repeat the process of moving the nth-oldest person into the nth position 1000 times. (please remember, 1000 is the number of data records in the whole file).
This will result in the list being completely sorted. Do it, and check that it worked. Make your program print the contents of the list after it has finished. Look at the output to make sure that everyone is printed in order of their age.
Try to implement your own selection sort function - instead of using the Python sort.
8. Sorting the File.
Once you have sorted the contents of the list, it might be a good idea to save the sorted data in a file. Make your program create a new file, and write all the contents of the list into that file in a sensible format. Use a text editor to look at the file and verify that it has the same format as the original file, and all the data is properly sorted.
9. How Fast Is It?
It is important to know how long computer operations are going to take when they have to work on a large amount of data.
Use a function (twice) to time how long it takes the computer to sort the list of 1000 data items. Do not include the time it takes to read the file or the time it takes to write the new file, just the pure sorting time. Note the time that you observe.
Now you know how long it takes to sort a database of 1000 items. How long do you think it would take to sort a database of 2000 names? 3000 names? 10,000 names?
Think about those questions, and work out what you believe the answer is. Then find out what the real answer is. The other files have exactly the same format as people1.txt, but are longer. PeopleN.txt contains N thousand data records. If your program was nicely written, it will be a few seconds' work to change the list size and make it read a different file.
See how long it takes to sort these larger files, and compare the results to your predictions. If your predictions weren't substantially correct, make sure you understand
why. You have just demonstrated a very important phenomenon of computing.
10. Friendships
a. Copy your code to a separate program.
b. You will work with the list of persons.
c. Implement or use a function random_in_range(int a, int b) function to choose a random integer number between two integers.
d. Add a friends list for your PersonType class.
e. For each person in the person list choose a number of friends (minimum is zero and maximum is Size/200). Assume this number is x. Now you need to generate x locations of the friends and add them as friends to the list of friends of the current person.
f. Write or use a function that will sort the list now by the number of friends in a descending order.
g. For each person, find other people who have common friends with that person and who those common friends are.
h. For each person, find all the people who have that person as a friend.
i. Repeat part e to randomly unfriend people (unfriending is zero to half of the number of friends).
j. Repeat part f after you have run the unfriend part.
Part II
In this assignment you will use clean structured design to solve a problem that is normally considered to be very difficult, and find that it is in fact surprisingly easy. Look before you leap: think about how your program is going to be organized, don't just start typing. A rational design will give you a working program quite easily; an unplanned design will not. You need to make sure that your program will flow smoothly and your functions are designed with the right parameters and appropriate data types (you should put very little in main().
The assignment is to create a nicely formatted calendar for any month of any year.
1. Length of a Month
Design a function that takes two parameters: year and month, and returns an integer indicating how many days long that month is. January 2009 was 31 days long, February 2009 was 28 days long, February 2008 was 29 days long, and so on. Remember that for February, leap years must be taken into account.
For this first part, we are only interested in the 21st century. Between the years 2000 and 2099 the leap year rule is very simple: a year is a leap year if it is divisible by four.
Incorporate your function into a simple program that allows you to test it conveniently, and then test it conveniently. Each stage of this lab assignment depends on the previous stage, so you won't do any good by going ahead with an incorrect function.
2. Day of the Year.
Design a function that takes three parameters: year, month, and day, and returns an integer indicating which day of the year that date is. For example, the 1st of January is day 1 of the year, the 2nd of January is day 2, the 1st of February is day 32, and so on.
Incorporate your function into a simple program that allows you to test it conveniently, and then test it thoroughly.
3. Day of the Century.
Now make a function that tells you what day of the century it is. Forget about foolish arguments about whether the century starts in 2000 or 2001. If you take 1st January 2000 as day 1, everything works out nicely. So 31st December 2000 was day 366, and 1st January 2001 was day 367, and so on. You still only need to be concerned with this century, 2000 to 2099.
4. Day of Forever.
You knew this part was coming. Now we want a function that again takes three parameters, representing year, month, and day, but this time, the year could be any positive number. This raises two issues: where to start counting (i.e. what date shall we choose to be day number 1?), and how to handle leap years.
Although pedantic folk will argue that there is no such thing as the year 0, pretending that there was makes for a very simple solution. Day 1 will be 1st January of the year 0 regardless of whether or not that date ever existed. It makes the counting easy.
The true rules for leap years are slightly more complex than just divisibility by four. The exact rules are given on the last page if you don't already know them, but in summary:
Any year that is divisible by 400 is a leap year, any other year that is divisible by 100 is not a leap year, any other year that is divisible by 4 is a leap year, and any other year is not a leap year.
Here are some pre-calculated samples to help with testing:
1st January 2000 was day number 730486
4th July 1776 was day number 648857
2nd, 3rd, and 4th of October 2012 are days 735144, 735145, and 735146
27th November 2737 will be the millionth day
1st January of the year 10 A.D. was day 3654
Give some serious thought to testing. If you are getting the wrong number for a date, try some very close dates, and you are likely to spot a pattern in the error that will give you a big clue about where your program may be wrong.
5. Day of the Week.
Now make a function that takes year, month, and day as parameters, and tells you what day of the week that date was. In some strange and wild countries, such as Czechoslovakia, the week starts on a Monday. We'll keep them happy. Make your function return the answer as an int, using 0 for Monday, 1 for Tuesday, ..., and 6 for Sunday. This is very easy if you think of the modulo % operator and remember how many days there are in a week. Also, make it flexible so that you could start the calendar on any day and you could then sell it in any strange and wild countries.
6. A Calendar for a Month.
Use that function in a program that allows the user to enter two integers, representing year and month, and then prints a correctly formatted calendar for that day and month. Like this, which would come from an input of 2014 2:
|
Mo
|
Tu
|
We
|
Th
|
Fr
|
Sa
|
Su
|
|
|
|
|
|
|
1
|
2
|
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
|
17
|
18
|
19
|
20
|
21
|
22
|
23
|
|
24
|
25
|
26
|
27
|
28
|
|
|
continued..
You certainly know how to print out a list of numbers starting from 1. To make those numbers come out looking like a calendar, you need to work out how many spaces to print before the "1", and how to tell when it is time to start a new line. You also need to take a little care to get the alignment of one and two digit numbers right.
7. A solid Product.
Make sure that your calendar works for any year, not just in the 21st Century, And enable the user to print a calendar that starts on any day not just Monday.
8. For A Little Extra Credit.
Write a function that works out how many sundays any given year has.