You should be able to define or explain the following terms:

• data structure
• algorithm
• major differences between C++ and Python
• scope of a variable
• pass by value (a.k.a. copy by value), pass by pointer (e.g., arrays)
• object oriented programming and its major properties (e.g., abstraction, modularity, reusability, encapsulation)
• class
• instance of a class (i.e., object)
• function call stack
• the heap
• inheritance, is-a relationship
• base class, derived class (a.k.a., parent class, child class)
• polymorphism
• algorithmic analysis (e.g., how to count steps, how to evaluate loops)
• pseudocode (both interpreting and writing)
• asymptotic analysis and Big-O notation
• constant, logarithmic, linear, quasilinear (n lg n), quadratic, and exponential functions
• induction
• correctness of an algorithm
• loop invariants (I won't ask you to solve a loop invariant problem, but you should understand the general use and purpose)
• Abstract data types; interface vs. implementation; advantages to using ADTs
• The List interface, including implementation details and runtime analysis using array lists, linked lists, and circular array lists
• Amortized analysis
• Stack interface and operations
• Queue interface and operations
• Depth-first and breadth-first search
• Divide and conquer
• Recursion trees
• Merge sort and merge

You should be familiar with all aspects of basic C++ programs, such as those you created for labs 00, 01, 02, 04, and the first two parts of 05. This includes:

• how to compile and execute C++ programs
• the int, float, char, bool, string data types
• variables, assignment with =, and basic arithmetic
• boolean and relational operators in C++
• if / else if / else statements, while loops, do-while loops, and for loops
• uses of break and continue
• variables, including their declaration, definition, and use
• functions, including their declaration, definition, and use
• arrays (statically and dynamically allocated)
• basic uses of cout and cin
• basic uses of file streams (i.e., ifstream ofstream)
• purpose of #include and using namespace std;
• void and its use
• pointers, dereferencing, NULL
• dynamic memory management with new and delete (and delete [])
• classes, including their declaration and implementation as well as the use of access control: public, private, and protected, data members, functions, constructors, destructors
• C++ inheritance
• virtual, pure virtual functions, and abstract classes
• dot notation and arrow notation
• tracing a program using a memory diagram (heap and stack)
• Segmentation fault.
• new and delete for basic types, one-dimensional arrays, and two-dimensional arrays
• Roll of class destructors and constructors
• Pointer/array equivalence
• Abstract classes
• Templates

Practice problems

1. Write a C++ program that prompts the user for an integer n and then prints a single output integer, the sum of the integers from 1 to n.


2. Write a boolean function isPrimaryColor that takes a string as an argument and returns true if the string is "red", "yellow", or "blue", and returns false otherwise. Then write a program that prompts the user for a color and uses isPrimaryColor to determine if their color is primary.


3. Draw a memory diagram for cs35/class/02/inheritance/testPerson.cpp as it executes. Include the stack and the heap.


4. Write a Shape class with the following features:
   • private color (a string) data member.
   • a constructor which takes in a color and initializes the color of the Shape.
   • appropriate public getColor(), setColor() and print() accessor functions. print() should output the color of the object, e.g. "Shape with color black."
   Then write a Rectangle subclass of Shape with the following features:
   • a private length and width (both int) data members
   • a constructor which takes a color, length, and width, which it uses to initialize the data members.
   • accessor functions: getArea() and print(). print should output the area and color of the Rectangle, e.g. "Rectangle with area 20. Shape with color black."
   Finally, write a main() function that declares a pointer p to a Shape, creates a single Rectangle on the heap and saves the pointer to that Shape as p, and then prints the Shape and releases its memory.


5. Prove that 41*n^2 + 12n - 1 is O(n^2).


6. Using induction, prove that 0^2 + 1^2 + 2^2 + ... + n^2 is less than or equal to n^3 for all non-negative integers n. NOTE: for this problem, it is easier to assume the proposition is true for n and then prove that is also true n+1


7. Prove by the following by induction for all values n ≥ 1:
   
   The equation above should read: the sum from i=1..n of i^3 = (n^2 * (n+1)^2)/4


8. 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. Do the same for the CircularArrayList class.


9. Define replaceItem for a templated LinkedList implementation. Compare and contrast the expected run time with the ArrayList implementation


10. 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.)

     
        #ifndef QUEUELIST_H_
        #define QUEUELIST_H_
     
        #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"
     
        #endif
    

    Using the above declarations, complete an implementation for the methods getSize(),insertAtHead(T item), and insertAtTail(T item). 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.

    
    
11. Consider the following somewhat simplified 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.
    • 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.
    
    
12. Consider the following algorithm, wackyMergeSort, similar to mergeSort:

     
        wackyMergeSort(A, n):
          if (n <= 1)
            return
          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?
    • Draw a recursion tree for wackyMergeSort on an input of size n. For each node (recursive call) in the recursion tree, write the amount of work you expect to be done for just that recursive call to wackyMergeSort. Use Big-O notation for all parts of this problem, justifying (but not proving) your work.
    • How much total work is done per level in the recursion tree?
    • How many total levels are in the tree?
    • Overall, how much total work is done for wackyMergeSort for an input of size n?