CSI 202 - Fall 2015 - Final Exam Review


Review CSI 201:
  C++ base types, string
  for, while, if	
  functions/methods, main
  static arrays v. dynamic arrays
  classes
  numeric manipulation 
  
  
Linux commands:
      ssh, scp, passwd, make
      ls, cat, script
      cp, mv, rm
      cd, mkdir  
      g++, make

Other:
	makefiles
	meaning of . and ..

Memory and Memory Diagrams 
 - Stack V. Heap
 - Static allocation vs. Dynamic allocation
 - Compile time vs run-time
 - Function Stack

Classes:
 - programmer-defined type
 - public vs private
 - dot (.) operator
 - w/ pointers and using the arrow (->) operators
 - with dynamic data - shallow vs deep copy
 - the big 4 - constructor, destructor, copy assignment, copy constructor (related to shallow vs deep)

Pointers:
  - declaration, meaning of star (*) in various places
  - Dynamic arrays
  - reference, dereference
  - new and delete
  - NULL
  - pointer / dynamic memory issues:
    - garbage
    - stale pointers
    - pointers to stack addresses
    - segmentation fault
  - deep copy vs shallow copy


Linked Lists:
  - node structure and code
  - pointers, use of NULL
  - end of list
  - head v tail
  - add to front, output, delete, print, operations on every element

STL: 
  stack - push pop size empty top overflow underflow
  queue - push pop size empty front
  vector - as dynamic arrays with reserve - [] push_back size resize empty
  list - double linked list
  set - tree (described in the future)


Trees:
  root, subtree, child, parent, leaf, height, depth
  traversals: depth - pre post in, breadth
  worst-case balance
  fully balanced
  Binary Trees
  Binary Search Trees
  	 -balance
	 -auto-balancing: rotations, two types, AVL, Red-Black
	 -inserting: bottom-up vs top-down


---------Sample quick answer questions:
  What do the following mean in linux?
  What linux command does the following operation?
  What compiler do we use?
  Show a sample compilation of the file hw1.cpp into the hw1 executable.
  Does the following code leave garbage? How much?
  Does the following code leave a stale pointer? Which variables are stale?
  What is the output of the following code?
  When does a segmentation fault occur?
  What is the danger of a stale pointer?
  When might the result of a pointer operation be undefined?
  Using STL, would you use a list or a vector in "xyz" situation?
  
  
--- since  exam 1:
  What is the root of the tree when inserting these numbers?
  What is the height of the tree when inserting these numbers?
  What is the optimal height of a tree with x number of nodes?
  What is the worst height of a tree with x number of nodes?
  When does a tree have optimal search time?
  When is data not well suited to be inserted into a tree? (without rotations)
  In which situations should a stack, queue, tree, AVL, RB, vector be used?
  Insert this data into [stack|queue|tree|AVL|RB|vector] - what element is at the [top|front|root|front|back] ?
    


---------Sample practical/questions:
* refers to difficulty. more stars is more difficult.

Assume LLNode in questions referring to linked lists. You may not
assume the LinkedList class or its implemented functions unless
otherwise mentioned. Also, LL refers to a linked list.

*     - Given the head of a LL, show how to print every element of the LL.
*     - Given the head of a LL, demonstrate how to change every element by increasing its value by 1.
*     - Given the head of a LL, show how to find the tail of the LL.
*     - Given the head of a LL, add a new element to the LL.
**    - Given an array with 10 elements, make a new array with 11 elements that has the same first 10 elements.
**    - Given an array, make a new array in the reverse order.
**    - Given an array, reverse the order of the elements without making a new array.
**    - Given the head of a LL, make a copy of the LL. (two identical LL at the end)
**    - Given the head of a LL, delete every node in the list and change the head to point to an empty list.
***   - Given the head of a LL, show how to create a new LL in the reverse order. (two LL at the end)
****  - Given the head of a LL, show how to modify the LL to reverse the order. (one LL at the end) 
      

--- Practical questions since exam 1:
* 	  - Insert these numbers into these trees. Compare search times of resulting trees.
* 	  - Given two vectors, show how to create a third vector with all the elements of the first two.
*	  - Operands are pushed onto the stack. Binary operators pop two operands from the stack and push the result on the stack. When this process is complete, the final result is the only element on the stack. Implement this for the sample types of operands and operands.
*	  - Stacks are immensely useful for matching. Implement a stack that matches a sample "language"
*	  - Place every element of a tree into a vector in any order.
*	  - Given a tree, perform a DFT that accomplishes some task (ex: print, increase all values by 10). 
** 	  - Given a tree, make a copy.
** 	  - Given a tree, show how to insert the tree items into an empty vector in sorted order.
*** 	  - Given two sorted vectors, show how to create a new vector that is a sorted version of the first two.
*** 	  - Use a BFT to put every element of a tree into a vector.
***	  - Delete a node from a Binary Tree
****	  - Given two sorted vectors, alter one vector to insert the other and be sorted.
****	  - Delete a node from an AVL|RB Tree