Intermediate Exercises

Simple exercises from adriann.github.io/programming_problems.html (CC-BY-SA)

1. Write a program that outputs all possibilities to put + or - or nothing between the numbers 1,2,…,9 (in this order) such that the result is 100. For example 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100. ✔️
2. Write a program that takes the duration of a year (in fractional days) for an imaginary planet as an input and produces a leap-year rule that minimizes the difference to the planet’s solar year. ✔️
3. Implement a data structure for graphs that allows modification (insertion, deletion). It should be possible to store values at edges and nodes. It might be easiest to use a dictionary of (node, edgelist) to do this. ✔️
4. Write a function that generates a DOT representation of a graph. ✔️
5. Write a program that automatically generates essays for you. ✔️ 5.1. Using a sample text, create a directed (multi-)graph where the words of a text are nodes and there is a directed edge between u and v if u is followed by v in your sample text. Multiple occurrences lead to multiple edges.✔️ (part of 5) 5.2. Do a random walk on this graph: Starting from an arbitrary node choose a random successor. If no successor exists, choose another random node.✔️ (part of 5)
6. (numbers 6 and 7 skipped)
7. Write a program that automatically converts English text to Morse code and vice versa. ✔️
8. Write a program that finds the longest palindromic substring of a given string. Try to be as efficient as possible! ✔️
9. Think of a good interface for a list. What operations do you typically need? You might want to investigate the list interface in your language and in some other popular languages for inspiration. ✔️
10. Implement your list interface using a fixed chunk of memory, say an array of size 100. If the user wants to add more stuff to your list than fits in your memory you should produce some kind of error, for example you can throw an exception if your language supports that. ✔️
11. Improve your previous implementation such that an arbitrary number of elements can be stored in your list. You can for example allocate bigger and bigger chunks of memory as your list grows, copy the old elements over and release the old storage. You should probably also release this memory eventually if your list shrinks enough not to need it anymore. Think about how much bigger the new chunk of memory should be so that your performance won’t be killed by allocations. Increasing the size by 1 element for example is a bad idea. ✔️
12. If you chose your growth right in the previous problem, you typically won’t allocate very often. However, adding to a big list sometimes consumes considerable time. That might be problematic in some applications. Instead try allocating new chunks of memory for new items. So when your list is full and the user wants to add something, allocate a new chunk of 100 elements instead of copying all elements over to a new large chunk. Think about where to do the book-keeping about which chunks you have. Different book keeping strategies can quite dramatically change the performance characteristics of your list. ❌ (not sure if I skipped this on purpose?)
13. Implement a binary heap. Once using a list as the base data structure and once by implementing a pointer-linked binary tree. Use it for implementing heap-sort. 🚧
14. Implement an unbalanced binary search tree. ❌
15. Implement a balanced binary search tree of your choice. I like (a,b)-trees best. ❌
16. Compare the performance of insertion, deletion and search on your unbalanced search tree with your balanced search tree and a sorted list. Think about good input sequences. If you implemented an (a,b)-tree, think about good values of a and b. ❌