e02 : Midterm Exam-II

Instructions for the exam

• You may bring one 8.5” x 11” piece of paper with notes on both sides. This paper will be collected along with your exam, so make your own copy if you would like to keep it.
• No calculators or phones are allowed in the exam
• No other notes or books are allowed
• There are no makeups for this exam
• You must write your name on every single sheet of paper including your notes
• We will provide you with scratch paper
• We will provide you the table of operator precedence

Collaborative notes

A fun way to prepare for the exam is to work with your classmates to create notes collaborative. I have created a document with the above list of topics. Jump right in and add content, code examples and other useful information. I will review and comment your notes as will the tutors and TAs! Students who contribute will get star points :)

Click here to contribute to Collaborative Notes

Review problems

Solutions available HERE

1) Find the Big-O running time of the entire snippet of code below.

for(int i=N; i>1; i-=2) {
	for(int j = 1; j<N; j*=2) {
		cout<<i<<j<<endl;
	}
}
for(int i=N; i>1; i=i/2) {
	for(int j = 1; j<N; j+=5) {
		cout<<i<<j<<endl;
	}
}

2) Complete the following table, where you are asked to find the Big O running times for the remove, find, insert, find min, and find max operations on each data structure. Provide the tightest bound.

3) Insert the following values into a binary search tree (in the order given), and draw the result 5, 2, 3, 21, 120, 15, 1

4) Write a member function of a BST that, given an integer value as input, returns an std::vector of all values in a BST that are larger than the given value, or an empty vector if the node with the input value doesn’t exist. You may use any functions from lab04 in your solutions.

5) Is this a valid binary search tree? Explain briefly.

If the tree is valid, trace the preorder, postorder, and inorder traversals of this binary tree. If not, trace the traversals of the tree without the problematic node.

Post exam information

Reference material

You are expected to know the material from the following lectures, labs and homeworks:

• Lecture 1 to lecture 11 , including all code implemented in class
• Homework 1 to 6
• Labs 0 to 5
• pa01 and pa02

Study guide

• Converting procedural code to OOP
• Basic design of classes - member variables and methods. Corrrect declaration of accessors and modifiers and the appropriate use of the const keyword
• Distinguishing between class vs.instance
• Understanding how to create instances of a class on the stack and heap
• Member functions, non-member functions and friend functions - why and how
• Operator overloading - why and how
• The big 4- Constructor, destructor, copy-constructor, assignment operator (default behavior, overloaded implementation and identifying when each is invoked in any given code)
• Linked-lists - you may be asked to implement any function that involves a linked list
• Recursive implementations involving linked-lists
• The big 4 for linked-lists - why and how to overload the c’tor, de-stor, copy-c’tor and copy assignment
• Run time analysis – Big-Oh
• Deriving Big-Oh for code that involves loops
• Binary Search Trees - Implementing all operations and derivations of running times.
• Binary Search Trees - Implementing overloaded operators, and the big 4.
• Analyzing the run times of operations supported by linked lists, sorted arrays ans binary search trees- insert, search, delete, min, max

Past exams

Midterm-1 questions are available at: http://bit.ly/CS24-S18-Midterm-I-questions

Midterm-1 solutions are available at: http://bit.ly/CS24-S18-Midterm-I-Solutions

Past exams have been posted on gauchospace.

Review notes

Link to the review notes