CS 225 Final Review

C++

void print(int value); // by value
void print(int * value); // by address
void print(int & value); // by reference
void print(int * & value); // by a'r

Pay attention to the consistency between declaration and invocation:

If declared as (int value), an error will be thrown by invoking with (int * value)

Const Keyword

Const can be placed in so many positions:

placed after declaration:

 int Deer::print() const;
 // No change to class members
 // Nonconst->Const, reverse forbided

placed before return

 const int Deer::print(); // return a const

placed before parameter

int Deer::print(const int x); // accept a const

For example:

class Fred {
public:
  void inspect() const;   // This member promises NOT to change *this
  void mutate();          // This member function might change *this
};
void userCode(Fred& changeable, const Fred& unchangeable)
{
   changeable.inspect();   // Okay: doesn't change a changeable object
   changeable.mutate();    // Okay: changes a changeable object
   unchangeable.inspect(); // Okay: doesn't change an unchangeable object
   unchangeable.mutate();  // ERROR: attempt to change unchangeable object
}

Read the pointer declarations right-to-left:

const X* p means “p points to an X that is const”: the X object can’t be changed via p.
X* const p means “p is a const pointer to an X that is non-const”: you can’t change the pointer p itself, but you can change the X object via p.
const X* const p means “p is a const pointer to an X that is const”: you can’t change the pointer p itself, nor can you change the X object via p.

Also:

const int a = 5; // constant object

Deer const a; //constant object

int const & a; // constant reference

int const p[5]; // constant array

char * const cp; // a constant pointer

char const * cp; // a pointer to constant

Constructor and Destructor

The requirement of

Copy Constructor
Destructor
- Dynamic memory allocation
```
~sphere() {
delete[] atts;
}
```
Assignment Operator
- protect against re-assignment: if (this != &rhs)
- clear lhs
- copy rhs
- return a helpful value: return *this

Inheritance

Object assignment:

Base b;
Derived d;
b = d; // OK, sliced
d = b; // compiler error

Base * b;
Derived * d;
b = d; // fine, no slicing
d = b; // compiler error

Function:

sphere s;
ball b;
s.display(); // sphere
b.display(); // ball

sphere * sptr;
sptr = &s;
sptr->display(); // sphere

sphere * sptr;
sptr = &b;
sptr->display(); // sphere, early function binding

Virtual function and polymorphism:

// display() is a virtual function
if (a == 0) sptr = &s;
else sptr = &b;
sptr->display(); //depends on value of a

Templates

template <class T, class U>
T addEm(T a, U b) {
  return a + b;
}

int main() {
  addEm<int,int>(3,4);
  // 7
  addEm<double,int>(3.2,4);
  // 7.2
  addEm<int,double>(4,3.2);
  // 7 (truncates)
  addEm<string,int>(“hi”,4);
  // compiler error
  addEm<int,string>(4,“hi”);
  // compiler error
}

Stack and Queue

Implementation:

Stack:

Push:

array: $> O(n) >$

single/double link list: $> O(1) >$

Queue:

Link list? Array?

Top in the head? Front in the head?

Single link list? Double? Sentinels?

Tail Pointers?

Time complexity?

Top in the head:

easy to insert and remove, good for stack

Front in the head:

easy to remove hard to insert

requires a tail pointer

Back in the head:

easy to insert and hard to remove

a tail pointer will not help in single link list

Tree

B-Tree:

Nodes in a b-tree can store $m-1$ elements and have $m$ children

Binary Tree:

AVL Tree:

Quadtree:

KD-Tree:

quick sort algorithm

Hashing

Priority Queues and Heap

Disjoint Set

Graph

contain a loop? $n$ vertiecs $n-1$ edges

MST and Dijkstra

Kruskal: Overall (E log E)

Prim: edge by edge (E + V log V)

Dijkstra: vertex by vertex (E log E) with binary heap

Final