Midterm Review Overview
- Due Date: Tonight, no late submissions allowed.
- Assignments: Project 4
Goals of the Review
- Explore the midterm structure.
- Examine midterm examples.
- 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
- Before the Test:
- Sleep well, eat well, and consider moderate caffeine intake.
- 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)