14. Other topics

Review Topics


General Information

Housekeeping

  • Make sure you follow along with this page linked in Canvas
  • Please keep your microphone off unless you are asking a question
  • Please turn on camera if you can (optional)
  • Use chat if you would like to comment or ask questions

Announcements

See Announcements link in Canvas for course information. Here are some other reminders:

  • Vaccine clinics for students this week offered by the Santa Cruz County Office of Education
  • New extra credit for the sampler project: binary search.
  • Remember that PAs and the Individual Readiness Assurance Quiz are due before class on Tuesday.
  • Remember to post in the Pair programming partners discussion group if you need a partner
  • Remember that CAs, Labs, and Class Exercises may be completed up to two days late but with a 10%/day penalty.
  • Remember that some lab solutions are posted in Canvas Modules
  • Cabrillo College is allowing students to select the P/NP option by the grade deadline for the term
  • Free Fresh Market schedule: free fresh fruits and vegetables
  • Food & Housing Resources: free food, meals, temporary and permanent housing
  • COVID-19 Resources and Information: Includes loaner-laptop information
  • Campus WiFi Access
    • Aptos: parking lots K and L on this Cabrillo Aptos Map
    • Watsonville: parking lot at Watsonville Center

Homework Help

Final Exam Approaching

Project Questions?

Questions from last class or the Reading?

14.1: Readiness Assessment Quizzes

  • Reading and participation activities are due before the first class meeting of the week
  • Quizzes assess the comprehension of the reading and participation activities

Quiz Part 1: Individual Readiness Assessment

  • Complete this quiz solo to assess your reading comprehension and readiness
  • Must take this quiz before the first class meeting of the week to ensure you are ready for the team quiz
  • Cannot take the quiz late
  • Quiz is open book and notes but timed
  • Highest score is counted so take the quiz multiple times

Quiz Part 2: Team Readiness Assessment (20m)

  • Must attend the class meeting to take this quiz
  • Login to Canvas and enter the access code
  • Will move to breakout rooms with your team
  • Make sure you have the access code for the exam
  • Openly discuss what you believe to be the best answers for the questions
  • Decide how to agree on the answers
    • Strive to reach a consensus on quiz answers
    • If no consensus, work it out as you and others in your group see fit
  • Turn in the quiz as a group
  • Each group member will receive the same score
  • Return to the main meeting room when finished

Quiz Appeals

  • After completing the team quiz, team members may appeal an answer
  • Appeals can be based on two criteria:
    1. Question is factually wrong

      Appeal must included citations to sources of information that document or support an alternative answer. Team may access reference materials during the appeal.

    2. Question is confusing based on it's wording

      Appeal must include an appropriate rewrite of questions or answers that you interpret as ambiguous or confusing.

  • Work with teammates to develop and write any appeals
  • Team has up to 24 hours after the quiz to email appeal to instructor
  • If appeal is granted, only the teams that submitted appeal gets credit

14.2: Algorithms and Searching

An algorithm is a sequence of steps for accomplishing a task. Some important algorithms involve how to search for information.

14.2.1: Reviewing Linear Search

  • One useful algorithm is to look for a particular value in a list
  • An easy and straightforward approach is linear search (a.k.a. sequential search)
  • In linear search we:
    1. Start at the beginning of the list
    2. Compare each value in the list looking for matches:
      1. If the value is found, then return the index where the element was found
    3. If the loop reaches the end of the list, return "not found"
  • Linear search is easy to implement using a simple loop: (Replit)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int linearSearch(const vector<int>& list, int key) {
        for (unsigned i = 0; i < list.size(); i++) {
            if (key == list.at(i)) {
                return i; // found
            }
        }
        return -1; // not found
    }
    
    int main() {
        vector<int> list { 2, 4, 5, 10, 11, 35, 42, 97 };
        int key = 0;
        int keyIndex = 0;
    
        cout << "List items: ";
        for (unsigned i = 0; i < list.size(); ++i) {
          cout << list.at(i) << ' ';
        }
        cout << endl;
    
        cout << "Enter a value: ";
        cin >> key;
        keyIndex = linearSearch(list, key);
    
        if (keyIndex == -1) {
            cout << key << " was not found." << endl;
        } else {
            cout << "Found " << key << " at index " << keyIndex << "." << endl;
        }
    
        return 0;
    }
    

Linear Search Runtime

  • An algorithm's runtime is the time the algorithm takes to execute
  • If each comparison takes 1 microsecond, a linear search algorithm's runtime is:
    • 1 second to search a list with 1,000,000 elements
    • 10 seconds for 10,000,000 elements
    • In other words, one second for each one million items
  • Amazon's online store has over 200 million items
  • If they used linear search, it would take 100 seconds to find an existing item on average
  • If an item was not found, it would take more than 3 minutes to finish the query

