Supplemental Problems for
Java, C++, and Assembler
OVERVIEW
Here are a collection of problems, most of which right now are well within your grasp of problem solving and programming -- given your current amount of experience and background. A few may require techniques that we've yet to discuss in class – but, be assured, we will cover all the tools you need to solve all of these problems well before the end of the semester.
Most of these problems are appropriate for solution in any language (Java, C++, Assembler, C, Pascal, Fortran, Basic, whatever…) Some of the problems are particularly appropriate for solution using Assembler. I've marked those with "(Asm)" at the end of the problem description. In the case of Assembler, use the standard conventions for the registers in which input arguments are passed and output values are returned. You'll need to build a short "driver" routine for all these problems (no matter what the language) that allows you to provide inputs and capture outputs. For some problems, you should consider whether you want to print the results, or to create a list or table (an array) in which to pass back the results.
My recommendation is to look over all these problems… Think about how you might attack each one… What data structures and control structures are required? What algorithms would need to be developed? Identify the objects. Identify the relationships among the objects. Then, for those that "catch your fancy," go ahead and develop a running solution. I'll be happy to provide consulting help, advice, suggestions, corrections, etc., before or after class, during office hours and via email.
There is no "extra credit" for doing any of these problems. Nor can any of these problems be substituted for problems that already are assigned in the course. These problems are for your use – the knowledge and experience that you gain in thinking about their solutions, and in actually constructing running programs are your "rewards" for working on them.
Lastly, remember that every textbook on programming (ours included) contain numerous problems and exercises that you might consider working on. Consider all of them added to this list…
For each problem, you should create:
1. Structure Chart / Outline for your program
2. Structured Flowchart for your program
3. Pseudocode for your program
4. Listing of your program
5. Listing of your data
6. Listing of the outputs from running your program
1. Build a program that tells whether it's legal to hold a meeting or not. Read in the maximum room capacity and the number of people who want to attend the meeting. If there are fewer people than the capacity, announce that the meeting can be held as planned. If not, then tell how many people must be excluded in order to comply with the fire marshal's regulations. Test your program using several capacities and about twice as many planned attendees. (I.e., your program should include a loop. What will you use as the end-of-data sentinel?)
2. Build a program that converts normal decimal numbers into Roman numerals. (1 = I, 2 = II, 3 = III, 4 = IV, 5 = V, 6 = VI, 10 = X, 50 = L, 100 = C, 500 = D, 1000 = M.)
3. Build a program that converts the Roman numeral representation of a number back into decimal.
4. Build a program that reads in a series of English words… Its job is to check the "I before E except after C" spelling rule… It should output the original series of words, with corrections made. It should keep track of how many times the author made a mistake and should report this number at the conclusion of the program. (Asm)
5. You go to the local burger joint and order a burger, fries and a drink. You pay for your meal with a $5 bill. The total cost of your meal is $X (X is in dollars and cents – i.e., it's a float). Build a program that the cashier can use to help him/her give you your change. The program should tell the cashier how many half-dollars, quarters, dimes, nickels, and pennies (s)he should give you. Consider how to modify your program so that it could accept payments of $10, $20, $50, $100… and, of course, it should give you change in terms of the appropriate bills as well as coins.
6. Build a program that REMOVES all the indentation from a program. It should read in lines (or characters) and echo the lines with all leading whitespace removed. Try running your program using any of your programs as input. The resulting, much more unreadable, output will show you how programs used to look before more "enlightened" indentation style became common. (Asm)
7. Modify your program so that instead of producing a less readable, whitespace removed, version of its input, change it so that it "prettyprints" its output. Step 1: Remove leading whitespace, Step 2: Insert whitespace corresponding to the "level" of indentation… You'll have to increase the amount of "indentation" each time you see a left brace; decrease the amount of "indentation" each time you see a right brace.
8. Build a program that counts the number of times that the word "the" appears in a passage of text. While you're at it, tell how many words are in the passage as well. Note that "the" should not be counted as a word if your program sees "their" or "other."
9. The DeMorgan Theorems say that ! (X || Y) == !X && !Y and that ! (X && Y) == !X || !Y, where X and Y are both Boolean-valued variables. Build a program that runs X and Y over the range FALSE..TRUE, calculate the values of each of the four expressions, and have your program tell you about whether or not it ever finds an exception to the DeMorgan Theorems. (Asm)
10. Julius Caesar invented a cypher (a coding scheme) that has been named after him. In the Caesar cypher, you replace each letter of the alphabet by the one that is just "one letter higher than the original." Thus 'a' -> 'b', 'b' -> 'c', 'c' -> 'd', … 'y' -> 'z', 'z' -> 'a'. Letters that aren't alphabetic remain unchanged (so, punctuation remains unchanged, digits remain unchanged, whitespace remains unchanged). Write a program that reads a passage in "clear text" and outputs it's Caesar-cypher encoded equivalent. Then write a program that decodes a Caesar-cypher encoded message. Check to see that both programs work by running the Decoder on the output of the Encoder. (Asm)
11. For many programs, it's handy to have a routine that accepts a "title" (a character string), a "table" (an array), and a length (an integer, telling how many values are in the table). The program displays the title, and then displays the entries in the table in a nicely laid-out format, with sequential numbers from 1 to N on the left and the values on the right. Build this routine. (Asm)
12. A concordance is a list of words and the frequencies with which they occur in a text passage. Write a program that accepts a text passage and outputs a concordance. (Asm)
13. Remember those childhood "Learning to read books"? – the ones that contained: "See Bob run. Run Bob run. See Jane run. Run Jane run. Bob and Jane run…" Build a program that outputs "Jane" each time its reads a "1"; "Bob" each time it reads a "2"; "See" for "3"; "run" for "4"; "and" is "5". Add a couple more words of your choosing. Then build a program that reads in a sequence of numbers and prints the resulting sentence. Make your program loop until it sees a number <= zero. Can you change your program so that it outputs all possible simple sentences?
14. Normally, you see large numbers written with a comma between every group of three digits… For example: 32,767 or -12,345,678.765,432 Write a program that inputs an integer and outputs a string that contains the comma-enhanced equivalent value. Modify your program so that it can handle floats or doubles. How do you plan to limit the number of digits displayed to the right of the decimal point? (Asm)
15. Build a program OrderChars that accepts three lower-case letters of the alphabet. It must modify its arguments (i.e., use inout parameters) so that the letters are in descending alphabetic order after the call to OrderChars.
16. Build a program that tells whether or not a string is a palindrome. A palindrome is an object that is identical to its mirror image. That is to say, it reads the same front-to-back as it does from back-to-front. A string is a collection of letters. For example, these are palindromic: a, ada, pop, toot, poop, madam. Note that palindromic strings don't have to be real English words… abcdefedcba is a fine palindrome. (Asm)
17. Build a program called Swap that accepts two double inout arguments. It should interchange their values so that they're changed in the calling function's memory space. (Asm)
18. Build a program called Shift that accepts four float inout arguments, fA, fB, fC, fD. Shift should change these values so that fA now has the value of fB, fB has the value of fC, fC has the value of fD, and fD has the value of fA. In other words, the values have all "been shifted to the left."
19. Build a program called Duplicates that accepts four char input arguments, and one char output argument. If any two of the four input characters are duplicates of one-another, then the output argument is to be set to that character. If all four input characters are distinct, then the output character is to be set to NUL (the character, '\0'). If there are more than one pair of duplicates, or if three (or four) of the characters are all the same, just return the first matching pair you find.
20. Build a program that accepts a single letter of the alphabet, in upper- or lower-case. Your program must return the first vowel that is "less than or equal to" than the input letter. Your program must "preserve case" – so that it returns 'E' if the input is 'G', and returns 'u' if the input is 'z'. (Asm)
21. You and your buddy take two rubber balls to the top of the Empire State Building in New York City. The first ball is pretty "bouncy," so each time it hits the ground it rebounds to 95% of its original height. The second ball isn't so "bouncy" – it only rebounds to 75% of its original height when it bounces… Assume that no matter how high the balls bounce, it ALWAYS takes EXACTLY one second for either ball to fall, bounce, and rebound. You drop the "bouncy" ball at exactly 1:00:00 PM. Your buddy drops the less "less bouncy" ball at exactly 1:00:04 PM. (In other words, 4 seconds later). Build a program that finds out how close the balls are at the top of each bounce. What is the closest they get at the top of the first 10 bounces? Assume that the Empire State Building is 2,000 feet tall. Stop your experiment when both balls bounce no higher than one foot.
22. Build a predicate (a Boolean-valued function) that accepts a year. Its value is TRUE if the year is a leap year and is FALSE otherwise. A leap year is one that is evenly divisible by four, except for centuries – which are usually not, unless they are also evenly divisible by 400. So, 1996 is a leap year, 1900 is not a leap year, and 2000 is a leap year.
23. Build a function that accepts a month and a day (as two integers in the ranges 1-12 and 1-31, respectively) and it returns the corresponding Julian day. The Julian day is the number of days past the start of a year. So, Jan 1 is Julian day 1, Jan 31 is Julian day 31, Feb 1 is Julian day 32, Feb 2 is Julian day 33, the last day of a year is Julian day 365, except in leap-years when it's Julian day 366.
24. Build a predicate (a Boolean-valued function) that accepts two month-day pairs (as pairs of integers in the ranges 1-12 and 1-31, respectively) that is TRUE if the first month-day combination is later in the year than the first month-day combination. So, 5-20 is later than 5-15, 5-20 is later than 2-3, 5-20 is later than 1-31, and 12-31 is later than every other day in the year except December 31st.
25. Extend the previous problem to allow for months, days, hours and minutes. How are you going to represent times after noon? You may use a 24-hour clock if you wish.
26. Build a function that accepts a time in normal notation, like 5:36 PM, and converts it into its 24-hour equivalent: 17:36. Build the reverse function as well – accepting 24-hour times and converting them into normal HH:MM A/PM notation. Extend your solution to handle seconds as well.
27. Build a program that reads in a collection of integers in the range 0-50 and PLOTS them using "stars." It should produce a "histogram" that looks roughly like this:
3 | ***
10 | **********
2 | **
7 | *******
Use data of your own choosing; but use at least 15 values. Be certain that you test your program on both zero and 50. Use –1 as a sentinel.
28. Build a function that tells the winner of the paper-rock-scissors game. Paper covers rock; rock breaks scissors; scissors cuts paper. Your function should accept the choices made by two players, and it should return the winner – or Nobody, in case the two players make the same selection.
29. In chess, the Queen can move and attack in any of 3 directions: horizontally, vertically, diagonally. Write a program that places 8 Queens on a normal 8 x 8 chessboard such that no Queen attacks another and no Queen is under attack.
30. Generalize the previous problem so that you can use a chessboard of size N x N, where N is read in, of course.
31. The Rook attacks quite differently than does a Queen. How many rooks can be placed onto a chessboard so that no rook attacks any other and no rook is under attack? How many different such solutions are there?
32. Build a program that sets up enumerations for SUITS and FACE_VALUES for a standard card deck. Then, set up a POKER_HAND as a collection of 5 CARDs. Build a driver than randomly loads the "hand" with cards… and then tells you "what's in the hand." Use standard poker rules: "nothing," 1-pair, 2-pairs, 3-of-a-kind, straight, flush, full-house, royal-flush, etc…
33. Build a program that finds the "value" of a bridge hand. Use the conventional bridge scoring values.
34. Build a program that plays Tic-Tac-Toe with the user. Make certain that it is "smart" enough so that it never loses a game.
35. Build a program that takes a deck of 52 cards (conventional playing cards) and it shuffles the deck. Then it deals the cards and displays the N hands that are dealt.
36. Using your solution to the previous problem, build a program that plays Hearts, Blackjack or Poker with the user.
37. Build a program that sets up a 2-dimensional array of size 100 x 100… "Seed" the array with a few "animals." The propagation rules for animals are: animals that are alone (have no immediately adjacent animals) die. Animals that are overcrowded (have 4 or more immediately adjacent animals) die. Animals that have exactly 1 neighbor propagate by generating either 1 or 2 offspring at random locations adjacent to the "parents." Now, given your initial array containing animals, determine what the locations of all the animals in the next instant of time will be. Do this again and again, seeing if your animal population dies out, lives "forever," is static, cyclic, or in motion. (This is a simplified version of Conway's game of "Life.")
38. A long can only hold about 10 digits of precision… What if you want to calculate something that needs 50 digits of precision? Build a program that represents a BIG_NUM as an array of integers, 50 elements in length. Construct routines that are able to input and output BIG_NUMs. Now, build routines that are able to add, subtract, multiply, divide and compare BIG_NUMs. This collection of routines is called a "multiple precision arithmetic package."
39. Define a C++ macro, called TELLME. TELLME should accept a pair of arguments. The first argument is the value that you'd like to see displayed. The second argument is a "condition" that must be true in order for TELLME to produce any output – it's a "debug control expression." TELLME should produce output that looks roughly like this; >>>>> The value of nBoys is 34 <<<<< assuming that the control expression was true and that nBoys is the variable whose value you wanted to see displayed. TELLME might be very valuable to you in debugging other programs… Hint…
40. Build a finite state machine for the elevator controls for some building with which you are acquainted… Test your program by sending it random requests for floors.
41. You are at the Bay Bridge in downtown San Francisco, on the freeway. You need to find a way to San Jose. Build a model of the freeways that connect your current location to San Jose. Now, write a program that finds a path from the Bay Bridge to San Jose. Finds all paths. Finds the shortest path. Finds a path that doesn't drive by the SF International Airport.
42. Build a predicate called IsDigit. It returns true if the character it is given is an ASCII digit, and returns false otherwise. (Asm)
43. Build a function called ToLower that accepts a single character. It returns the lower-case version of the input character. Non-characters are returned unchanged. (Asm)
44. Build a function called LowerCase that accepts a NUL-terminated character string. It changes all upper-case characters in the input string into lower-case equivalents. Non-letters are left unchanged. The original string is modified. (Asm)
45. Construct a function called strcmp that functions like the Java/C++/C string function of the same name: It accepts two NUL-terminated character strings. Strcmp returns -1 if the first string is less than the second, 0 if the two strings are identical, and +1 if the first string is greater than the second. (Asm)
46. Build a function that finds the largest number in a table of numbers. (Asm)
47. Build a function that determines whether any number is duplicated (appears more than once) in a table. Return the number that is duplicated and the number of times it appears. If more than one number is duplicated, then return the number that is duplicated the greatest number of times (and the number of times it is duplicated). (Asm)
48. Build a function that sorts a table of numbers into ascending order using any standard sorting algorithm. (Asm)
49. The multiplication operator in your compiler fails to function properly. Build a program called: int Multiply (int nX, int nY). Its job is to multiply nX by nY and return the product. You may NOT use the "*" symbol anywhere in your program (except, perhaps, as part of a comment).
50. This time, it's the division operator in your compiler that's broken. Build a program called: int Divide (int nX, int nY). Its job is to divide nX by nY and return the quotient, ignoring any remainder. You may NOT use the "/" symbol anywhere in your program (except a part of a comment). How are you going to handle the case of nY = 0?
51. Build a program that converts normal decimal (base 10) numbers into binary (base 2) numbers. For example, 0 = 0, 1 = 1, 2 = 10, 3 = 11, 4 = 100, 5 = 101, 6 = 110, 7 = 111, 8 = 1000, etc. (Asm)
52. Build a program that converts binary numbers back into normal decimal numbers. (Asm)
53. Build a program that converts decimal numbers into base N numbers, where you read in the value of N. Try your program with N = 2, N = 8, N = 16, N = 50. Then, modify your program so that it converts base N numbers into base K numbers, where you read in the values of N and K. (Asm)
54. Build a function called Isqrt that calculates the integer square root of its input argument (an integer). The integer square root is the largest integer, r, such that r2 <= n (the input argument). For example, 4 = Isqrt(16), 0 = Isqrt(0), 5 = Isqrt(30), 6 = Isqrt(37), 10 = Isqrt(100), etc. Decide how to handle negative inputs. (Asm)
55. An integer vector is a list < a, b, c,… > where each of the a, b, c,… are integers. The magnitude of a vector || v ||, is the value: Isqrt (a2 + b2 + c2 + …). Build a function that accepts an integer vector and returns its magnitude. (Asm)
56. Pythagorean Triples are triples of integers – x, y, z – that satisfy the equation: x2 + y2 = z2. Every "right triangle" from geometry satisfies this equation. For example, 32 + 42 = 52 . Find all the Pythagorean Triples (i.e., find all the right triangles) for x,y,z all in the range 1..N. Read in N. (Asm)
57. Build a program that determines whether a number is perfect, abundant or deficient. A perfect number is one whose value is equal to the sum of all of its divisors. For example, 6 is perfect, because 6 = 1 + 2 + 3, (1, 2, 3 are the divisors of 6). If a number is less than the sum of all its divisors, it is said to be deficient. If it is larger than the sum of all its divisors it's said to be abundant. Make a table of numbers in the range 1..N, telling for each number, whether it is perfect, abundant or deficient. Read in N, of course. (Asm)
58. Build a program that can calculate the result of raising X to the Y'th power: XY. You may NOT use any routines from the math library (like exp or log). Assume that X and Y are both integers > 0. Build another program that allows X to be a float or a double.
59. Build a program that tells whether or not an integer is a palindrome. A palindrome is an object that is identical to its mirror image. That is to say, it reads the same front-to-back as it does from back-to-front. For example, these are palindromic: 1, 22, 393, 4774, 27372, 12344321. Could you use your palindrome detector to find all the palindromic integers between 1 and N? Read in N. (Asm)
60. Do you remember the definition of Complex numbers? Build a class that implements Complex numbers. Be certain to include functions that allow Complex numbers to be: input, output, added, subtracted, multiplied, divided, find the magnitude.
61. A prime number is a natural number that has no divisors other than one and itself. Examples of primes include 2, 3, 5, 7, 11, 13, etc. Non-primes are called composite numbers. Build a program that is able to display all the prime numbers between 2 and N. (Asm)
62. A composite number is one that has factors other than one and itself. Build a program that accepts a number and displays the word "Prime" if it is a prime number, but shows ALL its factors if the number is composite. The number 12, for example, has the following factors: 2, 3, 4, 6. (Asm)
63. Instead of displaying all the factors, as in the problem just above, only display the prime factors if the input number is composite. (Asm)
64. Sometimes, primes occur as "prime pairs" -- two primes whose difference is 2. For example, 3 and 5, 11 and 13, etc. How many prime pairs are there less than N? (Asm)
65. Find a way to approximate the value of Pi… Calculate Pi to 100 digits. Let the user type in the number of digits to which your program should calculate.
66. In calculus you learned about Newton's Method for determining the root of an equation. Build a program that uses Newton's Method to find the cube root of 3. Check your result (of course) by cubing it and seeing how close to 3.0 it is.
- o -- O -- o -
File: SupplementalProblems.htm Last updated: Feb. 27, 2006