1Midterm 2 Overview Fawzi EmadChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkOverview of Topics1. Data structures2. Graph algorithms3. Searching Search trees Heaps Hash tables Tries4. Sorting5. Compression2Topic – Data StructuresWhy data structures are importantTaxonomy of data structuresLinearHierarchicalGraphMaps & setsData structure examplesRelationship between elementsOperations supportedImpact on efficiencyTopic – Graph AlgorithmsTypes of graphsOperations on graphsTraversalsSpanning treesMinimal spanning treesShortest pathsImplementation methods3Topic – SearchingData structures for searchingBinary search treeHeapsMaps & hashingIndex search trees (tries)Multi-way search treesBalanced search treesImplementation & maintenanceInsert(), delete(), find()Comparing data structuresAdvantages & disadvantagesTopic – SortingApproaches to sortingComparison sortsLinear sortsProperties of sortingImplementing sortingComparing approachesAdvantages & disadvantages4Topic – CompressionApproaches to compressionHuffman encodingAlgorithmImplementationPropertiesMidterm Question FormatsMultiple choice questionsShort 1-sentence answersWrite codeApply & describe algorithms5Multiple Choice Question ExampleSorting is different from searching becauseSorting is more complexSearching is more complexSorting takes more spaceSearching takes more spaceSorting compares two items by size(circle all that apply)Short 1-Sentence Answer ExampleSorting is different from searching because(provide short 1-sentence answer)6Write CodeGiven the following Java code fragment, write code to insert into an unsorted linked list class Node {Object value;Node next;void insert ( Node n ) {… // place your code here}}void BubbleSort ( Comparable [ ] a ) {… // place your code here}Apply & Describe AlgorithmsGiven the following binary search treeDraw tree after adding 9Draw tree after deleting 5Perform postorder traversal510302 25 457Apply & Describe AlgorithmsGiven the following graphApply depth-first search, starting at 1Apply breadth-first search, starting at 1Apply Djikstra’s algorithm, starting at 1Apply Kruskal’s algorithmShow
View Full Document
Unlocking...