14.2.2: Reviewing Binary Search

  • When a list is sorted, a much faster search algorithm exists: binary search
  • Binary search works by comparing the target value to the middle value of the list
  • If they are not equal, the half in which the target cannot exist is eliminated and the search continues on the remaining half
  • Each step reduces the values that need to be search by half
  • The search ends when the item is found or the search space is empty (element not found)
  • Search time is log2(N) + 1
  • Thus finding one item in 200 million, like for an Amazon product, takes 29 steps at most

Comparing binary and linear search
Image source: miro.medium.com

Exercise 14.2: Coding Binary Search (15m)

In this exercise we develop code for binary search of a sorted list.

For this exercise we break into teams. Within the team, work with each other to develop a solution. When the team has finished, choose one member to show your solution to the class by sharing your screen. The instructor will ask one team to share their solution.

Specifications

  1. Start Replit and copy the following code into the code editor.
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main() {
        vector<int> list { 2, 4, 5, 10, 11, 35, 42, 97 };
        int key = 0;
        int keyIndex = 0;
    
        cout << "List items: ";
        for (unsigned i = 0; i < list.size(); ++i) {
          cout << list.at(i) << ' ';
        }
        cout << endl;
    
        cout << "Enter a value: ";
        cin >> key;
        //keyIndex = binarySearch(list, key);
    
        if (keyIndex == -1) {
            cout << key << " was not found." << endl;
        } else {
            cout << "Found " << key << " at index " << keyIndex << "." << endl;
        }
    
        return 0;
    }
    
  2. Declare the following function and add braces for the definition:
    int binarySearch(vector<int> list, int key)
    
  3. Within the body of the function add a statement returning -1.
  4. At this point, uncomment the function call in main(). When run, the program output should look like:
    List items: 2 4 5 10 11 35 42 97
    Enter a value: 97
    97 was not found.
    
  5. Within the body of the function and before the return statement, declare and initialize the following variables:
       int low = 0;
       int high = list.size() - 1;
       int mid = 0;
    
  6. After the variables, code a while loop with a test condition that evaluates to true while high >= low.
  7. Within the while loop, add a statement to calculate the value of the midpoint between high and low, and assign the value to the variable mid.
  8. After calculating the midpoint, add an if-statement testing if list.at(mid) < key. If so, assign low = mid + 1.
  9. After the if-statement, add an else if clause that tests if list.at(mid) > key. If so, assign high = mid - 1.
  10. After the else-if clause, add an else clause that returns mid.
  11. Compile and run your program again and verify the output looks like:
    List items: 2 4 5 10 11 35 42 97
    Enter a value: 97
    Found 97 at index 7.
    
    and this:
    List items: 2 4 5 10 11 35 42 97
    Enter a value: 24
    24 was not found.
    
  12. Once satisfied with your code, copy your code into a text editor, save the file as "binarysearch.cpp", and to submit the file to Canvas with the rest of the exercise files for the week.

When finished developing your code click hereClick to show answer to verify. Code need not look exactly the same. After you have completed your own program, reviewing another is often helpful in learning how to improve your programming skills.

14.3: Selection Sort

Selection sort is an algorithm that sorts elements within a list, such as a vector.

14.3.1: Reviewing Selection Sort

  • Selection sort is an algorithm for sorting the items of an ordered list like a vector
    { 5, 2, 4, 6, 1, 3 }
    
  • The algorithm treats the list as two parts, a sorted part and an unsorted part
          { 5, 2, 4, 6, 1, 3 }
    sorted | unsorted
    
  • Initially the sorted area is empty
  • The selection sort algorithm searches the unsorted part of the list for the smallest value
          { 5, 2, 4, 6, 1, 3 }
    sorted | unsorted
    
  • The smallest unsorted element is selected and, if smaller, is exchanged with the first unsorted element
          { 1, 2, 4, 6, 5, 3 }
    sorted | unsorted
    
  • The first unsorted element is then incorporated into the sorted area
        { 1, 2, 4, 6, 5, 3 }
    sorted | unsorted
    
  • The selection process repeats until the unsorted area is empty as shown in the following animation

Animation of Selection Sort

Selection sort animation
Image source: Selection Sort in JavaScript

14.3.2: Implementing Selection Sort

  • Selection sort has the advantage of being easy to code
  • The main parts are:
    1. Iterate over the list with a for-loop
      for (unsigned i = 0; i < list.size() - 1; ++i)
      
    2. Inside the for loop, find the minimum value in the unsorted area of the list
      indexSmallest = i;
      for (unsigned j = i + 1; j < list.size(); ++j) {
        if (list.at(j) < list.at(indexSmallest)) {
           indexSmallest = j;
        }
      }
      

      Notice that the unsorted area starts at i + 1.

    3. Exchange list.at(i) and list.at(indexSmallest)
  • We will develop an implementation of selection sort in the following exercise

