CIT 594 Quick OverviewPointers and ReferencesMachine addressesC (and C++) vs. JavaReferencesData structuresA trivial exampleA more serious exampleBinary trees in JavaSize of objectsThe magic of VectorsVector’s secret trickPowerPoint PresentationSlide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Types of AlgorithmsAlgorithm classificationA short list of categoriesAnalysis of AlgorithmsTime and spaceWhat does “size of the input” mean?Characteristic operationsExact valuesHigher-level languagesAverage, best, and worst casesConstant timeLinear timeConstant time is (usually) better than linear timeWhat about the constants?Simplifying the formulaeBig O notationBig O for subset algorithmCan we justify Big O notation?y = x2 + 3x + 5, for x=1..10y = x2 + 3x + 5, for x=1..20Common time complexitiesThe EndJan 12, 2012CIT 594 Quick OverviewJan 12, 2012Pointers and ReferencesMachine addressesComputer memory consists of one long list of addressable bytesA pointer is a data item that contains an address3FA71CF23FA71CF33FA71CF43FA71CF53FA71CF63FA71CF73FA71CF83FA71CF93FA71CFA3FA71CFB3FA71CFC3FA71CFD3FA71CFE3FA71CFF3FA71D003FA71D01::3FA71CF6• A reference is a data item that contains an address3FA71CF6• C has pointers, but Java has references• So what’s the difference?C (and C++) vs. JavaIn C you can dereference (follow) a pointerIn Java you can dereference (follow) a referenceIn C you can assign one pointer variable to anotherIn Java you can assign one reference variable to anotherIn C you can determine whether one pointer is larger than, equal to, or smaller than another pointerIn Java you can determine whether one reference is equal to another referenceIn C you can create a pointer to anythingIn Java you can have references to objectsIn C you can do integer arithmetic on pointersReferencesAn Abstract Data Type (ADT) has a set of values and a set of operations on those valuesPointers and references have the same set of values (memory addresses)Pointers have more defined operations than referencesPointers are more flexible and more general than referencesReferences are safer than pointers (from error or malicious misuse)References allow automatic garbage collection (pointers don’t)A (non-abstract) Data Type also has an implementationThe implementations of pointers and references are similarJava references carry information about the thing referenced; in C, it’s up to the compiler to figure out what it canData structuresBasically, pointers and references are the same thing; they point to (refer to) something else in memoryA Data Structure is a description of how data is organized in memoryMany (not all) data structures are built from objects pointing/referring to one anotherUnderstanding pointers (references) is fundamental to this courseIf this course were taught in C or C++ instead of Java, all the “nuts and bolts” would be the sameThis course is in Java, but it’s not about JavaYou need to know how to create your own data structuresI will also teach some Java-specific packagesIn real life, it’s stupid to redo work that’s already been done for youA trivial exampleWe use a lot of references in Java:class Person { String name; Person spouse; Person (String n) { name = n; }}…Person john = new Person("John");Person mary = new Person("Mary");john.spouse = mary;mary.spouse = john;"John""Mary"johnnamespousemarynamespouseA more serious exampleA binary tree is a data structure in which every node (object) has zero, one, or two children (references to other nodes)Arithmetic expressions can be represented as binary treesTo evaluate an arithmeticexpression:If it is a leaf, return its valueOtherwise, evaluate its two subtrees, and perform the indicated operation+/12nullnull4nullnull7nullnullA binary tree representing thearithmetic expression 12/4+7Binary trees in Javapublic class BinaryTree { public Object value; // the information in this node private BinaryTree leftChild; private BinaryTree rightChild; // Constructors and methods...}To make binary trees as useful as possible, we make the value in a node an ObjectAs implementers of the BinaryTree class, our job is to make sure that the structure of the binary tree is always validWe don’t really care what the user puts in the value fieldSize of objectsObjects in Java have, generally speaking, a fixed sizeThe size of all primitives is knownObjects don’t actually “contain” other objects—they just have references to other objects, and a reference is 4 bytesSo what about Vectors?A Vector is like an array, but it gets bigger as you put things into itA Vector actually has two “sizes”—its capacity, which is how many references it can hold, and its size, which is how many references are in it right nowWhen you exceed the capacity of a Vector, Java creates a new Vector for youThe magic of VectorsSuppose you have two references to a Vector, and you use one of them to add elements to the VectorWhat happens if Java decides to replace this Vector with a bigger one?It looks like the second reference is a “dangling pointer,” referring to nothingThis doesn’t happen! Java protects you from this errorBut how?v1v2Vector’s secret trickA reference to a Vector is actually a reference to a reference to a VectorIn this way, the “real” reference has to be changed in only one place, and all the other, indirect references automatically workIt’s clever, but it isn’t magicv2v1Jan 12, 2012Recursion14Definitions IA recursive definition is a definition in which the thing being defined occurs as part of its own definitionExample:An atom is a name or a number A list consists of:An open parenthesis, "("Zero or more atoms or lists, andA close parenthesis, ")"15Definitions IIIndirect recursion is when a thing is defined in terms of other things, but those other things are defined in terms of the first thingExample: A list is:An open parenthesis,Zero or more Symbolic expressions, andA close parenthesisA Symbolic expression is an atom or a list16Recursive functions...er, methodsThe mathematical definition of factorial is:We can define this in Java as:long factorial(long n) { if (n <= 1) return 1; else return n * factorial(n – 1);}This is a recursive function because it calls
View Full Document
Unlocking...