Transcript cs1311lecture30wdl

Announcements
Review problems
Review Outline
Online Survey
http://www.coursesurvey.gatech.edu
Java vs. Pseudocode
• Problems will be labeled with requirements
– Java
– Pseudcode
• Focus is not on syntax
Taking the Final
•
•
•
•
•
•
•
•
•
Read .announce
Travel light
Don’t be late
No calculators, cell phones, laptops, implants, neural
networks, etc.
Use pencil (bring an eraser!)
Look over test before starting
Ask questions
Pace yourself/Spend 1/nth of the time on a question
Do easier questions first
Review Problems
• What is the Big O?
i <- N
j <- 1
loop
exitif(i <= 0)
loop
exitif(j > M)
j <- j + 1
endloop
i <- i - 1
endloop
Review problems
• Circle and Identify the 3 parts of recursion:
Function Fact returnsa Num(N iot in Num)
if(N = 0) then
Fact returns 1
else
Fact returns N * Fact(N - 1)
endif
endfunction // Fact
Review problems
• Circle and Identify the 3 parts of recursion:
Function Fact returnsa Num(N iot in Num)
Check for
if(N = 0) then
termination
Fact returns 1
else
Fact returns N * Fact(N - 1)
endif
endfunction // Fact
Call self
Move one
step closer
Review Problems
• Recall that a leaf is a node in a binary tree with no
children.
• Write a module that when passed a pointer to a
binary tree will return the number of leaves.
• The module should use recursion
Leaves
Function Leaves returnsa Num
(current iot Ptr toa TNode)
if(current = NIL) then
Leaves returns 0
elseif(current^.left = NIL AND
current^.right = NIL) then
Leaves returns 1
else
Leaves returns Leaves(current^.right) +
Leaves(current^.left)
endif
endfunction // Leaves
Review Problems
• Write a module to convert an unsorted linked list to a
sorted linked list.
• Use data structure conversion as opposed to a sort
algorithm such as Bubble Sort or Merge Sort
Solution
• Recall that for this type problem you will typically
need three modules:
– A standard linked list AddInOrder module
– A modified linked list traversal module
• modified to keep track of pointer to new list
– A startup module
Review problems
Algorithm Pain
a,b,c iot Char
a <- ‘b’
b <- ‘c’
c <- ‘a’
Agony(c,a,’b’)
print(a,c,b)
b <- funky(a,c)
print(a,b,c)
endalgorithm
Procedure Agony(a iot in/out Char,
b iot out Char,
c iot in Char)
t iot Char
if(c = ‘c’) then
c <- ‘d’
t <- b
b <- a
a <- t
else
b <- a
a <- ‘b’
endif
endprocedure
Function funky returnsa Char
(x,y isoftype in Char)
if(x = y) then
funky returns ‘a’
else
funky returns ‘b’
endif
endfunction
Review problems
• Write a vector class
• It should be generic and support (at least) the
following methods in the public section
• AddToEnd
• AddAt(nth)
• Remove(nth)
• Size
• Get(nth)
class Node
{
Object data;
Node next;
public Node(Object data)
{
this.data = data;
next = null;
}
}
class Vector
{
private Node head;
int count;
public Vector()
{
head = null;
count = 0;
}
public int size()
{
return count;
}
public void addToEnd(Object datain)
{
if(head == null)
{
head = new Node(datain);
count++;
}
else
{
addToEnd (head, datain);
}
}
private void addToEnd(Node cur, Object datain)
{
if(cur.next == null)
{
cur.next = new Node(datain);
count++;
}
else
{
addToEnd(cur.next, datain);
}
public void addAt(int nth, Object datain)
// First element is numbered 0
if(head == null || nth == 0)
{
Node temp = new Node(datain);
temp.next = head;
head = temp;
count++;
}
else
{
addAt(head, nth, datain, 1);
}
private void addAt(Node cur, int nth,
Object datain, int position)
{
if(cur.next == null || nth == position)
{
Node temp = new Node(datain);
temp.next = cur.next;
cur.next = temp;
count++;
}
else
{
addAt(cur.next, nth, datain, position + 1);
}
)
public void remove(int nth)
{
if(head != null)
{
if(nth == 0)
{
head == head.next;
count--;
}
else
{
remove(head, nth, 1);
}
}
} // remove
private void remove(Node cur, int nth,
int position)
{
if(cur.next != null)
{
if(nth == position)
{
cur.next = cur.next.next;
count--;
}
else
{
remove(cur.next, nth, position + 1);
}
}
}
public Object get(int nth)
{
return get(head, nth, 0);
}
private Object get(Node cur, int nth, int pos)
{
if(cur == null) {
return null;
}
else if(nth == pos) {
return cur.data;
}
else {
return get(cur.next, nth, pos + 1);
}
}
} // Vector
Questions?
Review
• The Algorithmic Model
– Algorithm defined
– Properties of good algorithms
– How to describe algorithms
– Relating problems to algorithms to programs
(hierarchy needed)
Review
• View of programming languages/algorithms
– Data vs. instructions
– Built-in vs. user-defined
– Complex vs. atomic
• Data
– Type vs. variable (Declaration and Initialization
of variables)
– The 4 atomic built-in types (Num, Characters,
Booleans, Pointers)
– The complex built in type String
Review
• Operations
– Assignment
– Arithmetic
• +, -, x, /, div, mod
• Precedence rules
• Using parenthesis to modify precedence
– Input and output
• Print
• Read
Review
• Conditionals
– Purpose & defined
– Relational operators (<, >, =, <>, >=, <=)
– Boolean operators (AND, OR, NOT)
– Boolean expressions (Simple & Complex)
– Control flow of the if-then-else statement
– Elseif as shorthand
• Writing an algorithm (how to begin)
Review
• Program maintenance
• Software Engineering facts about program
cost
• Documentation
• Benefits of Constants
Review
• Procedural Abstraction
• Why modularity (Benefits)
• Need for interface
• Scope of variables
• Contract (Pre, post, and purpose statements
for every module)
• Information flow – in, out, in/out
• Parameters intro (In, out, in/out)
• Types of modules
Review
• Procedure
• Rules when to use a procedure
• Declaration
• Function
• Rules when to use a function
• Declaration
• Returning values via the “returns”
Review
• Module invocation
• Parameters
• Formal vs. actual
• Parameter matching
• How parameters work (In, Out, & In/out)
• Tracing
• Activation stack
• Frames
• Rules of parameter matching (In, Out, & In/out)
• Examples
Review
• Recursion (Intro)
• Purpose – repetition
• Characteristics – calls itself, terminating
condition, move closer
• 2 forms – final action or not
• Examples
• Tracing recursive modules
• Recursion (Advanced)
• Mutual recursion
• Design by Contract
Review
• Data Abstraction
– Records
• Declaring records
• Creating variables of record type
• Accessing fields of a record variable (the ‘.’
operator)
• Avoid anonymous types
• Combining records (records inside records)
Review
• Static vs. dynamic memory/data
• Pointers
• Simple example of ptr toa num
• Following the pointer via the ‘^’ operator
• Dynamic data structures
• Linked Lists
• Defined/properties
• Proper Record declaration
• Accessing information in a linked list via
pointers
Review
• Linked Lists (continued)
– Adding nodes
– Simple – no recursion (To front)
– Insertion recursive method
– To end
– In middle (when sorted)
– Deleting nodes
• Simple - no recursion (From front)
• Deletion recursive method
Review
• Stack
– Defined/properties
– Push
– Pop
– Tracing changes (example of algorithm using
push & pop)
Review
• Queue
• Defined/properties
• Enqueue
• Dequeue
• Tracing changes (example of algorithm using
enqueue and dequeue)
• Trees
• Defined/properties
• Binary trees (Record declaration)
• Binary search trees
Review
• Trees (Continued)
• Recursive insertion in BST
• Deleting from BST (conceptually)
• Graphs
• Defined/properties
• Record definition
Review
• Static data structures
• Arrays
• Defined
• Need of constants
• Accessing elements via the index
• Multi-dimensional arrays (Declaring and
accessing)
Review
• Iteration
• Defined, use for repetition
• How looping works
• Loop
• Endloop
• Exitif
• Combined types
• Examples – array of lists, list of array, tree of
lists, etc.
Review
• Methods of Accessing Data Structures
• Traversal
• Lists
• Recursive on lists
• Iterative on lists
• Trees
• In-order
• Pre-order
• Post-order
• Miscellaneous Traversals
• (Right before Left)
Review
• Breadth-first vs. depth- first
• Arrays
• Iterative on arrays
• Recursive on arrays
• Search
• Linear
• Recursive on lists
• Traversal-search on binary tree (not BST)
• Linear, iterative search on array
Review
• Binary, recursive search on BST
• Binary, iterative search on sorted array
• Sort
• Bubble sort
• Merge sort
Review
• Conversion
• Defined
• Helper module advantages
• List to Tree
• Array to List
• Tree to List
Review (Java/OO)
• Syntax
– Operators
– Operator overloading
– Assignment statements
– Control structures
• if else
• case
– Iterative structures
• while
• do while
• for
• Data Types
– Primitives
– References
• class
• attribute
– access modifiers
• public/private
– static
– final/constants
– initialization
Review (Java OO)
• constructors
– access modifiers
– default
– chaining
– overloading
• methods
– access modifiers
• public/private
–
–
–
–
–
–
static
return type/void
main method
accessors
modifiers
overloading
Review (Java OO)
• object/instance
• Inheritance
– Redefinition (Overriding)
– Extension
– super class
– subclass
– abstract
• Polymorphism
•
Compilation
– reference type checking
– method checking
– Type mismatch checking
• Run Time
– interpreting
– dynamic binding
– Java virtual machine
Review
• Algorithm Cost and Complexity
• Measuring performance (space & time)
• Measuring work (counting instructions)
• Best, worst, average
• Measuring work growth
• O() notation
• Complex O() rules (drop constants, keep
dominant term, etc.)
Review
• Analysis
– Linear vs. binary search
– Traversals
– Data structures
• Compare on traversals, search, & insert
– Bubblesort vs. mergesort
• Exponential growth
– Hanoi, Monkey tiling, wise peasant
• Reasonable vs. unreasonable
Feedback
• What did you like about the course?
Feedback
• What did you dislike about the course?
Feedback
• What would you differently?
Questions?
Thanks for taking CS1311!
Good luck on Finals.