CSE 240 Final Exam Review
CSE 240 Final Exam Review
1
Topics Covered in the Finals
The final exam will cover the following topics:
Object-Oriented Paradigm (C++)
Functional Paradigm (Scheme)
Logic Paradigm (Prolog)
Total points: 70
45 multiple choice points.
25 write-in questions points
Time allowed is 110 minutes
70 minutes for multiple choice
40 minutes for write-in
2
Memory Management
Static Memory- allocated during compilation before program executes.
One copy per application.
Used for global and static variables.
The value of each global or static variable is consistent across all files and object instances.
Goes out of scope when the program terminates.
Stack Memory- allocated for all non-static “local” variables.
Used for the local variables within functions.
Automatically de-allocated when the function goes out of scope.
Heap Memory- dynamic memory allocation
Used to create objects and structures of any data type.
Uses keyword “new” or some variant of “malloc”.
Rule of thumb: every “new” used must have a corresponding delete.
3
4
all local variables and local objects, including member functions
size known at compilation time
Global and static
variables & objects
Heap
Stack
Program code
size known at compilation time
Starting address
Stack pointer
Heap pointer
Static memory
Memory Management
Example of Memory Management
#include
using namespace std;
int PI = 3.14;
struct node
{
float value;
node* next;
};
float area(float radius)
{
float toReturn = PI * radius * radius;
return toReturn;
}
int main()
{
static radius = 5;
node* head = new node();
head->value = area(radius);
delete node;
node = NULL;
return 0;
}
5
Local variable from stack memory
– Parameters
– Local Variables
Static variable from static memory
– Use of static keyword
Object created from heap memory
– Use of keyword “new”
Every new should have a corresponding delete
Global variable from static memory
– Declared outside any class or method
Class (C++)
Class definition gives class members:
Description of state (internal variables) // Like struct
Operations (functions) // struct can’t do this
Controlling Access to Class Members:
– Public : can be used by any functions in the program.
– Protected : can be used only by members functions of the class and the derived classes from the original class.
– Private : can be used only by member functions of the class.
6
Implementation of Member Functions
(C++)
In-class : it is more efficient to have function implementation in the class.
Out-class : structurally clearer to separate implementation from definition.
Scope Resolution Operator:
class_name::function_name
Example:
bool Queue::compact(void)
7
Constructor and Destructor (C++)
What is a constructor? A function whose name is the same as the class name and is used to automatically initialize objects.
What is a destructor? Used to de-allocate any memory you allocated on the heap from within your class (i.e. call delete on any variables you created from the heap).
What is memory leakage? If a programmer forgets to delete unused variables, the program will eventually run out of memory.
Dangling Reference: Trying to access an object that has been deleted or go out of scope.
When is destructor needed? When an object created using heap memory must be deleted. (i.e. an object that uses an array from).
Do you know how to define a destructor?
virtual ~Queue() {
delete buffer;
buffer = null;
}
8
8
Inheritance (C++)
What is inheritance?
Define new classes by extending existing class: support code reuse.
What is a base class? The parent class.
What is a derived class? The children of the base class. They are extended from the base class and have all the properties as the base class. They can have more properties.
Compare and contrast “is-a” relationship vs. “has-a” relationship.
Inheritance “is-a” relation, members of the base class can be used in the same way as its own members. A penguin is-a bird.
Containment “has-a” relation, requires an additional level of access path and setup to use the (super) data. A car has-a wheel.
9
Polymorphism (C++)
Why declare virtual classes?
Can redefine base class fields or operations for more specific behavior.
Example: base class of polygon uses an area function. Square can be a derived class and redefine area function as side*side.
Polymorphism in C++:
A pointer to a base class can be assigned to a derived class since the derived class has all elements of the base class. Allows the same function to perform different behaviors.
Polygon shape = *squarepointer;
area = shape->area();
10
11
Inheritance and Polymorphism (C++):
See text Section 2.10 Case Study
11
name
email
phone
Person
double gpa;
Student
char *program;
student(g, p);
Faculty
char *position;
faculty(p);
Person();
~person();
virtual display();
virtual display();
virtual display();
~student();
~faculty();
*plink
*next
Container
*plink
*next
*plink
*next
null
head
Linked List
Inheritance
Inheritance and Polymorphism (C++)
Do you know how to create a linked list of “Person” objects?
12
1) Create a new Container object:
Container *cNode = new Container();
2) Create a new Person object.
Person *pNode = new Person();
4) Link this Container node into the list.
cNode->next = head;
head = cNode;
3) Link this Person object into Container object.
cNode->plink = pNode;
Virtual and Overloading
What are virtual functions?
Where are they used?
What are overloading functions?
Must have different parameters.
Different return types do not count.
What are overloading operators?
How are they defined?
13
Scheme
Uses prefix notation: 3+2 (+ 3 2)
Naming convention: use dashes for next word. Ex: squareArea(int side) (square-area side)
Form: something to be evaluated. Anything within parentheses will be evaluated. Ex: (- 3 2 )
Note: (2) cannot be evaluated (no operation) so it will cause an error. Use ‘(2) instead.
All forms are evaluated in a run-time global environment.
14
Binding and Procedures
Scheme uses a form of assignment called binding.
Binding: associate a name with a value or an expression
Example: (define pi 3.141592653579)
Procedure: abstraction for an expression that has operand(s) that are free variables.
Examples:
(define (name parameter1 parameter2 … parameter n) (body) )
(define name (lambda (parameter1 parameter2 … parameter) (body) ) )
(define (force mass accel) (* mass accel) )
(define force (lambda (mass accel) (* mass accel) ) )
15
Scheme Data Types
What non-functional features does Scheme allow?
display and begin
Data Types:
String: use quotation marks “Hello”
Boolean: true is #t and false is #f
Character: #\A means the character ‘A’
Symbol: turns code to data. ‘Jim is a symbol
Note: (+ ‘5 4) returns 9 even thought ‘5 is a symbol
List : ‘() is an empty list. ‘(3 a b c 3 f).
(cons ‘(a) (a b c d)
Pair: (1 . 2) or (1 . (2 . (3 . (4 . 5))))
16
Logic Operations
(not (boolean-expr) )
(not (< x 1 ) ) x >= 1
(and (boolean-expr1) (boolean-expr2))
(and (# t) ( > 3 2 ) ) #t && #t == #t
(or (boolean-expr1) (boolean-expr2))
(or (= 3 2 ) (< 0 1 ) ) #f || #t == #t
17
Control Constructs
( if (condition) (if ( = x 2)
then-body (* x x)
else-body (- x 1)
) )
(cond (cond
( (condition) body) ( (< x 1) 10)
( (condition) body) ( (= x 2) (* x x))
… …
(else body ) ;optional (else -1)
) )
18
Scopes in Scheme
Environment: List of names and corresponding values that are valid (known) during and after the execution of a program.
Procedures and names are added to global environment after they are defined.
Local Scope: only within the let body
(let ( (name1 binded-value1)
(name2 binded-value2)
…
(namen binded-valuen)
)
body
)
Example:
(let (
( x 2 )
( y 3 )
)
( + x y ) )
19
Local scope only occurs here
Let Examples and Nested Let
(let (
(x 10)
(y 5 )
)
(let (
(x (+ 1 y))
(y (+ 2 x))
)
(* x y)
)
)
20
(let (
(x 2)
(y 3)
(z 4)
)
(let (
(x (* x x))
(y (+ x y))
(z 1)
)
(let (
(h (+ x y z))
)
(+ h 0)
)
)
)
x == 10
y == 5
x == 6
y == 12
y == 3
x == 2
y == 5
x == 4
z == 1
Result is 72
Result is 10
Converting Between Let Form and Lambda
(let (
(x 2)
(y 3)
(z 4)
)
(let (
(x (* x x))
(y (+ x y))
(z 1)
)
(+ z (* x y))
)
)
( (lambda
(x y z)
( (lambda
(x y z)
(+ z (* x y))
)
(* x x)(+ x y) 1)
)
2 3 4
)
21
Converting Between Lambda and Let Form
( (lambda
(a b c)
( (lambda
(a b c)
(+ a (* b b) (* c c))
)
(* a a) (* b c ) (+ a b c))
)
3 2 1
)
(let
(
(a 3)
(b 2)
(c 1)
)
(let (
(a (* a a))
(b (* b c))
(c (+ a b c))
)
(+ a (* b b) (* c c))
)
)
22
Data Versus Code
Symbol: a value treated as data rather than code.
Examples: “Hello” is a string, but ‘Hello is a symbol
(+ 2 3) 2 + 3, but ‘(+ 2 3) is data
Operations can be applied to symbols
Examples: (+ ‘3 ‘2 ) 3 + 2 == 5
(symbol? ‘apple) #t
(eq? ‘a ‘b) #f
‘( a b c d 1 2 3) is not treated as a form to be evaluated, but is treated as data (a.k.a. a list!!!)
23
List and Pair (Scheme)
What defines a Pair? And a list? Is ‘( ) consider a pair?
A list is a subtype of pairs and is also a special case of pairs, except for ‘( ).
What does car return?
First element of list. (car ‘(e f g)) returns e
What does cdr return?
All elements after first element. (cdr ‘(e f g)) returns ‘(f g)
What will this function return (caddr ‘(8 9 10 19 . 12))?
10
24
Recursive Procedure
Can you create a recursive procedure to find the reverse a list given without using the built-in function?
What is the size (n-1) problem in this question?
What part of the program formulates the construction of size-n problem’s solution based on the solution to the size (n-1) problem?
25
Solution
(define (reverse-list lst)
(if(null? lst)
'()
(append (reverse-list (cdr lst))(list (car lst)))
)
)
26
(reverse-list ‘(b c d e f))
(append (reverse-list ‘(c d e f)) ‘(b))
(append (append (reverse-list ‘(d e f)) ‘(c)) ‘(b))
(append (append (append (reverse-list ‘(e f)) ‘(d)) ‘(c)) ‘(b))
(append (append (append (append (reverse-list ‘(f)) ‘(e)) ‘(d)) ‘(c)) ‘(b))
(append (append (append (append ‘(f) ‘(e)) ‘(d)) ‘(c)) ‘(b))
(append (append (append ‘(f e) ‘(d)) ‘(c)) ‘(b))
(append (append ‘(f e d)) ‘(c)) ‘(b))
(append ‘(f e d c) ‘(b))
‘(f e d c b)
Recursive Procedure
Can you create a recursive procedure to find and remove a given element in a list given an index?
What is the size (n-1) problem in this question?
What part of the program formulates the construction of size-n problem’s solution based on the solution to the size (n-1) problem?
27
Solution
(define (remove-element lst element)
(cond
((null? lst) lst)
((= (car lst) element) (cdr lst))
(else (append (list(car lst)) (remove-element (cdr lst) element)))
)
)
28
(remove-element ‘(3 7 6 4 12 9) 4)
(append ‘(3) (remove-element ‘(7 6 4 12 9) 4 ))
(append ‘(3) (append ‘(7) (remove-element ‘(6 4 12 9) 4)))
(append ‘(3) (append ‘(7) (append ‘(6) (remove-element ‘(4 12 9) 4))))
(append ‘(3) (append ‘(7) (append ‘(6) ‘(12 9))))
(append ‘(3) (append ‘(7) ‘(6 12 9)))
(append ‘(3) ‘(7 6 12 9))
‘(3 7 6 12 9)
Recursive Procedure
Write your own custom append procedure to combine 2 list into one.
What is the stopping condition and the return value at the stopping condition.
What is the size (n-1) problem in this question?
What part of the program formulates the construction of size-n problem’s solution based on the solution to the size (n-1) problem?
29
Ackermann function
(define (Ackermann s t) ; size-n problem
(cond
((= s 0) (+ t 1)) ; stopping condition and return value
((= t 0) (Ackermann (- s 1) 1)) ;
(else (Ackermann (- s 1) (Ackermann s (- t 1))))))
What are the size-m problems?
What are the steps to construct the size-n problem solution?
30
Higher-Order Functions
What are higher-order function?
Functions that take another procedure name as an argument or return a procedure
Scheme support which of the higher-order functions?
Mapping, Reduction, and Filtering
Do you know how to apply mapping to a list?
(map (lambda (x) (+ x 1) ) ‘(1 2 3 4))
31
Reduce
(define reduce
(lambda (op base x) ;passing by name
(if (null? x)
base
(op (car x) (reduce op base (cdr x))))))
Do you know how to use reduce?
(reduce + 0 (map (lambda (x) (* x x)) '(1 2 3 4)))
30
(reduce - 1 (map (lambda (x) (+ x 1)) '(1 2 3 4)))
-1
32
Filter
(define filter (lambda (pred a-list)
(if (null? a-list)
'()
(if (pred (car a-list))
(cons (car a-list) (filter pred (cdr a-list)))
(filter pred (cdr a-list))))))
The elements that don’t meet the predicate are filtered out (removed) from the list.
Example:
(filter (lambda (x) (x < 20) ) ‘(1 20 30 40 100 14 22 17 2 1000))
(1 14 7 2)
(filter (lambda (x) (< x 1000) ) (map (lambda(x) (* x x))'(1 20 30 40 100 14 22 17 2 1000)))
(1 400 900 196 484 289 4)
33
Prolog Basics
Variables are uppercase and data (constants) are lowercase.
Fact (axiom) about objects and their relationship: father_of(bill,kate). Bill is the father of Kate.
Rules extend facts: parent_of(X,Y): mother_of(X,Y); father_of(X,Y).
Questions about objects and their relationship: ?- parent_of(X, kate). bill.
Atom: non-numerical constant that cannot be split into smaller component.s
34
Types of Symbols
Common Symbols: (What do they denote?)
Semi-colon ( ; ) or
Comma ( , ) and
Period ( . ) end of statement
Underscore ( _ ) anonymous variable (don’t care)
35
Prolog
What type of passing mechanism does Prolog use?
Pass by reference.
A goal and a fact unify, if
their predicates are the same.
their arities are the same.
their corresponding arguments match.
36
Defining Facts
37
Syntax for facts:
relationship(object, ..., object).
predicate
(functor)
arguments
# arguments = arity
weather(tempe, winter, warm).
weather(tempe, summer, hot).
weather/3
grandmother_of(jane, conrad).
grandmother_of/2
Notation: we use predicate/arity to refer to a set of facts or rules.
Rules
A rule states a general relationship, normally uses variables as arguments, that may be used to conclude a specific fact or another rule.
Syntax of rules:
relationship(object, ..., object) :- relationship(object, ..., object).
head or conclusion neck or if body or condition
A fact is a special case of a rule: a rule without the body!
Examples:
dad(X, Y) :- father(X, Y). /* synonym */
child(Y, X) :- father(X, Y).
parent(X, Y) :- mother(X, Y); father(X, Y). /* ";" = "or" */
grandmother(X, Y) :- mother(X, Z), parent(Z, Y). /* "," = "and" */
38
List and Pair (Prolog)
How are pairs defined?
Pair is defined by [ a | b] or [ a | [ b | [c | [ ] ] ] ]
What is the output of the rule:
?- member(3, [1 | [2 | 3]]).
no
?- member(3, [1 | [2 | [3 | []]]]).
true? yes
?- member([1 | 2], [[1 | 2], 2]).
true? yes
How are Lists defined?
List is defined by [ ] or [ a b c ]
[ H | T ] as member predicate where H is car and T is cdr.
39
4 Step Recursion
Identify size-n problem;
Find the stopping condition and the return value at the stopping condition;
Place the stopping rule before the recursive rule.
Identify size-m (e.g., m = n-1) problem and assume it will return the solution;
Construct the size-n problem solution based on the assumed size-m solution.
40
Recursive Rule(Prolog)
41
Can you write a recursive rule to determine if 2 nodes are connected?
/* the list of edges in a directed graph: */
edge(a,b).
edge(a,c).
edge(b,d).
edge(c,d).
edge(c,f).
edge(d,e).
edge(f,g).
edge(g, h).
edge(i,j).
a
b
c
d
e
f
g
h
i
j
Recursive Rule(Prolog)
42
Write a recursive rule to find the distance between 2 nodes that are connected?
/* the list of edges in a directed graph: */
edge(a,b,10).
edge(a,c,5).
edge(b,d,6).
edge(c,d,7).
edge(c,f,8).
edge(d,e,5).
edge(f,g,3).
edge(g,h,20).
edge(i,j,15).
a
b
c
d
e
f
g
h
i
j
Solution
connected(X,Y):- edge(X,Y); edge(Y,X). % Base case – one edge apart
connected(X,Y):- edge(X,Z), connected(Z,Y). % Turn size n into n - 1
% Similar base case/size-n
distance(X,Y,D):- edge(X,Y,D); edge(Y,X,D).
distance(X,Y,D):- edge(X,Z,A), distance(Z,Y,B), D is B + A.
43
Recursion Example (Factorial)
factorial(0,1) :- !, /* This cut !” has nothing to do with factorial */
/* It removes backtrack points and reduce search options*/
write('Completed').
factorial(N,F) :-
N>0,
N1 is N-1, /* Size n becomes size n – 1 */
factorial(N1,F1),
F is N * F1.
Change for a dollar
This simple Prolog program checks or generates change adding up to a dollar consisting of half-dollars, quarters, dimes, nickels, and pennies.
change(H, Q, D, N, P) :-
member(H,[0,1,2]), % Half-dollars member(Q,[0,1,2,3,4]), % quarters member(D,[0,1,2,3,4,5,6,7,8,9,10]) , % dimes member(N,[0,1,2,3,4,5,6,7,8,9,10,11,12,13, 14,15,16,17,18,19,20]), % nickels
S is 50*H + 25*Q +10*D + 5*N,
S =< 100,
P is 100-S.
Member Predicate: Example
not rule Using Cut
not(X) :- X, !, fail. % what happen if “!” is not used?
not(_).
If X is true, cut will be executed, and fail will be executed too, which will fail.
If X is false, cut and fail will not be executed, and thus, the next not(X) clause will be executed. As it has no condition. It always succeed.
Anonymous variable is used to prevent a “singleton” variable warning.
Calvin Cheng (CC) - I"m not sure we'll get to this point. Please remain students to check with their instructor.
/docProps/thumbnail.jpeg