Exercise 14.3: Coding Selection Sort (10m)

In this exercise we develop code for selection source.

For this exercise we break into teams. Within the team, work with each other to develop a solution. When the team has finished, choose one member to show your solution to the class by sharing your screen. The instructor will ask one team to share their solution.

Specifications

  1. Start Replit and copy the following code into the code editor.
    #include <iostream>
    #include <vector>
    using namespace std;
    
    void printList(vector<int>& list) {
        for (unsigned i = 0; i < list.size(); ++i) {
          cout << list.at(i) << ' ';
        }
        cout << endl;
    }
    
    int main() {
        vector<int> list { 10, 2, 78, 4, 42, 35, 7, 11 };
        cout << "List items: ";
        printList(list);
        cout << "Sorted list: ";
        selectionSort(list);
        printList(list);
    
        return 0;
    }
    
  2. Declare the following function and add braces for the definition:
    void selectionSort(vector<int>& list)
    
  3. At this point, uncomment the function call in main(). When run, the program output should look like:
    List items: 10 2 78 4 42 35 7 11
    Sorted list: 10 2 78 4 42 35 7 11
    
  4. Inside the function, add a for-loop to iterate over all elements of the list:
    for (unsigned i = 0; i < list.size() - 1; ++i)
    
  5. Inside the outer for-loop, add an inner for-loop to find the minimum value in the unsorted area of the list
    // Find index of smallest remaining element
    int indexSmallest = i;
    for (unsigned j = i + 1; j < list.size(); ++j) {
        if (list.at(j) < list.at(indexSmallest)) {
            indexSmallest = j;
        }
    }
    
  6. After the inner for loop, add code to swap list.at(i) and list.at(indexSmallest)
    // Swap list.at(i) and list.at(indexSmallest)
    int temp = list.at(i);
    list.at(i) = list.at(indexSmallest);
    list.at(indexSmallest) = temp;
    
  7. Compile and run your program again and verify the output looks like:
    List items: 10 2 78 4 42 35 7 11
    Sorted list: 2 4 7 10 11 35 42 78
    
  8. Once satisfied with your code, copy your code into a text editor, save the file as "selectionsort.cpp", and to submit the file to Canvas with the rest of the exercise files for the week.

When finished developing your code click hereClick to show answer to verify. Code need not look exactly the same. After you have completed your own program, reviewing another is often helpful in learning how to improve your programming skills.

14.4: Project Design and Prototype Review

  • The instructor will review your project proposal to provide recommendations for your final project.
  • You will need a computer for this meeting so you can screen share
  • Due to the number of students, review time will be short (~3 minutes)

Waiting Room Instructions

  • You will be in a waiting room, so have other work to do while you wait
  • When it's your turn, the insturctor will bring you into main room
  • If you miss your turn, rejoin the meeting to get added back to the queue
  • Put your name in chat if you are ready and would like to review earlier
  • Names submitted for earlier review will be selected randomly
    srand(time(0));
    cout << rand() % numRemaining + 1 << endl;
    
  • After earlier review, remaining students will then be selected randomly

14.4.1: Before the Review

  • Submit the following to Canvas before the review:
    1. Project design documentation
    2. Source code file(s) for your prototype (i.e. .cpp files)
    3. Any other files needed to make your prototype code function
  • Remember that there are no late submittals accepted after the review time
  • If you have problems completing your proposal or prototype, then turn in what you have and present
  • Without presenting you get a much lower score

Prototype Setup

  • Verify your prototype code compiles
  • Prepare your computer to share it's screen
  • If you get stuck or do not know what to do, ask for help

14.4.2: Reviewing Your Project Proposal and Prototype

Be prepared to:

  1. Describe the purpose of your project
  2. Describe parts of the design when asked: class, file system, logic and flow, user interface
  3. Share your screen and compile your source code by typing into Terminal:
          g++ -Wall -Wextra -Wpedantic -o main main.cpp (other-cpp-files)
    
    compiler | -------- options --------  exe | files to compile
    exe: executable program file nameS
    
    See lesson 4.2.1: Compiling with warnings enabled
  4. Demonstrate what is working in your program so far

After the Review

  • You are free to leave after your review
  • If in a breakout room, let the next student(s) know it is their turn via chat and voice before you leave

Wrap Up

Due Next:
Wk 14 Exercises, CAs (5/9/21)
Wk 14 Lab: Sampler Project (5/13/21)
Wk 15 Exercises (5/13/21)
Work on your project!
Last Updated: May 07 2021 @03:22:05