13_Midterm_Review

Midterm Review Overview

• Due Date: Tonight, no late submissions allowed.
• Assignments: Project 4

Goals of the Review

1. Explore the midterm structure.
2. Examine midterm examples.
3. Provide tips for preparation.

Midterm Details

• Date & Time: March 12th, 1:00 PM - 2:15 PM
• Format: Written test in the classroom.
• Restrictions: No hats or sunglasses allowed.

Midterm Structure

• Topics and Points
  • Abstract Data Types & Data Structures: 6 points
  • Analysis: 12 points
  • Implementation: 12 points
  • Programming: 30 points
  • Total: 60 points

Abstract Data Types & Data Structures

• Key Questions to Address:
  • Main purpose of Abstract Data Types (ADTs).
  • Differences between an ADT and a Data Structure.
  • C++ tools for implementing data structures and their support for ADTs.
  • Two approaches to storage in Data Structure implementations and their differences.

Analysis Section

• Compare and Contrast Requirements:
  • Function from a data structure using each storage approach (similarities/differences).
  • Function from two data structures using the same storage approach (similarities/differences).
  • Note: Code examples will not be provided.

Example Analysis

• Task: Compare and contrast the Bag and toVector functions for each storage approach.

Analysis of toVector

// Array Implementation
template<class ItemType>
vector<ItemType> ArrayBag<ItemType>::toVector() const {
    vector<ItemType> bagContents;
    for (int i = 0; i < itemCount; i++) {
        bagContents.push_back(items[i]);
    }
    return bagContents;
}

// Linked Implementation
template<class ItemType>
vector<ItemType> LinkedBag<ItemType>::toVector() const {
    vector<ItemType> bagContents;
    Node<ItemType>* curPtr = headPtr;
    for (int i = 0; i < itemCount && curPtr != nullptr; i++) {
        bagContents.push_back(curPtr->getItem());
        curPtr = curPtr->getNext();
    }
    return bagContents;
}

• Comparison:
  • The array implementation uses index iteration from 0 to itemCount - 1.
  • The linked implementation uses getNext() to traverse nodes in the chain.

Function Comparison Example

• Task: Compare and contrast ArrayBag::add() and ArrayList::insert() functions.

Functions Analysis

// ArrayBag add
template<class ItemType>
bool ArrayBag<ItemType>::add(const ItemType& newEntry) {
    bool hasRoom = itemCount < maxItems;
    if(hasRoom) {
        items[itemCount] = newEntry;
        itemCount++;
    }
    return hasRoom;
}

// ArrayList insert
template<class ItemType>
bool ArrayList<ItemType>::insert(int newPos, const ItemType& newEntry) {
    bool canInsert = itemCount < maxItems && newPos >= 1 && newPos <= itemCount + 1;
    if(canInsert) {
        for(int pos = itemCount; pos >= newPos; pos--) {
            items[pos + 1] = items[pos];
        }
        items[newPos] = newEntry;
        itemCount++;
    }
    return canInsert;
}

• Comparison:
  • ArrayBag simply adds an entry at the end while ArrayList shifts items to create space for a new entry at a specified position.

Time Complexity Analysis

• General Task: Determine the time complexity of specified code blocks and explain reasoning.
  • Example: LinkedQueue::enqueue() operates in O(1) - constant time, no loops.
  • Example: LinkedList::clear() operates in O(n) - linear time due to a loop that removes at position 1 repeatedly.

Implementation Section

• Task: Implement specified data structure functions with indicated storage methods.
  • No need to memorize all functions; understanding the ADT suffices.
  • Focus on necessary attributes for the data structure, storage methods, expected behaviors of functions, and how to utilize the storage method.

Common ADT Operations

• Queue: isEmpty, enqueue, dequeue, peekFront
• Stack: isEmpty, push, peek, pop
• List: isEmpty, insert, replace, remove, clear, getEntry, getLength

Programming Section

• Task: Given a problem, choose the appropriate data structure and justify this choice (50% of exam points).
  • Include correct headers, data structure declaration, function calls, parameters, and arguments.
  • Ensure the solution algorithm works properly.

Example Programming Task

• Implement a main driver that allows a user to enter a word and check if it's a palindrome.

Additional Programming Instructions

• Use existing data structure files without creating new classes.
• Provide functionality explicitly required and ensure proper usage within the driver.

Example Code Implementation

#include <string>
#include "ArrayStack.h"
#include "ArrayQueue.h"
using namespace std;

bool isPalindrome(ArrayStack<char>, ArrayQueue<char>);
int main() {
    string input;
    ArrayStack<char> backwards;
    ArrayQueue<char> forwards;
    cout << "Enter a word: ";
    cin >> input;
    for(int i = 0; i < input.length(); i++) {
        backwards.push(input[i]);
        forwards.enqueue(input[i]);
    }
    if(isPalindrome(backwards, forwards)) {
        cout << input << " is a palindrome" << endl;
    } else {
        cout << input << " is NOT a palindrome" << endl;
    }
    return 0;
}

bool isPalindrome(ArrayStack<char> stack, ArrayQueue<char> queue) {
    while(!stack.isEmpty()) {
        if(stack.peek() != queue.peekFront()) {
            return false;
        }
        stack.pop();
        queue.dequeue();
    }
    return true;
}

Department Policy

• To secure a C or better, students must achieve a C (70%) or higher in:
  1. Average between midterms and final exam.
  2. Overall class grade.
• Not meeting either requirement results in a C-.

Studying Techniques

Memorization Strategies

• Vocabulary: Create flashcards for frequently used or unclear terms.
• Syntax: Practice writing code without looking at solutions, check against examples, and repeat until proficient.

Problem Solving Techniques

• Break the problem into smaller components and apply CS tools to those components.
• Iterative questioning will help identify functions needed for larger programs.
• Ensure testing of code increments and overall functionality.

Test Day Preparation

1. Before the Test:
   • Sleep well, eat well, and consider moderate caffeine intake.
2. During the Test:
   • Arrive early, bring a pencil, and stay relaxed.
   • Outline your algorithm before starting to code.

Next Class Reminder

• Date: March 12th
• Time: 1:00 PM - 2:15 PM
• Format: Written test; classroom rules apply (no hats or sunglasses)