Simple Programming Problems

 

Elementary Programming Exercises:

Here are some basic programming exercises to get you started:

1. Hello World! - Print "Hello World" to the screen.
2. Greet by Name - Ask the user for their name and display a greeting.
3. Special Greetings (Modification) - Greet only users named Alice or Bob (modifies exercise 2).
4. Sum of Numbers (1 to n) - Find the sum of all numbers from 1 to a user-provided number n.
5. Sum of Multiples (3 or 5) - Calculate the sum of multiples of 3 or 5 up to a user-specified number n.
6. Sum or Product (1 to n) - Allow the user to choose between calculating the sum or product of all numbers from 1 to n.
7. Multiplication Table - Generate a multiplication table for numbers up to 12 (or another chosen number).
8. Prime Numbers - Find and display all prime numbers up to a certain limit.
9. Guessing Game - Play a guessing game where the user tries to guess a secret number.
10. Alternating Series Sum - Calculate the sum of a specific mathematical alternating series.

Lists and Strings Exercises:

These exercises will challenge you to manipulate and analyze data stored in lists and strings:

Basic Operations:

1. Largest Element: Write a function that finds and returns the largest element in a list.
2. Reverse a List: Write a function that reverses the order of elements in a list, ideally modifying the original list (in-place).
3. Element Check: Write a function that determines if a specific element exists within a list.
4. Odd Positions: Write a function that returns a new list containing only the elements at odd positions (1st, 3rd, 5th, etc.) from the original list.
5. Running Total: Write a function that calculates the running sum of all elements in a list, creating a new list with each position representing the sum up to that point.

Strings and Text:

6. Palindrome Check: Write a function that checks if a given string is a palindrome (reads the same backward as forward).
7. Sum of Numbers (3 Approaches): Write three separate functions to calculate the sum of elements in a list, using:
   • a for-loop
   • a while-loop
   • recursion (if supported by your language)

Function Applications:

8. on_all Function: Write a function on_all that applies a provided function to every element in a list. Use this function to print the first twenty perfect squares (numbers obtained by squaring natural numbers).

List Manipulation:

9. Concatenation: Write a function that merges two lists into a single list, preserving the order of elements from both.
10. Alternating Merge: Write a function that combines two lists by taking elements alternately from each, creating a new interleaved list.
11. List Merging: Write a function that efficiently merges two sorted lists into a single new sorted list.

Advanced Exercises:

12. List Rotation: Write a function that rotates a list by a specified number of elements (k), modifying the original list (in-place) if possible.
13. Fibonacci Numbers: Write a function that generates a list containing the first 100 Fibonacci numbers.
14. Digits to List: Write a function that takes a number and returns a list containing its individual digits.
15. Large Number Arithmetic: (Optional) Implement functions for addition, subtraction, and multiplication of two numbers represented as lists of digits. Explore Karatsuba multiplication and the impact of base choice on performance.
16. Base Conversion: Write a function that converts a number represented as a list of digits in one base (b1) to another base (b2).

Sorting and Searching:

17. Sorting Algorithms: Implement various sorting algorithms like selection sort, insertion sort, merge sort, quick sort, and stooge sort.
18. Binary Search: Implement binary search for efficiently finding an element in a sorted list.

Text Formatting:

19. Framed Text: Write a function that takes a list of strings and prints them with a decorative rectangular frame around the entire list.

Bonus Challenge:

20. Pig Latin: Write functions to translate text to Pig Latin (first letter moved to the end with "ay" appended) and back to the original form.

Intermediate Programming Exercises:

These exercises delve into more complex algorithms, data structures, and problem-solving techniques:

Math and Logic:

1. Expression Evaluation: Write a program that finds all possible ways to insert "+" or "-" or nothing between the numbers 1, 2, ..., 9 (in that order) to get a sum of 100.
2. Leap Year Rule: Given a planet's year duration (in fractional days), generate a leap year rule that minimizes the difference between the planet's solar year and the defined leap year cycle.

Data Structures:

3. Modifiable Graph: Implement a data structure for graphs that allows adding, removing, and modifying nodes and edges. Store values at both nodes and edges.
4. DOT Graph Representation: Write a function that generates a DOT language representation of a graph structure, enabling visualization of the graph.

Text Processing:

