.. _lab-arrays1d:

.. index::
   single: labs; arrays

Lab: Arrays
==================================

- **Notes on GAI**: Note that the course policy is that you should not use generative AI (GAI)
  without authorization. GAI's are great tools and you should learn how to use it, but 
  they are tools and should be used to facilitate but not replace your learning. 
  If you are suspected to have used GAI tools to generate answers 
  to the assignment questions instead of using it as a learning tool, you may be 
  called up to explain/reproduce your work. If you fail to demonstrate your 
  competency, all your **related assignments throughout the semester will be 
  regraded as 0**. For example, if you fail to produce good code in ``while`` loops 
  in midterm exam, your *lab06 while loop homework and labs* will be re-evaluated.  

#. Create a dotnet console app project (see :ref:`create-project` if you need to) in your 
   ``introcscs`` directory (``C:\Users\*USERNAME*\workspace\introcscs`` for Windows or ``COMPUTER:introcscs USERNAME$`` 
   for macOS) ; call it **Ch08ArraysLab**. 
#. Inside the folder, issue the command ``dotnet new console`` to create the project in the folder. 
#. Still inside the project directory, type ``code .`` to start VS Code with the folder as the default folder. 
#. Prepare your code in VS Code using the file Program.cs to code unless otherwise specified.
#. The namespace of this project is *IntroCSCS*. 
#. The class name of this project is *Ch08ArraysLab*. 
#. When executing code, you will only use the Main() method in class *Ch08ArraysLab*. 
#. You will prepare methods in the same class to be called from the Main() method. 
#. Use a Word document to prepare your assignment. 
#. Number the questions and **annotate** your answers (using // when appropriate) to show your understanding. 
#. For coding questions, screenshot and paste 1) your code in VS Code and 2) the 
   results of the code's execution (**command prompt** and **username** are part of the execution).


**Overview**

In this lab, we'll practice working with arrays. Arrays are
fundamental to computer science, especially when it comes to
formulating various *algorithms*. We've already learned a bit about
arrays through the ``string`` data type. In many ways, a **character
string** reveals the secrets of arrays:

- each element of a string is a common **type** (char)
- we can use indexing to find any given character, e.g. ``s[i]`` gives
  us the character at position ``i``.
- we know that the string has a finite length, e.g. ``s.Length``.

So you've already learned these *concepts*. But practice is useful
creating and manipulating arrays with different kinds of data.


**Tasks**

Go to the example file :repsrc:`array_lab_stub/array_lab.cs` and download the file 
(``Download raw file``) and move it to the project folder. Comment out the Main method 
in the default ``Program.cs`` and use the ``array_lab`` file for your tasks. 
Complete the body of a method
for each main part, and call each method in ``Main`` several times with
actual parameters chosen to test it well.  To label your illustrations, make
liberal use of the first method, ``PrintNums``, to display and label inputs 
and outputs.  Where several tests are appropriate for the same method, 
you might want to write a separate testing method that prints 
and labels inputs, passes the data on to the method being tested,
and prints results.

Recall that you can declare an array in two ways::

      int[] myArray1 = new int[10];
      int[] myArray2 = { 7, 7, 3, 5, 5, 5, 1, 2, 1, 2 };

The first declaration creates an array initialized to
all zeroes. The second creates an
array where the elements are taken from the bracketed list of
values. The second will be convenient to set up tests for this lab.

#. Complete and test the method with documentation and heading:

   .. literalinclude:: ../../examples/introcs/array_lab_stub/array_lab.cs
      :start-after: PrintInts chunk
      :end-before: ReadInts chunk

   This will be handy for labeling later tests.  Note that you end
   on the same line, but a later label can start with ``\n`` 
   to advance to the next line.

#. Complete and test the method with documentation and heading:

   .. literalinclude:: ../../examples/introcs/array_lab_stub/array_lab.cs
      :start-after: ReadInts chunk
      :end-before: Minimum chunk

   This will allow user tests.  The earlier input utility methods
   are included at the end of the class.

#. Complete and test the method with documentation and heading:

   .. literalinclude:: ../../examples/introcs/array_lab_stub/array_lab.cs
      :start-after: Minimum chunk
      :end-before: CountEven chunk

#. Complete and test the method with documentation and heading:

   .. literalinclude:: ../../examples/introcs/array_lab_stub/array_lab.cs
      :start-after: CountEven chunk
      :end-before: PairwiseAdd chunk
   
