Warning: This study guide is still in draft form, the definitive version will be updated Tuesday (March 20) morning.
In addition to all concepts from Quiz 1,
You should be able to define or explain the following terms:
- Big-O and analysis of algorithms
- Abstract data types; interface vs. implementation; advantages to
using ADTs
- The List interface, including implementation details and runtime analysis
using array lists, linked lists
- Divide and conquer (general idea, no details)
- Merge sort and merge
- Quick sort, partition, randomized quick sort, and pivot
- Concepts related to sorting: runtime, comparisons, swaps.
- Stack interface and operations
- Queue interface and operations
- Depth-first and breadth-first search
- Dynamic memory management and responsibilities
You should be familiar with the following C++-related concepts:
- Segmentation fault.
- new and delete for basic types, one-dimensional arrays,
and two-dimensional arrays
- Role of class destructors and constructors
- Pointer/array equivalence
- Abstract (or pure virtual) classes
- Templates
- comparison operators
Practice problems
- You should be able to implement all of the methods
of LinkedList and ArrayList classes as well as
provide a stack trace of a sample main() program.
Declare and implement a new method for ArrayList ,
replaceItem(int i, T val), that replaces the existing value at
position i with val. It should return the
previously held value.
- Define replaceItem for a templated LinkedList
implementation. Compare and contrast the expected run time with
the ArrayList implementation.
- Write a program that prompts the user for an integer n,
then reads n strings into an array of strings stored on the heap,
prints true if the array is sorted and false otherwise, and
then frees the memory on the heap.
As part of this program declare and
implement a templated boolean isSorted(T* a, int n)
function that, given a pointer to an array a and the length of
that array n, returns true if the array is sorted and false
otherwise.
-
In class, we defined a Queue using various List
implementations. Let's flip this around.
Consider the following (somewhat strange)
List definition, QueueList,
that uses an awesomely cool MagicQueue to represent the data
in the list. (Note that the details of MagicQueue are not
given, but are also unnecessary given what you know about interfaces.)
#pragma once
#include "list.h"
#include "magicqueue.h"
template <typename T>
class QueueList : public List<T> {
private:
MagicQueue <T> values;
public:
QueueList();
~QueueList();
void insertAtHead(T item);
void insertAtTail(T item);
int getSize();
bool isEmpty();
// ...etc. all List methods are declared here
};
#include "queuelist-inl.h"
Using the above declarations, complete an implementation for
the methods getSize(), insertAtHead(T item), and
removeTail(). Your answers should be written as they would
appear in queueList-inl.h, paying attention to the scope and
template operators. Once complete, describe the O() of
each of your methods.
Again, the details of MagicQueue are not
important; you should assume it implements a Queue
interface properly in O(1) time.
- Consider the following somewhat simplified, inaccurate map of Sharples:
- Use depth-first search to find a path from the Entrance
to the Fried food location. Carefully track the data
used by depth-first search as the algorithm runs. You can assume that neighbors are visited in alphabetical order.
- Use breadth-first search to find a path from the Entrance
to the Fried food location. Carefully track the data
used by breadth-first search as the algorithm runs. You can assume that neighbors are visited in alphabetical order
- Trace and show work for sorting a set of integers using both
merge sort and quick sort. In particular, be able to see how the helper
methods merge and partition are used.
- Consider the following algorithm, wackyMergeSort,
similar to mergeSort:
wackyMergeSort(A, n):
if (n > 1)
A1 = new array
A2 = new array
copy first two-thirds (2n/3) of A into A1
copy last one-third (n-2n/3) of A into A2
wackyMergeSort(A1, 2n/3)
wackyMergeSort(A2, n-2n/3)
// merges sorted A1, A2 back into A
merge(A1, 2n/3, A2, n-2n/3, A)
- Is wackyMergeSort a correct sorting algorithm?
- How much total work is done per "level" of recursion ?
- How many total levels are in the tree?
- Overall, how much total work is done for wackyMergeSort
for an input of size n?