5. Essay Generator (for Fun): This is a fun (and potentially challenging) exercise. Write a program that attempts to automatically generate essays. Consider the limitations and ethical implications of such a program.
6. Text Graph and Random Walk: Create a directed graph where words from a sample text are nodes, and an edge connects two nodes if the first word is followed by the second in the text (handling multiple occurrences). Implement a random walk algorithm on this graph, starting from a random node and choosing a random successor to traverse.
7. Morse Code Conversion: Write a program that can translate between English text and Morse code.

String Manipulation:

8. Longest Palindrome Substring: Write a program that finds the longest substring within a given string that is a palindrome (reads the same forward and backward). Aim for efficiency in your implementation.

List Implementation:

9. List Interface Design: Define a good interface for a list data structure, considering the common operations you might need for working with lists. Analyze existing list interfaces in popular programming languages for inspiration.
10. Fixed-Size Array List: Implement a list interface using a fixed-size chunk of memory (e.g., an array of 100 elements). Handle potential errors if the user tries to add more elements than the available space.
11. Dynamically Resizable List: Improve your previous implementation to handle an arbitrary number of elements. Allocate larger memory chunks as the list grows, copying old elements and releasing unused memory for efficiency. Consider how much to increase the size of new chunks to avoid constant reallocations.
12. List with Separate Memory Chunks: Optimize the previous implementation by allocating new chunks of memory for newly added items instead of copying everything when the list is full. Design a strategy for bookkeeping to track separate memory allocations.

Advanced Data Structures:

13. Binary Heap Implementations: Implement a binary heap data structure in two ways:
    • Using a list as the underlying data structure.
    • Using a pointer-linked binary tree structure. Utilize the binary heap for implementing heap sort.
14. Binary Search Trees: Implement both unbalanced and balanced binary search trees. Consider an (a,b)-tree as a balanced option.
15. Search Tree Performance Comparison: Compare the performance (insertion, deletion, search) of your unbalanced search tree, balanced search tree, and a sorted list. Analyze the impact of different input sequences on performance. For (a,b)-trees, experiment with different values of a and b.

Algorithm Challenges:

16. Longest Common Subsequence: Given two strings, write a program that efficiently finds the longest common subsequence (a subsequence that appears in both strings without changing the order of elements).
17. Nearest Larger Value: Given an array of numbers, develop a program that efficiently answers queries about the nearest larger value for a number at a specific position (considering the difference in array indices). Preprocess the array in linear time to enable constant-time query responses.
18. String Edit Distance: Given two strings, write a program to find the minimum number of character insertions and deletions required to transform one string into the other.
19. Matrix Multiplication: Implement a function for matrix multiplication, optimizing it for efficiency. Compare its performance to a well-optimized linear algebra library in your chosen language. Explore Strassen's algorithm and the impact of CPU caches. Experiment with different matrix layouts to see performance variations.
20. van Emde Boas Tree: Implement a van Emde Boas tree data structure and compare its performance with your previous search tree implementations.

Volume of Union: This exercise involves calculating the volume of the union of a set of d-dimensional rectangular boxes (start with 2D and progress to higher dimensions).

Open Ended Programming Challenges:

These exercises push you beyond standard algorithms and data structures, encouraging creative problem-solving and exploration of advanced techniques.

Playing Games:

1. Intelligent Hangman: Develop a Hangman program that plays strategically.
   • Leverage a large dictionary to choose letters that eliminate the most potential words.
   • Optimize efficiency by avoiding full dictionary scans in every turn. You can explore data structures like tries for efficient word representation and exclusion.
2. Rock-Paper-Scissors Mastery: Write a program that surpasses random play in Rock-Paper-Scissors against a human opponent.
   • Exploit human biases in generating "random" choices. Analyze patterns in human behavior and use them to gain an advantage.
   • Consider using probabilistic decision-making to account for uncertainty.
3. Battleship AI: Create a program that plays Battleship against human opponents.
   • Allow for human input of coordinates to indicate hits or misses.
   • Develop an AI strategy to strategically place ships and make informed guesses for attacking. Consider using a probabilistic approach to account for uncertainty in ship locations.

These challenges encourage you to:

• Think strategically: Consider opponent behavior, resource management, and decision-making under uncertainty.
• Explore advanced techniques: Investigate data structures like tries for efficient word handling in Hangman, or probabilistic algorithms for decision-making.
• Optimize for efficiency: Minimize unnecessary calculations and data scans to enhance gameplay responsiveness.

Remember:

• Balance between challenge and fun: Strive for a program that provides a challenging but enjoyable experience for the human player.
• Ethical considerations: Ensure fair play in Rock-Paper-Scissors by avoiding exploiting human weaknesses in a manipulative way.