Department of Engineering

IA Programming Club

Michaelmas Term

Level 1

• Write a function that prints the primes less than 100
• Write a function that prints the prime factors of a number less than 100. Write it so that its prototype is void primes(int num)
• Write a function that given 2 integers, prints the lowest common denominator
• Pick a number. If it's even, divide by 2. If it's odd multiply by 3 and add 1. Continue this until you reach 1. E.g. if you start with 3, the sequence will be 3-10-5-16-8-4-2-1. Write a program to find out which integer less than 100 produces the longest chain.
• Write a function that adds 2 vulgar fractions and prints their sum as a vulgar fraction. E.g. its prototype could be void addfractions(int numerator1, int denominator1, int numerator2, int denominator2), so that calling it as addfractions(3,4,5,6) will make it output something like 38/24, or better still 19/12, or even 1 + 7/12
• 12 black mice and 1 white mouse are in a ring. Where should a cat start so that if it eats every 13th mouse the white mouse will be last? Hint - write the program so that it starts at an arbitrary mouse, then see how far out you are and make the necessary correction
• I have 3 cards - an Ace and 2 Jokers. I shuffle them and fan them out in my hand, holding them up so I can see what they are. I invite you to take the card which you think is the Ace, telling you not to look at it. I then put a Joker from my hand face up on the table, and offer you the option of swapping the card you have with the card that's left in my hand. Should you keep your card, exchange, or doesn't it matter?
  Write a program to simulate a 1000 runs of this experiment to see what happens. The RollDie.cc program you used in your first term is a good starting point.
• With C++ you can do just about anything that any other computing languages let you do, though sometimes C++ can't express things so concisely. On the right is a program in a language called Scratch (free for Windows and MacOS). Scratch programs are created by clicking colorful blocks together. Look at this program, try to guess what it does, and then write a C++ program that does the same. C++ doesn't have repeat or forever keywords, but you can replicate the behaviour using for or while constructions
• Suppose you're on the GO square in Monopoly, and someone else has all the hotels along the first side. What's the chance that you'll miss them all? What's the chance that you'll land on as many as possible? Simulate 10,000 runs. Note: the side is 10 squares long, and (counting GO as square 0) there are hotels on squares 1, 3, 6, 8 and 9. Monopoly uses 2 dice.
• The "Ulcers" board-game has a "Business Venture" detour that you go through using 1 die. If you land on the 1st square your initial stake doubles. For subsequent squares the multiplication factors are 3, 0.5, 2, 3, 0.5 and 0. The effects accumulate. For example, if you throw a 1 and then another 1, you're in line to get 6 times your initial stake, but if you then get a 5, you lose everything. Simulate 10,000 runs and count how many different final outcomes there are. What's the chance of losing all your money?
• Here are some questions from the first day's homework assignment of a Stanford C++ course (provided by Andrew Koenig).
  1. Write a program to count the number of words in an input file.
  2. Extend that program to count the number of occurrences of each word
  3. Ensure that the output to problem 2 is sorted by the number of occurrences. That is, print all words that occur once, followed by those that occur twice etc.
  4. Write a program to read a collection of numbers from the standard input and then compute and print their median.
  5. Given a file of student names and exam scores (formatted as described below), compute the student's final grade. The input will be records such as:

         Smith 87 92 93 60 0 98 75 90
         Carpenter 47 90 92 73 100 87 93 91
         ...
     

     (Name, grades on six homework assignments, midterm, final)
     The program should calculate the final grade as a weighted sum: The median homework grade counts 40%, the final 40% and the midterm 20%. So, for the input above, the output would be

         Smith 86.8
         Carpenter 90.4
         ...
     

     NOTE: the decimal points should all line up.

Level 2

Here are some tasks you might like to try if you are confident about computing.

• Vectors - When designing C++ they looked at the features of C that were error-prone. Arrays were considered a weakness and vectors were written to replace them. They're covered in the Deitel and Deitel course book, and they're used in the 1B computing course
  1. What are the weaknesses of arrays? How do vectors overcome them?
  2. Re-write the Michaelmas RollManyDice program so that it uses vectors rather than arrays.
• Transform - for loops were also identified at a source of errors. In the Michaelmas course you used a loop to find the square root of integers from 1 to 10. Change that program so that it uses transform instead of a for loop -
  1. Create a vector of floats containing the integers from 1 to 10
  2. Use the transform algorithm to replace each of the vector's elements by its square root, using your own square-rooting function.