CIT 594Basic contentTypes of CollectionThe Collections hierarchyUniformity through interfacesCreating lists in JavaA short list of categoriesExample recursive algorithmsExample backtracking algorithmExample greedy algorithmTime and spacey = x2 + 3x + 5, for x=1..20The EndCIT 594Basic contentCIT 594 is a continuation of CIT 591Java will be used throughoutHowever, CIT 594 is not primarily a course about JavaTopics:Data StructuresSupplied by JavaHow to create your ownAlgorithmsA sampling of some better-known algorithmsAnalysis of algorithmsSimple algebra is requiredTypes of CollectionA collection is a structured group of objectsJava supplies several types of Collection:Set: cannot contain duplicate elements, order is not importantSortedSet: like a Set, but order is importantList: may contain duplicate elements, order is importantJava also supplies some “collection-like” things:Map: a “dictionary” that associates keys with values, order is not importantSortedMap: like a Map, but order is importantThe Collections hierarchyUniformity through interfacesMuch of the elegance of the Collections Framework arises from the intelligent use of interfacesFor example, the Collection interface specifies (among many other operations):boolean add(Object o)boolean isEmpty()boolean remove()int size()Object[] toArray()Iterator iterator()Creating lists in Java class Cell { int value; Cell next; Cell (int v, Cell n) { // constructor value = v; next = n;} } Cell temp = new Cell(17, null); temp = new Cell(23, temp); temp = new Cell(97, temp); Cell myList = new Cell(44, temp);44 97 23 17myList:A short list of categoriesAlgorithm types we will consider include:Simple recursive algorithmsBacktracking algorithmsDivide and conquer algorithmsDynamic programming algorithmsGreedy algorithmsBranch and bound algorithmsBrute force algorithmsRandomized algorithmsExample recursive algorithmsTo count the number of elements in a list:If the list is empty, return zero; otherwise,Step past the first element, and count the remaining elements in the listAdd one to the resultTo test if a value occurs in a list:If the list is empty, return false; otherwise,If the first thing in the list is the given value, return true; otherwiseStep past the first element, and test whether the value occurs in the remainder of the listExample backtracking algorithmTo color a map with no more than four colors:color(Country n):If all countries have been colored (n > number of countries) return success; otherwise,For each color c of four colors,If country n is not adjacent to a country that has been colored cColor country n with color crecursively color country n+1If successful, return successIf loop exits, return failureExample greedy algorithmSuppose you want to count out a certain amount of money, using the fewest possible bills and coinsA greedy algorithm would do this would be:At each step, take the largest possible bill or coin that does not overshootExample: To make $6.39, you can choose:a $5 billa $1 bill, to make $6a 25¢ coin, to make $6.25A 10¢ coin, to make $6.35four 1¢ coins, to make $6.39For US money, the greedy algorithm always gives the optimum solutionTime and spaceTo analyze an algorithm means:developing a formula for predicting how fast an algorithm is, based on the size of the input (time complexity), and/ordeveloping a formula for predicting how much memory an algorithm requires, based on the size of the input (space complexity)Usually ti me is our biggest concernMost algorithms require a fixed amount of spacey = x2 + 3x + 5, for x=1..20The
View Full Document
Unlocking...