Programming Fundamentals/Practice: Arrays

Chapter Summary

• Arrays and Lists - Data structures consisting of collections of elements (values or variables).
• Index Notation - Typically indicated by brackets [] or parenthesis (), index notation is used to identify the location or numeric value of an element of an array.
• Displaying Array Members - To display all array members, get the value of each element using a for loop and output the element using index notation and the loop control variable.
• Arrays and Functions - Array processing functions are usually passed with the array and any data necessary to process the array for the given task.
• Math Statistics with Arrays - Statistics is a branch of mathematics dealing with the collection, organization, analysis, interpretation, and presentation of data. Arrays can store words, letters/characters (strings) and numbers (integers/floats), therefor the arrays and statistics go hand in hand.
• Searching Arrays - Linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
• Sorting Arrays - A sorting algorithm is an algorithm that puts elements of a list in a certain order.
• Parallel Arrays - A group of parallel arrays is a form of implicit data structure that uses multiple arrays to represent a singular array of records.
• Multidimensional Arrays - The number of indices needed to specify an element is called the dimension or dimensionality of the array.
• Dynamic Arrays - A dynamic array is random access, a variable-size list data structure that allows elements to be added or removed.

Review Questions

True / False

1. The array data type is one of the standard data types in C++.
2. Arrays can have more than one dimension.
3. For loops are often used to display the members of an array.
4. When defining an array, it is preferable to specify how many members are in the array.
5. Arrays are rarely used to represent data.
6. Linear searches require complex algorithms.
7. Functions are often created for searching for the max and min values in an array.
8. The bubble sort is an easy way to arrange data an array.
9. There is only one method of bubble sorting.
10. Sorting an array is frequently done.
11. A single-dimensional array is also called a table.
12. Array members are referenced starting with one.
13. If you don't know how many elements are going to go in a certain array, you should create a static array.
14. It is better to use a list if you want to perform arithmetic functions on the data elements as opposed to a traditional array.
15. it is impossible for an array to have an empty value in the middle of the array.
16. You can subtract values from an array.

Answers:

1. false
2. true
3. true
4. false
5. false
6. false
7. true
8. true
9. false
10. true
11. false - A single-dimensional array is known as a list.
12. false - Some programming languages may start at one, but for others, such as Python, the array members start at 0.
13. false
14. false
15. false - A dynamic array can have empty values, where elements can be added or removed.
16. true

Short Answer

1. Briefly explain what an array is and list the two common operators used with arrays.
2. Give a short explanation of bubble sorting.
3. Explain the difference between array push and array pop.
4. Describe the difference between a static array and a dynamic array. Also, include why you would choose one instead of the other.
5. Briefly explain the differences between a variable and an array.
6. explain why sorting arrays is used so often.

Activities

Complete the following activities using pseudocode, a flowcharting tool, or your selected programming language. Use separate functions for input, each type of processing, and output. Avoid global variables by passing parameters and returning results. Create test data to validate the accuracy of each program. Add comments at the top of the program and include references to any resources used.

Defined-Value Arrays

1. Review MathsIsFun: Leap Years. Create a program with a defined array where each entry is the number of days in the corresponding month (January = 31, February = 28 or 29 depending on year, March = 31, etc.). Build a parallel string array with the names of each month. Ask the user to enter a year and month number and then look up the corresponding month name and number of days and display the information. Continue accepting input until the user enters an invalid year or invalid month number.
2. Review Wikipedia: Zeller’s congruence. Create a program that asks the user for their birthday (year, month, and day) and then calculates and displays the day of the week on which they were born. Use an array lookup to convert the numeric day of the week to the correct string representation (Monday, Tuesday, Wednesday, etc.).

Fixed-Length Arrays

1. Review MathsIsFun: Definition of Average. Create a program that asks the user to enter grade scores. Start by asking the user how many scores they would like to enter. Then use a loop to request each score and add it to a static (fixed-size) array. After the scores are entered, calculate and display the high, low, and average for the entered scores.
2. Review Wikipedia: Monty Hall problem. Create a program that uses an array to simulate the three doors. Use 0 (zero) to indicate goats and 1 (one) to indicate the car. Clear each “door” and then use a random number function to put the number 1 in one of the array elements. Then use the random number function to randomly select one of the three elements. Run the simulation in a loop 100 times to confirm a 1/3 chance of winning. Then run the simulation again, this time switching the selection after a 0 (goat) is removed from the remaining choices. Run the simulation in a loop 100 times to confirm a 2/3 chance of winning by switching.
3. If your programming language supports it, use a built-in sort function to sort the grade scores from the activity above and display the array in order from highest score to lowest score.

Dynamic Arrays / Lists

1. If your programming language supports it, update the grade score program above to replace the static array with a dynamic array, and extend the array as each item is added to the array. Continue accepting scores until the user enters a negative value.
2. Review Khan Academy: A guessing game. Write a program that allows the user to think of a number between 0 and 100, inclusive. Then have the program try to guess their number. Start at the midpoint (50) and ask the user if their number is (h)igher, (l)ower, or (e)qual to the guess. If they indicate lower, guess the new midpoint (25). If they indicate higher, guess the new midpoint (75). Record each guess in an an array and continue efficiently guessing higher or lower until they indicate equal, then display the list of guesses required to guess their number and end the program.
3. If your programming language supports it, use a built-in sort function to sort the grade scores from the activity above and display the array in order from highest score to lowest score.

References

• cnx.org: Programming Fundamentals – A Modular Structured Approach using C++
• Wikiversity: Computer Programming

Programming Fundamentals