#. Complete and test the method with documentation and heading:

   .. literalinclude:: ../../examples/introcs/array_lab_stub/array_lab.cs
      :start-after: PairwiseAdd chunk
      :end-before: NewPairwiseAdd chunk

   To test this out, you'll need to declare and initialize the arrays
   to be added. You'll *also* need to declare a third array to hold the
   results. Make sure that the arrays all have the same
   dimensionality before proceeding.
   
   This section is a warm-up for the next one.  It is not required
   if you do the next one:

#. Complete and test the method with documentation and heading:

   .. literalinclude:: ../../examples/introcs/array_lab_stub/array_lab.cs
      :start-after: NewPairwiseAdd chunk
      :end-before: IsAscending chunk
      
   See how this is different from the previous part!

#. Complete and test the method with documentation and heading:

   .. literalinclude:: ../../examples/introcs/array_lab_stub/array_lab.cs
      :start-after: IsAscending chunk
      :end-before: PrintAscendingValues chunk

   This has some pitfalls.  You will need more tests that the ones 
   in the documentation!  You can code this with
   a "short-circuit" loop.  What do you need to find to be
   immediately sure you know the answer?
   
#. Complete and test the method with documentation and heading:

   .. literalinclude:: ../../examples/introcs/array_lab_stub/array_lab.cs
      :start-after: PrintAscendingValues chunk
      :end-before: PrintRuns chunk


#. Complete and test the method with documentation and heading:

   .. literalinclude:: ../../examples/introcs/array_lab_stub/array_lab.cs
      :start-after: PrintRuns chunk
      :end-before: PrintRuns chunk

#. Given two arrays, ``a`` and ``b`` that represent vectors. Write a
   method that computes the vector dot product of these two
   floating point arrays. The vector dot product (in mathematics) is defined  
   as the sum of ``a[i] * b[i]`` (for all i). Here's an example of how it
   should work::

      double[] a = new double[] { 1.5, 2.0, 3.0 };
      double[] b = new double[] { 4.0, 2.0, -1.0 };

      double dotProduct = VectorDotProduct(a, b);
      Console.WriteLine("The dot product is {0}", dotProduct);

      // Should calculate 1.5 * 4.0 + 2.0 * 2.0 + 3.0 * -1.0 = 7.0
      
   From here on, create your own headings.
      
.. #. Suppose we have loaded an array with the digits of an integer,
..    where the digit for the highest power of 10 is kept in position 0, 
..    next highest in
..    position 1, and so on. The ones position is always at position
..    array.Length - 1::


..       int[] digits = { 1, 9, 6, 7 };

..    representing :math:`1(10^3)+9(10^2)+6(10^1)+7(10^0)`.

..    Without showing you the code, here is how you would convert a
..    number from its digits to an integer efficiently, without
..    calculating high powers for 10 separately::

..       num = 0
..       num = 10 * 0 + 1 = 1
..       num = 10 * 1 + 9 = 19
..       num = 10 * 19 + 6 = 196
..       num = 10 * 196 + 7 = 1967
..       done!

..    Write a method that converts the array of digits representing
..    a base 10 number to its ``int`` value 
..    (or for really long integers, you are encouraged to use
..    a ``long`` data type). Note that we only allow single digit
..    numbers to be placed
..    in the array, so negative numbers are not addressed.

.. #. Each digit represents a multiple of a *power* of the 
..    *base*.  In the previous version the base is 10, 
..    but other bases are important.  Now make the base a parameter.
..    Here we consider bases no bigger than 10, so we can continue to use
..    only digits for place value symbols.
..    Write a method (or revise the
..    previous solution) to return the int or long represented.
..    For example if {1, 0, 0, 1, 1} represents a base 2 number,
..    :math:`1(2^4)+0(2^3)+0(2^2)+1(2^1)+1(2^0)=19`
..    is returned. Base 2 is central to computer hardware.



.. Modified Parameter Print Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Modify a copy of :repsrc:`print_param/print_param.cs` to contain the earlier
.. example method :ref:`PrintStrings <printstrings>`, and call it.

.. .. index:: exercise; command line adder
..    command line adder exercise
..    Main; parameter exercise
..    parameter; for Main exercise



..    .. _new_upper:

.. NewUpper Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~

.. Complete the definition for

