Samenvatting
Advanced Programming Summary
- Instelling
- Erasmus Universiteit Rotterdam (EUR)
Advanced Programming Summary
[Meer zien]Voorbeeld 6 van de 86 pagina's
Voorbeeld 6 van de 86 pagina's
In winkelwagengesponsord bericht van onze partner
Gekoppeld boek
Titel boek:
Auteur(s):
- Uitgave:
- ISBN:
- Druk:
Voorbeeld van de inhoud
Advanced Programming SamenvattingIndex
1 Chapter 15 3
1.1 An Overview of the Collections Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Arrays vs. ArrayList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Arrays/ArrayList vs. LinkedList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Linked Lists Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.1 Example: Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.2 Programming Tip 15.1: Use Interface References to Manipulate Data Structures . . . . . . . . 16
1.6 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.7 Stacks, Queues, and Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7.1 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7.2 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.7.3 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8 Stacks and Queue Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.8.1 Example: Polish calculator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.8.2 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2 Chapter 4: Algorithm Analysis 29
2.1 Experimental Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.1.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.1.2 Counting Primitive Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.3 Measuring Operations as a Function of Input Size . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.4 Focusing on the Worst-Case Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2 The Seven Functions Used in This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.1 The Constant Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.2 The Logarithm Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.3 The Linear Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.4 The N-log-N Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.5 The Quadratic Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.6 The Cubic Function and Other Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.7 The Exponential Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2.8 Comparing Growth Rates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3 Asymptotic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.1 The Big-Oh Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.3.3 Big-Omega . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3.4 Big-Theta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3.5 Comparative Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3.6 Examples of Algorithm Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 Chapter 5: Recursion 44
3.1 Illustrative Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.1.1 The Factorial function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.1.2 Drawing an English Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.3 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.1.4 File Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 Analyzing Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2.1 Computing Factorials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2.2 Drawing an English Ruler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
1
,INDEX
3.2.3 Performing a Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2.4 Computing Disk Space Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3 Further Examples of Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.1 Linear Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.2 Recursive Algorithms for Computing Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3.3 Binary Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3.4 Multiple Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4 Designing Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5 Recursion Run Amok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5.1 An Inefficient Recursion for Computing Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . 60
3.5.2 An Efficient Recursion for computing Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . . 60
4 Chapter 6: Stacks, Queues and Deques 61
4.1 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.1 A simple Array-Based Stack Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1.2 Implementing a Stack with a Singly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.1.3 Reversing an Array Using a Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.1.4 Matching Parentheses and HTML Tags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.1.5 Matching Tags in a Markup Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.1 Array-Based Queue Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.2 Implementing a Queue with a Singly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2.3 A Circular Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 Double-Ended Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.1 Implementing a Deque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.3.2 The Double-Ended Queue (Deque) ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5 Chapter 7: List and Iterator ADTs 76
5.1 Array List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.1.1 Amortized Analysis of Dynamic Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.1.2 Java’s StringBuilder class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2 Positional Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2.1 Positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.2.2 The Positional List Abstract Data Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.3 Doubly Linked List Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.3 Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
2
,1 CHAPTER 15
1 Chapter 15
1.1 An Overview of the Collections Framework
Each interface type is implemented by one or more classes. Each collection class implements an interface from a
hierarchy.
java.util.Collection → Collection is an interface.
Each class is designed for a specific type of storage.
Figuur 1: Interfaces and Classes in the Java Collections Framework
A collection groups together elements and allows them to be retrieved later.
When you need to organize multiple objects in your program, you can place them into a collection. The collection
interface has methods for adding and removing elements. Because all collections implement this interface, its methods
are available for all collection classes. For example, the size method reports the number of elements in any collection.
A list is a collection that remembers the order of its elements.
Unlike an array list, a linked list allows speedy insertion and removal of elements in the middle of the list.
A list is a collection that remembers the order of its elements.
You use a list whenever you want to retain the order that you established.
Order matters: On your bookshelf, you may order books by topic. A list is an appropriate data structure
for such a collection because the ordering matters to you.
ArrayList → Stores a list of items in a dynamically sized array
LinkedList → Allows speedy insertion and removal of items from the list
Order does not matter: A mail-order dealer of books. Without browsing the shelves, there is no need to order
books by topic. Such a collection without an intrinsic order is called a set.
HashSet → Uses hash tables to speed up finding, adding and removing elements
TreeSet → Uses a binary (search) tree to speed up finding, adding and removing elements.
A set is an unordered collection of unique elements.
Because a set does not track the order of elements, it can arrange them in a way that speeds up the operations
of finding, adding, and removing elements.
− Hash tables
− Binary search trees
3
,1 CHAPTER 15
Another way of gaining efficiency in a collection is to reduce the number of operations.
A stack remembers the order of its elements, but it does not allow you to insert elements in every position. You can
add and remove elements only at the top.
In a queue, you add items to one end (the tail) and remove them from the other end (the head).
E.g. You could keep a queue of books, adding required reading at the tail and taking a book from the head whenever
you have time to read another one.
E.g. A line of people waiting for a bank teller.
A map keeps associations between key and value objects.
A map manages associations between keys and values. Every key in the map has an associated value. The map
stores the keys, values and the associations between them.
E.g. Consider a library that puts a bar code on each book. The program used to check books in and out needs to
look up the book associated with each bar code.
Keys → Provides an easy way to represent an object (such as a numeric bar code).
Values → The actual object that is associated with the key.
List, Queueand Set are specialized interfaces that inherit from the Collection interface. All share the following
commonly used methods.
4
,1 CHAPTER 15
Tabel 1: The Methods of the Collection Interface
The ArrayList class implements the Collection inter-
Collection<String> coll = new ArrayList<String>();
face
The TreeSet class also implements the Collection in-
coll = new TreeSet<String>();
terface
Gets the size of the collection. n is now 0.
int n = coll.size();
Adds elements to the collection
coll.add("Harry");
coll.add("Sally");
Returns a string with all elements in the collection.
String s = coll.toString();
s is now "[Harry, Sally]"
Invokes the toString method and prints [Harry, Sally]
System.out.println(coll);
Removes an element from the collection, returning
coll.remove("Harry");
false if the element is not present. b is false.
boolean b = coll.remove("Tom");
Checks whether this collection contains a given ele-
b = coll.contains("Sally");
ment. b is now true.
You can use the "for each"loop with any collection.
for (String s : coll)
This loop prints the elements on separate lines.
{
System.out.println(s);
}
You use an iterator for visiting the elements in the
Iterator<String> iter = coll.iterator()
collection
5
, 1 CHAPTER 15
1.2 Arrays vs. ArrayList
Arrays: ArrayList :
− Static in size − Dynamic in size
− Slightly better performance (hardly noticeable, − Slightly lower performance (due to indirection
more accentuated when using primitive types) methods as add() and get())
− Stores primitive types (int, double, etc) (in ad- − Cannot store primitive types (uses autoboxing)
dition to objects)
− Uses iterators (iterator() from
− Uses for loop or for each loop to iterate through java.util.Collection (allows next()
array and remove()) or list iterator() from
java.util.List (allows next() and previous(),
− Type safe (can store only objects of a certain add() and remove())
type)
− Type safe (by means of generics)
− Length given by .length public field
− Length given by size() public method
− Can be multidimensional
Integer arrayobject[][] = new − Is always unidimensional
Integer[3][2]; ArrayList<Integer> arraylist = new
ArrayList<Integer>()
Conclusion: use for fixed size arrays.
Conclusion: use for variable size arrays.
1.3 Arrays/ArrayList vs. LinkedList
Arrays/ArrayList LinkedList
− Preserves order − Preserves order
− ArrayList uses an array in the implementation − Implemented as a doubly linked list
− (+) Random access − (-) Sequential access
− (-) Inefficient for add/remove elements (element − (+) Efficient for add/remove elements (no ele-
shifting) ment shifting)
− ArrayList implements the List interface − Implements List and Dequeue interfaces
Conclusion: fast access to static sequential data. Conclusion: store dynamic sequential data
1.4 Linked Lists
A linked list is a data structure used for collecting a sequence of objects that allow efficient addition and removal of
elements in the middle of the sequence.
Linked lists use references to maintain an ordered list of ’nodes’.
The ’head’ of the list reference the first node. Each node has a value and a reference to the next node.
Figuur 2: A Linked List
They can be used to implement
− A List Interface
6
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper studenteconometrics. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €6,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 67474 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen