Difference between revisions of "Problem of the Week"
(→Text/Strings) |
|||
| (11 intermediate revisions by the same user not shown) | |||
| Line 9: | Line 9: | ||
Note that some "classic" programming problems are listed. You should work to solve these on your own, not by simply looking up the solutions online. You learn and improve your skills by making the solutions yourself. | Note that some "classic" programming problems are listed. You should work to solve these on your own, not by simply looking up the solutions online. You learn and improve your skills by making the solutions yourself. | ||
| + | |||
| + | Correct working solutions to some of these problems are in /u1/junk/ProblemOfTheWeek/ on the CS server. If you think you have a problem solved, run yours and the correct working solution on a variety of test cases to make sure your program is giving the correct output. | ||
=Basic Programming= | =Basic Programming= | ||
| Line 21: | Line 23: | ||
'''primes''' 5/20/2020 - read an integer from standard input, output all prime numbers <= that number. | '''primes''' 5/20/2020 - read an integer from standard input, output all prime numbers <= that number. | ||
| + | <pre> | ||
Example input: 19 | Example input: 19 | ||
Example output: 2 3 5 7 11 13 19 | Example output: 2 3 5 7 11 13 19 | ||
| + | </pre> | ||
'''stats''' 5/20/2020 - read an integer n and then n integers from standard input, output the min, max, mean. | '''stats''' 5/20/2020 - read an integer n and then n integers from standard input, output the min, max, mean. | ||
| + | <pre> | ||
Example input: 5 7 3 2 10 -5 | Example input: 5 7 3 2 10 -5 | ||
Example output: -5 10 3.4 | Example output: -5 10 3.4 | ||
| + | </pre> | ||
| + | |||
| + | ==Text/Strings== | ||
| + | '''reverse''' 6/9/2020 - take a string as a command-line argument and print the string in reverse order. | ||
| + | <pre> | ||
| + | Example: ./reverse hello | ||
| + | Output: olleh | ||
| + | </pre> | ||
| + | |||
| + | '''substring''' 6/9/2020 - take two strings as command-line arguments and print yes/no whether the first is a substring of the second (case-sensitive). | ||
| + | <pre> | ||
| + | Example: ./substring hat what | ||
| + | Output: yes | ||
| + | Example: ./substring Hat what | ||
| + | Output: no | ||
| + | </pre> | ||
| + | |||
| + | '''wc''' 6/9/2020 - read from standard input until EOF and output the same as the wc command (number of lines, number of words, number of characters). Note - first get it working for number of characters, then number of lines, and number of words last. | ||
| + | |||
| + | '''lookup''' 6/9/2020 - first command-line argument is a string to lookup, second is a filename for a "dictionary", program outputs whether the string is contained in the dictionary. | ||
| + | <pre> | ||
| + | Example: ./lookup balloon /usr/dict/words | ||
| + | yes | ||
| + | Example: ./lookup balloony /usr/dict/words | ||
| + | no | ||
| + | </pre> | ||
| + | |||
| + | ==Bit Operations== | ||
| + | '''parity''' 6/9/2020 - command-line argument is an integer, print whether it has an even or odd number of 1's in its binary representation. Should work for non-negative integers that are at most 2 billion. | ||
| + | <pre> | ||
| + | Example: ./parity 8 | ||
| + | odd | ||
| + | Example: ./parity 9 | ||
| + | even | ||
| + | Example: ./parity 10 | ||
| + | even | ||
| + | Example: ./parity 11 | ||
| + | odd | ||
| + | </pre> | ||
| + | |||
| + | '''basePrint''' 6/9/2020 - first command-line argument is an integer in decimal, second is one of - binary, octal, hexadecimal. Program should print the integer in either binary, octal, or hexadecimal. Do octal and hexadecimal first as these can be done with built-in print commands. For printing octal, print a "0" first, for hexadecimal print a "0x" first, and for binary print a "b" at the end of the printout. | ||
| + | <pre> | ||
| + | Example: ./basePrint 23 binary | ||
| + | 10111b | ||
| + | Example: ./basePrint 23 octal | ||
| + | 027 | ||
| + | Example: ./basePrint 23 hexadecimal | ||
| + | 0x17 | ||
| + | </pre> | ||
=Data Structures and Algorithms= | =Data Structures and Algorithms= | ||
==Sorting== | ==Sorting== | ||
| − | '''sorts''' 5/20/2020 - first command-line argument is either bubble, insertion, selection. Read from standard input until EOF, output the number of steps to sort the numbers. If second command-line argument is "verbose", also print the numbers in sorted order. | + | '''sorts''' 5/20/2020 - first command-line argument is either bubble, insertion, selection. Read from standard input until EOF, output the number of steps (number of comparisons) to sort the numbers. If second command-line argument is "verbose", also print the numbers in sorted order. As a first attempt, assume there will be exactly 10 numbers and do just one of the sorting algorithms. As a second attempt, assume there will be at most 1000 and add in one of the other sorting algorithms. Finally, make the program work no matter how many numbers there are and for all three sorting algorithms. |
| + | <pre> | ||
| + | Example input (bubble): 1 2 3 4 | ||
| + | Example output: | ||
| + | # steps to sort: 3 | ||
| + | Example input (bubble verbose): 4 3 2 1 | ||
| + | Example output: | ||
| + | # steps to sort: 6 | ||
| + | 1 | ||
| + | 2 | ||
| + | 3 | ||
| + | 4 | ||
| + | </pre> | ||
==Trees== | ==Trees== | ||
| − | '''binaryTree''' 5/20/2020 - read integers from standard input until EOF, output the number of steps to build a binary tree out of the numbers. If second command-line argument is "verbose", also print the tree. | + | '''binaryTree''' 5/20/2020 - read integers from standard input until EOF, output the number of steps (number of comparisons) to build a binary tree out of the numbers. Build the binary tree without rebalancing it. If second command-line argument is "verbose", also print the tree. |
==Lists== | ==Lists== | ||
| − | '''rpn''' 5/20/2020 - evaluate the command line integer arguments as an RPN expression. Note that you will need to keep a stack (linked list) of the values (since this is how RPN is evaluated). | + | '''rpn''' 5/20/2020 - evaluate the command line integer arguments as an RPN expression. Note that you will need to keep a stack (linked list) of the values (since this is how RPN is evaluated). You can keep track of the stack in an array or a linked list. Both are good practice. Note that because * is a wildcard character in the terminal, you will need to type "*" for doing *. |
| − | Example input (command-line args): 1 2 3 * + | + | <pre> |
| + | Example input (command-line args): 1 2 3 "*" + | ||
Example output: 7 | Example output: 7 | ||
Example input: 3 5 7 - / | Example input: 3 5 7 - / | ||
| − | Example output: -1 | + | Example output: -1 |
| + | </pre> | ||
=Data Science= | =Data Science= | ||
Latest revision as of 11:34, 9 June 2020
This page lists the "problems of the week" - extra programming problems meant to help people practice their programming skills.
Contents
About
These will be at a variety of different levels. Some support is provided in the CS Online Lab team in Microsoft Teams. You can go to the team, go to the Problem of the Week channel, and fire away your questions.
Note that many of these problems can be solved in any programming language. The CS Online Lab will support assistance in Python, C, C++, and R. Some problems may be easier to implement in some languages than others.
Problems are listed in "reverse chronological order" within each section/subsection (new problems are added to the top of the section). A date of posting is listed for each problem.
Note that some "classic" programming problems are listed. You should work to solve these on your own, not by simply looking up the solutions online. You learn and improve your skills by making the solutions yourself.
Correct working solutions to some of these problems are in /u1/junk/ProblemOfTheWeek/ on the CS server. If you think you have a problem solved, run yours and the correct working solution on a variety of test cases to make sure your program is giving the correct output.
Basic Programming
Numbers
factor 5/20/2020 - read an integer from standard input (keyboard), output its prime factorization.
Example input: 12 Example output: 2 * 2 * 3 Example input: 5 Example output: 5
primes 5/20/2020 - read an integer from standard input, output all prime numbers <= that number.
Example input: 19 Example output: 2 3 5 7 11 13 19
stats 5/20/2020 - read an integer n and then n integers from standard input, output the min, max, mean.
Example input: 5 7 3 2 10 -5 Example output: -5 10 3.4
Text/Strings
reverse 6/9/2020 - take a string as a command-line argument and print the string in reverse order.
Example: ./reverse hello Output: olleh
substring 6/9/2020 - take two strings as command-line arguments and print yes/no whether the first is a substring of the second (case-sensitive).
Example: ./substring hat what Output: yes Example: ./substring Hat what Output: no
wc 6/9/2020 - read from standard input until EOF and output the same as the wc command (number of lines, number of words, number of characters). Note - first get it working for number of characters, then number of lines, and number of words last.
lookup 6/9/2020 - first command-line argument is a string to lookup, second is a filename for a "dictionary", program outputs whether the string is contained in the dictionary.
Example: ./lookup balloon /usr/dict/words yes Example: ./lookup balloony /usr/dict/words no
Bit Operations
parity 6/9/2020 - command-line argument is an integer, print whether it has an even or odd number of 1's in its binary representation. Should work for non-negative integers that are at most 2 billion.
Example: ./parity 8 odd Example: ./parity 9 even Example: ./parity 10 even Example: ./parity 11 odd
basePrint 6/9/2020 - first command-line argument is an integer in decimal, second is one of - binary, octal, hexadecimal. Program should print the integer in either binary, octal, or hexadecimal. Do octal and hexadecimal first as these can be done with built-in print commands. For printing octal, print a "0" first, for hexadecimal print a "0x" first, and for binary print a "b" at the end of the printout.
Example: ./basePrint 23 binary 10111b Example: ./basePrint 23 octal 027 Example: ./basePrint 23 hexadecimal 0x17
Data Structures and Algorithms
Sorting
sorts 5/20/2020 - first command-line argument is either bubble, insertion, selection. Read from standard input until EOF, output the number of steps (number of comparisons) to sort the numbers. If second command-line argument is "verbose", also print the numbers in sorted order. As a first attempt, assume there will be exactly 10 numbers and do just one of the sorting algorithms. As a second attempt, assume there will be at most 1000 and add in one of the other sorting algorithms. Finally, make the program work no matter how many numbers there are and for all three sorting algorithms.
Example input (bubble): 1 2 3 4 Example output: # steps to sort: 3 Example input (bubble verbose): 4 3 2 1 Example output: # steps to sort: 6 1 2 3 4
Trees
binaryTree 5/20/2020 - read integers from standard input until EOF, output the number of steps (number of comparisons) to build a binary tree out of the numbers. Build the binary tree without rebalancing it. If second command-line argument is "verbose", also print the tree.
Lists
rpn 5/20/2020 - evaluate the command line integer arguments as an RPN expression. Note that you will need to keep a stack (linked list) of the values (since this is how RPN is evaluated). You can keep track of the stack in an array or a linked list. Both are good practice. Note that because * is a wildcard character in the terminal, you will need to type "*" for doing *.
Example input (command-line args): 1 2 3 "*" + Example output: 7 Example input: 3 5 7 - / Example output: -1