.. .. literalinclude:: ../../examples/introcs/string_array/string_array.cs
..    :start-after: chunk NewUpper
..    :end-before: {
..    :dedent: 6


.. and write a ``Main`` driver to demonstrate it.  Use the example method
.. :ref:`PrintStrings <printstrings>` in your demonstration.


.. .. _all_to_upper:

.. AllToUpper Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Complete the method with this heading:

.. .. literalinclude:: ../../examples/introcs/string_array/string_array.cs
..    :start-after: chunk AllToUpper
..    :end-before: {
..    :dedent: 6


.. Write a ``Main`` method to demonstrate it.  Use the example method
.. :ref:`PrintStrings <printstrings>` to show off your result.


.. Sign Array II Exercise/Example
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Create a variation on :ref:`sign-array-exercise` with a method 
.. with heading

.. .. literalinclude:: ../../examples/introcs/sign_array2/sign_array2.cs
..    :start-after: chunk
..    :end-before: chunk
..    :dedent: 3


.. and a main method to demonstrate it.

.. You can compare your solution with ours in
.. :repsrc:`sign_array2/sign_array2.cs`.



.. Anonymous Array Initialization
.. --------------------------------

.. Sometimes you only want to use an array with specific values 
.. as a parameter to a function.  You could write something like ::

..     int[] temp = {3, 1, 7};
..     SomeFunc(temp);

.. but if ``temp`` is never going to be referenced again, you can 
.. do this without using a name::

..     SomeFunc(new int[] {3, 1, 7});

.. Like with the use of ``var``, the compiler can infer the type of the array, and the
.. last example could be shortened to  ::

..     SomeFunc(new[] {3, 1, 7});

.. It is essential to include the ``new int[]`` or ``new[]``
.. *in addition to*  the ``{3, 1, 7}``.

.. Such an approach could also be used if you want to return a fixed
.. length array, where you have values for each parts, as in::
    
..     int minVal = ...
..     int maxVal = ...
..     // ...
..     return new[] {minVal, maxVal};




.. Testing NewUpper Exercise/Example
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Elaborate :ref:`new_upper` so your ``Main`` method calls
.. ``NewUpper`` with an anonymous array as part of the demonstration. 


.. You can see our code for all the string array exercises in example project
.. :repsrc:`string_array/string_array.cs`, and with the ``Main`` 
.. demonstration method in :repsrc:`string_array/string_array_demo.cs`.







.. Array Examples and Exercises
.. ------------------------------

.. .. index:: index; variable not in loop heading
..    example; remove_zeros.cs
   
.. We have been using array index variables all though this chapter.  
.. We have been getting you started in situations where
.. they all just advanced continually in a 
.. ``for`` loop heading.  The fanciest situations have been where the same index
.. is used to reference more than one array in parallel.

.. Now that you have some experience, 
.. this section will include a variety of exercises where array index
.. variables need to be manipulated in fancier ways.  Consider this heading:

.. .. literalinclude:: ../../examples/introcs/remove_zeros/remove_zeros.cs
..    :start-after: chunk
..    :end-before: {

.. We have a starting array ``data`` and we need to create an ending array, 
.. but the corresponding nonzero data is *not*
.. at corresponding index values in ``data``!

.. Since we are returning a new array, we need to create it, and for that
.. we need a length.  How would you do that by hand?
.. Go through the original array, look at individual elements, and count the nonzero
.. ones.  We can do a counting loop Say we put our count into the variable 
.. ``countNonZero``. Then create a new ``int`` array, say ``notzero``,  with the 
.. proper length.

.. The next part is new.  Clearly we need to get non-zero values from the original array 
.. ``data`` and put them in the other array, ``notzero``.  
.. As we said, the array indices are 
.. not in sync.  That means we are going to need to deal with their indices
.. separately: The index in ``data`` is not going to relate directly to the 
.. index in ``notzero``.

.. We could just have a separate index variable for each array.  
.. Think about ``data``:
.. We do want to go through it sequentially, and we are only *reading* the
.. sequential values, so we can actually use a ``foreach`` loop and not
.. keep track of that index directly at all!  

.. On the other hand we need to assign values *into* ``notzero``, and hence we will
.. need to refer to an index variable for ``notzero``, 
.. say ``i``.

.. However, we cannot just assign the index values in a 
.. ``for`` loop heading as we have been before! 
.. We have to be more careful and think when and how does ``i`` change?

.. This might be a good place to do this by hand, for instance with the sample
.. data in the function documentation.  Keep track of what ``i`` 
.. should be as you iterate through the elements of ``data``, one step at a time:  
.. How do you change
.. ``i`` and when?  You are *encouraged* to stop and actually do this manually,
.. on paper, and think before going on....

.. You should see that:

.. *  We start by being ready to fill the place at index 0 in ``notzero``.
.. *  We only copy a non-zero element of ``data``, so we need an ``if`` 
..    statement in the body again.
.. *  Each such non-zero number
..    is placed after the last number we copied into ``notzero``.
.. *  This means that each time we copy an element to ``notzero`` we advance ``i``!

.. If you get those ideas together, hopefully you can write the needed code.  
.. Our version is:

.. .. literalinclude:: ../../examples/introcs/remove_zeros/remove_zeros.cs
..    :start-after: chunk
..    :end-before: chunk
..    :linenos:
..    :dedent: 6

.. Adding a ``Main`` demostration method, you get our full example
.. :repsrc:`remove_zeros/remove_zeros.cs`.

.. Initialization Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~

.. a.  In the ``NoZeros`` function above,
..     what are the values in the array ``notzero`` just after
..     line 12 is executed?

.. #.  In the :ref:`new_upper`  or our version of ``NewUpper`` in
..     :repsrc:`string_array/string_array_demo.cs`
..     consider the execution of the ``NewUpper`` function 
..     immediately after you first create
..     the string array that you are going to later return.  
..     Right then, what are the element values in that array?


.. .. index:: exercise; ExtractItems
..    ExtractItems exercise
   
.. ExtractItems Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. A string intended to indicate a sequence of items could be like in the 
.. discussion  above of :ref:`IntsFromString1 <ints_from_string1>`.  
.. As illustrated there, individual items
.. are separated out neatly with ``Split``.  If you want to act on a user-generated
.. string, it is probably better to allow more leeway:  
.. Commas are often used to separate items or comma with blank, or several blanks.

.. In this exercise write a version that will accept all those variations
.. and return an array of non-empty strings, without the commas or blanks.
.. Complete this function::

..    /// Return an array of non-empty strings that are separated
..    /// in the original string by any combination of commas and blanks.
..    /// Example:  ExtractItems("  extra  spaces,plus,  more, ") returns an
..    /// array containing {"extra", "spaces", "plus", "more"} 
..    public static string[] ExtractItems(string s)
   
.. Hints: It is possible to deal with more than one separator character, but
.. the simplest thing likely is to use string method ``Replace`` 
.. and just replace all the
.. commas by spaces.  If you then ``Split`` on each space you get all the non-empty
.. strings that you want *and* maybe a number of
.. empty strings.  You need to create a final array with just the nonempty
.. strings from the split.  When you create the array to be returned,
.. you need know its size.  Then populate it
.. with just the nonempty string pieces.
.. Handling the indices for the new array also adds complication.

.. .. _intsfromstring_exercise:

.. IntsFromString Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Write a function
.. ``IntsFromString`` with a corresponding signature and intent
.. like :ref:`IntsFromString1 <ints_from_string1>`, but make it
.. more robust by allowing all the separator combinations of 
.. ``ExtractItems`` from the last exercise, so
.. ``IntsFromString(" 2, 33  4,55 6 77  ")`` returns an array containing ``int``
.. values 2, 33, 4, 55, 6, 77.  (Don't reinvent the wheel: call ``ExtractItems``.)
.. Also write a ``Main`` function so you can demonstrate the use of 
.. ``IntsFromString``.
       
  
    
.. .. index:: exercise; TrimAll for arrays
..    TrimAll exercise

.. .. _trim-all-exercise:
   
.. Trim All Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Write a program ``trimmer.cs`` that includes and tests a 
.. function with heading::

..    // Trim all elements of a and replace them in the array.
..    //  Example: If a contains {" is  ", " it", "trimmed?   "}
..    //  then after the function call the array contains
..    //  {"is", "it", "trimmed?"}.   
..    static void TrimAll(string[] a) 
   
   
.. .. index:: exercise; Dups
..    Dups exercise for arrays

.. .. _Dups-exercise:
   
.. Count Duplicates Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Write a program ``count_dups.cs`` that includes and tests a 
.. function with heading::

.. 	// Return the number of duplicate pairs in an array a.  
.. 	// Example: for elements 2, 5, 1, 5, 2, 5 
.. 	// the return value would be 4 (one pair of 2's three pairs of 5's. 
.. 	public static int dups(int[] a)


.. .. index:: exercise; Mirror
..    Mirror exercise for arrays

.. .. _Mirror-exercise:
   
.. Mirror Array Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Write a program ``make_mirror.cs`` that includes and tests a 
.. function with heading::

.. 	// Create a new array with the elements of a in the opposite order.
.. 	// {"aA", "bB", "cC"} produces a new array {"cC", "bB", "aA"}
.. 	public static string[] Mirror(string[] a)


.. .. index:: exercise; Reverse for arrays
..    Reverse exercise for arrays

.. .. _Reverse-exercise:
   
.. Reverse Array Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Write a program ``reverse_array.cs`` that includes and tests a 
.. function with heading::


.. 	// Reverse the order of array elements
.. 	// If array a first contains "aA", "bB", "cC",
.. 	// than it ends up containing "cC", "bB", "aA".
.. 	public static void Reverse(string[] a)

.. Do this *without* creating a second array.  (There is a
.. trick here.)
   
.. .. index:: exercise; Histogram
..    Histogram exercise

.. .. _Histogram-exercise:
   
.. Histogram Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Write a program ``make_histogram.cs`` that includes and tests a 
.. function with heading::

..     // Return a histogram array counting repetitions of values
..     // start through end in array a.  The count for value start+i
..     // is at index i of the returned array, starting at i == 0.  
..     // For example:
..     // Histogram(new int[]{2, 0, 3, 5, 3, 5}, 2, 5) counts how
..     // many times the numbers 2 through 5, inclusive, occur in
..     // the original array, and returns a new array containing
..     // {1, 2, 0, 2}, that is, 1 2, 2 3's, 0 4's, and 2 5's. The
..     // count of 2's appears as the first (0th) element of the
..     // returned array, the count of 3's as the second, etc.
..     // Similarly, Histogram(new int[]{2, 0, 3, 5, 3, 5}, -1, 1)
..     // returns the new array {0, 1, 0}, 
..     // that is, 0 -1's, 1 0, and 0 1's.
..     public static int[] Histogram(int[] a, int start, int end)

.. This problem clearly requires you to loop through all the elements of 
.. array ``a``.  You should *not* need any further nested loop.

.. .. _Histogram-interval-exercise:
   
.. Histogram Interval Exercise
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. This is a slight elaboration of the previous problem, where
.. you count entries in intervals, not just of width 1. 

.. Write a program ``make_histogram2.cs`` that includes and tests a 
.. function with heading::

..     // Return a histogram array counting repetitions of values
..     // in array a in the n half-open intervals [start, start + width),
..     // [start+width, start+2*width), ... [
..     // [start + (n-1)*width, start + n*width) .  The counts for 
..     // each of the n intervals, in order, goes in the returned array 
..     // of length n.  For example
..     // Histogram(new[]{89, 69, 100, 83, 99, 81}, 60, 10, 5)  
..     // would return an array containing counts 1, 0, 3, 1, 1,
..     // for 1 in sixties, 0 in seventies, 3 in eighties, 1 in nineties,
..     // and 1 in range 100 through 109.
..     public static int[] HistogramIntervals(int[] a, int start, 
..                                            int width, int n)

.. The previous exercise version ``Histogram(a, start, end)`` 
.. would return the same
.. result as ``HistogramIntervals(a, start, 1, end-start+1)``.

.. Again, the only loop needed should be to process each element of ``a``.

.. .. index:: exercise; power table 2

.. .. _power_table_exercise2:

.. Power Table Exercise 2
.. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    
.. Write a program :file:`power_table2.cs`` producing a table much 
.. like :ref:`power_table_exercise`, with right-justified columns,
.. but this time make each separate column have the minimum width
.. necessary - so there is a single space (and no less)
.. in front of some entry in
.. *each* column, except the first.  
.. Be careful: take the heading widths into account; the
.. parameter limits are important, too; test them::

..    /// Print a table of powers of positive integers.  
..    /// Assume 1 <= nMax <= 14, 1 <= powerMax <= 10 
..    /// Example: output of PowerTable(4, 5)
..    /// n^1 n^2 n^3 n^4  n^5 
..    ///   1   1   1   1    1
..    ///   2   4   8  16   32
..    ///   3   9  27  81  243      
..    ///   4  16  64 256 1024
..    public static void PowerTable(int nMax, int powerMax) 






..    .. index:: Shuffle exercise
..    exercise; Shuffle
   
.. Shuffle Exercise
.. ~~~~~~~~~~~~~~~~~

.. Complete the ``Shuffle`` function and add a ``Main`` method to test it::

..     /// Shuffle the elements of an array into random positions, 
..     /// changing the array.  An array containing 
..     /// 2, 5, 7, 7, 7, 9 *might* end up in the order 
..     /// 7, 7, 2, 9, 7, 5.
..     static void Shuffle(int[] a)

.. Use a Random and do something close to a reverse of selection sort, using 
.. ``Exchange`` with a random position.

.. .. index:: sorting; insertion sort
..    algorithms; insertion sort
..    nested loop
..    insertion sort