1 CSS 342 Data Structures, Algorithms, and Discrete Mathematics IMidtERm REVIEW.
2 Midterm: Carrano Sections CoveredChapter 1, Data Abstraction : All except UML C++ Interlude 1: All, except 1.4, 1.5 Chapter 2, Recursion: All Chapter 3, Arrays: All C++ Interlude 2, Pointers/Memory: All, except 2.4 Chapter 4, Linked lists: All Chapter 5, Recursion++: 5.3, 5.4 only Chapter 7, Stacks: All Chapter 8/9, Lists: All Appendix A, C++: All Appendix D, Software Lifecycle: All Appendix E, Induction: All
3 Midterm topics Interface Design Encapsulation C++ fundamentalsTenants of OOP/C++ Interface Design Encapsulation C++ fundamentals Constructors Operator Overloading: when/how Pass by value, ref, const ref Copy Constructors Assignment
4 Midterm topics Pointers Dynamic Memory Allocation heap v. stack usageRecursion Induction Templates Algorithms: bubble sort, insertion sort, Binary Search Data structures: string, vector, stack, array, linked list (single, double)
5 Why Object Oriented Programming (OOP)?Abstraction Encapsulation Hierarchy Polymorphism
6 Interface Design Simple Complete Cohesive Descriptive IntuitiveMinimal No Public Data Amenable to loosely couple
7 Problem Design an interface to represent a Book
8 Call by Value, Reference, and Constant Referencestruct Rectangle { int length; int width; }; int Area(Rectangle rect) int Area(Rectangle &rect) int Area(const Rectangle &rect) { int temp; temp = rect.length; rect.length = 35; return(temp * rect.width); } int main() { int result; Rectangle r = { 3, 3 }; result = Area(r); cout << "length = " << r.length << endl; cout << "width = " << r.width << endl; cout << "Area = " << result << endl; return 0; }
9 Problem Circle the lines of code below would have compiler errors?Put a line through those which would have runtime errors? How man constructors are callsed when the code is invoked? Bird Bird::TheCoop(Bird b1, const Bird &b2, Bird &b3) const { int x = b2.wingSpan; wingSpan = b1.wingSpan; this->wingSpan = b3.wingSpan; Bird b = b2; b3.wingSpan = wingSpan; b2.wingSpan = b3.wingSpan; b2.wingSpan = 8; b3.wingSpan = x; return b; }
10 Problem: Operating OverloadingWhat is the signature for overloading the == operator? Given a class Foo with the assignment operator overloaded, overload the copy constructor.
11 Operating Overloadingclass Rational { friend std::ostream& operator<<(std::ostream &outStream, const Rational &rat); friend std::istream& operator>>(std::istream &inStream, Rational &rat); public: Rational(); Rational(int a, int b); int getNumerator() const; int getDenominator() const; Rational operator*(const Rational &rat) const; Rational operator/(const Rational &rat) const; Rational operator+(const Rational &rat) const; Rational operator-(const Rational &rat) const; ………. }
12 Arrays Arrays: reservation and construction of indexed set of objects or built-in types int x=5; int arr1[100] int arr2[3] = {34, 7, 34}; char cArr1[7]; char cArr2[10][5]; arr1[x] = 32; arr2[0] = arr1[x]; cArr2[3][3] = ‘a’; Arrays v Pointers (following are equivalent) void Foo(int arr[]) { } void Foo(int *arr) { } MyFooClass theFooObj; MyFooClass arrFoo[200]; //default constructors run MyFooClass *pFoo; pFoo = arrFoo; arrFoo[54] = theFooObj; pFoo = &theFooObj;
13 Time of Constructor InvocationAutomatic Local Each time block is executed Static Local Once –first time it is hit Global In order of declaration in translation unit Typically before main() is entered Destroyed in reverse order of construction Dynamic new/delete Malloc/Free– just memory, not constructor Array: one per item w/new
14 Templates PolymorphismAllows for multiple types to be passed to routine Works on Function or Class level Syntax: template
15 Dynamic Allocation 4 1 2 3 Pointer declaration int *p, *q;Dynamic allocation p = new int; q = new int; Deallocation delete p; p = NULL; Memory leak q = new int; 4 1 ? p q 2 p q ? 3 p q NULL p q NULL Leak! ? ? ? ?
16 Dangling References: common causesA pointer which is initialized but not set to NULL Delete or free is called and pointer is not set to NULL Aliasing of pointers which are not updated in tandem
17 Allocation: where / when
18 Induction Axiom: The principle of mathematical inductionA property P(n) that involves an integer n is true for all n ≥ 0 if the following are true: P(0) is true. If P(k) is true for any k ≥ 0, then P(k+1) is true.
19 Problem Find a formula for 𝑖=1 𝑛 1 𝑖(𝑖+1)𝑖=1 𝑛 1 𝑖(𝑖+1) by examining the value of this expression for small values of n. Use mathematical induction to prove your result.
20 In order to understand recursion, it helps to understand recursion
21 A Catalan number is defined by the following recursive formula:Write a recursive function which computes the nth Catalan number.
22 Copy Constructor ReviewCan be implemented with call to default constructor and then assignment (may not be most efficient) Is called in four cases: MyObj o1(o2) MyObj o1 = o2 Pass by Value Return by Value
23 Problem There is no copy constructor in the Rational class we built in class (with int numerator and denominator data members), yet it works correctly, Why?
24 A linked list with headPtrFIGURE 4-3 A head pointer to the first of several linked nodes Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
25 Problem Insert or move a node in a singly linked list
26 Array v. Linked List for StackArrays easy to use, but have fixed size Increasing size of dynamically allocated array can waste storage, time Array based implementation good for small bag Linked chains do not have fixed size
27 Resources Do the posted tests / quizzes Do the Induction problemsReview all slides Read Carrano chapters and do problems in back Want even more? Cusack on Induction