The following are hidden (display:none)

List exercises

1. read a bunch of values from <>, sort them, repeatedly find them (using BinarySearch)
2. Redo some exercises from BIT 142's 'arrays' section
   1. Using only part of the array (Hand-In)  - create array, put <= 10 positive integers into array (negative numbers mean 'exit')
   2. Returning an array (Hand-In) PrintArray, and CreateRandomlyFilledArray
   3. Sieve of Erastothenes?

Linked List Exercises

1. Game: SumUp: LL of numbers need to sum up to a particular, target number.  Allowed operations: add two, adjacent numbers, split an even number into two equal parts, multiply two adjacent number together (replacing them both with the result), divide the first number by the second (replacing both with the result)
   SumUp to 3
   1 1 3 2
   1 +1, then 2 * 3, then 6/2
   
   SumUp to 3
   2 3 1 1
   1 +1, then 2 * 3, then 6/2
   
   SumUp to 3
   2 3 1 1
   1 +1, then 2 * 3, then 6/2
2. BubbleSort the list?
3. Clone the list?

 

Utilizing data structures that other people have built

STUFF TO ADD:

• foreach loops
• Make sure we can retro-slot these into prior lessons ok

---

 

• Outcomes
  • Know how to choose a good class
  • Know how to learn the parts of the API you need
  • Memorize the commonly used parts (like ‘Add’ and ‘Remove’, etc, for List<>)
    • Be clear: students need to know what these things should do
      AND
    • need to know how to use it in a program (i.e., make sure you're able to write an individual line of code that uses this to do something)

• Topics (in Collections.Generic)
  • Foreach topic
    • overview
    • warmup code
    • solve a small example with it
    • Methods to memorize
    • compare & contrast: why was this a good alg. to use to solve this problem? Why were the prior topics not good fit for this current problem? & vice versa
    • MUST USE BIG OH NOTATION IN ESSAY

    • Look for pictures/diagrams to illustrate the data structure

      • 10 Common Data Structures Explained with Videos + Exercises

      • Visualizations?

  • Array
    • Fixed-size storage space
    • There are some utility methods on System.Array that you can use
      • BinarySearch
      • IndexOf / Last
      • Copy
      • Resize
      • Reverse
      • Sort
      • GetEnumerator / foreach loop
      • etc
  • List
    • TODO: Would it be good to add something about the indexer?  Maybe a getAt method?
    • Exercise: solve a problem with this
    • Exercise: for a list of problems, when would it be good to use a List<>?
      • Array for fixed-length situations
      • List<> for the rest
      • So why don't we cover Lists<> instead of arrays?
        • A lot of the extra functionality in List isn't useful in BIT 142/143
          • for a lot of the things that we're doing, List and array are interchangeable - we don't resize the arrays all that often, we don't insert / reorder stuff all that much, and we're frequently focused on just using a bunch of array elements in order to get used to dealing with a collection.
        • Many of the better-paying jobs require you to do more difficult things, getting used to handling the extra difficulty is good
          • Arrays are still used in languages like C, C++, etc, and specifically used for situations where performance is key (operating systems, games, etc)(want to work at MS/Google/Amazon/etc?
    • List<>
      • Implemented as an array internally (source)
      • Good for index-based access to elements
    • SortedList<>
      • Mention that this exists (and what it's used for), but don't cover it
      • This will maintain itself in a particular order, whereas the list just puts thing where you tell it to put things
      • Does a nice Compare & Contrast with SortedDicitionary
      • Also this SO question
  • LinkedList
    • LinkedList<>
      • Implemented as a doubly-linked list
      • Good for sequential access WITHOUT discarding elements (in contrast to Queue, which does discard elements)
        (Can access in either direction)
      • Methods
        • AddFirst  - add to front - AddLast
        • AddBefore/AddAfter
        • Clear
        • Contains, Find, FindLast
        • Remove, RemoveFirst, RemoveLast
        • GetEnumerator / foreach loop
  • Map
    • in Java, the Map interface replaces the Dictionary abstract base class
      • They both map keys to values
    • Called an IDictionary<> in C#
    • Hash Table
      • Hash table can / will use the GetHashCode() method, thus blurring the key/value distinction (Java Maps / C# IDictionary-s explicity treat the key as separate, and potentially unrelated)
    • Dictionary<>
      • Add( Key, Value)
      • Remove
      • Clear
      • ContainsKey, ContainsValue (this will be very slow - O(N) for the linear search)
      • You can enumerate this, but you'll get stuff in jumbled order
    • SortedDictionary<>
      • Same methods as Dictionary<>, only now the enumerator traverses the list in a known order
  • Set
    • HashSet<>
      • Basically a hashtable (there is the older System.Collections.Hashtable class, too)
      • "In simple terms, the HashSet class can be thought of as a Dictionary collection without values."
      • Methods
        • Add
        • Remove
        • Clear
        • Contains
        • Explain why we normally don't enumerate hashtables - either very slow to go in order O(N^2), or else you get stuff back in a random order (but it's O(N)  ).
    • SortedSet<>
      • Methods
        • Add
        • Clear
        • Contains
        • Remove
        • Reverse
        • GetEnumerator / foreach loop
  • Stack
    • Stack<>
  • Queue
    • Queue<>
      • "This class implements a generic queue as a circular array."
      • HOW IS THIS SUBSTANTIALLY DIFFERENT FROM A LIST<>?
        It looks like the Queue can enumerate all it's items, but can only add/remove from the ends. List allows for deletion anywhere
  • Tree
    • Not really provided in C#
    • (The SortedSet is a Red-Black tree, but it doesn't really let you fiddle with the internal details much.  Source)
      
      

 

Paste next section here