D.4 Advanced Program Development

Recursion

\
* A method where the solution to a problem depends on the solutions to smaller instances of the same problem. It calls itself. 

Applications of Recursion

* Not really used in practice. They are difficult for humans to follow in order to understand and maintain code
* Only used when they can provide an elegant solution
* Fibonacci given a number
* Factorial or power of a given number
* Print a binary tree
* Reverse a string

Object Refrence

* A reference to an object in memory
* Used in java by the dot notation to access the fields and methods
* Person p = new Person();
* p.setName(“Fred”)
* p = object reference

Features of the ADT List

* A list is a data structure that can grow in size at runtime as memory is allocated dynamically
* A list is a generic ADT (abstract data type) and usually has a few basic methods
* They can be indexed to allow the program to add and remove elements from specified positions

Generic ADT Methods

* Add
* Size
* Get
* isEmpty
* Remove

Stacks

* First element added to the stack sits on the bottom
* Last one added is the first one removed
* LIFO
* The add method is a push and the remove a pop

Queues

* Elements are added to the end of the queue and removed from the front
* FIFO
* Add method is an enqueue and remove is dequeue

Methods and Algorithms for Manipulating Lists and Object References

* add (to front and back)
* insert (in order)
* delete
* list (print)
* isEmpty
* isFull

When are stacks used in operating systems?

* To keep track of instructions and which to execute next
* Hence stackOverFlow error
* Also used to keep track of events in the software so the undo button can be used

Binary trees

* Ordered list of elements where elements of a lower number or letter are stored to the left of the node and elements of a higher number or letter are stored to the right of the node
* Have a root at the top - search start point
* Recursion used to print them
* Can traverse in pre-order, post-order, and in-order

Code Naming Conventions

* Start class names with a capital letter
* Objects with a lowercase letter
* Use meaningful names for the fields and variables
* Indent the code
* Inline annotaitons

Why are naming conventions important?

* Code is read more often than written
* If all code is written the same it is easy to read
* Cuts down time on maintenance and reduces the chance of error through misinterpretation
* Saves time, money, and effort
* Makes it easy to read and update