CSE 373: Topics Covered (post-midterm: July 24 – August 16 ...



CSE 373: Topics Covered (post-midterm: July 24 – August 16, 2017)(Note that this is only a big-picture overview – it leaves out a lot of detail)GraphsGeneral knowledge & terminologyMathematical representation( G = (V, E), etc.)Undirected & Directed GraphsSelf EdgesWeightsPathsCyclesConnectednessTrees as graphsDAGsDensity & SparsityGraph data structuresAdjacency MatrixAdjacency ListWhen to use which and whyGraph algorithmsTopological SortWhat it isNecessary conditionsTwo algorithms for topological sortTraversalsDepth First Search (DFS)Breadth First Search (BFS)When to use whichShortest pathFor unweighted graphsFor weighted graphs (Dijkstra's algorithm)Two approaches to Dijkstra's, when to use whichSpanning TreesApproach #1: DFSApproach #2: Add acyclic edgesMinimum Spanning Tree (MST)Prim's AlgorithmKruskal's AlgorithmSorting AlgorithmsTerminologyStable sortIn-place sortExternal sortComparison SortInsertion SortSelection SortHeapsort (including in-place version)Merge Sort (including time- & space-saving versions)Quicksort (including different pivot rules and in-place quicksort)Using cutoffsOther SortsConditions that let you use themBucket Sort (a.k.a. Bin Sort)Radix SortHow to sort massive dataWhat algorithms make the most sense and whyHow to sortFor each algorithm:Worst- best-case scenarios & run timesOther pro's/con's of eachWhen to use whichGeneral Algorithms KnowledgeAnalyzing algorithmsCorrectness (less emphasis here)EfficiencySeveral algorithm typesGreedy algorithmsDynamic programming Divide-and-conquerP vs NPSoftware Design: Preserving AbstractionsAbstraction (what it is, why it's important)Memory representation (call stack, heap space, program counter, etc.)Aliasing and mutations, how they're problematicCopy-inCopy-outImmutability (e.g. using the 'final' keyword)Deep copies & deep immutability (and why)ParallelismTerminologyParallelism vs ConcurrencyShared memory & race conditionsThreads / Fork-join programmingHow to use in Java (subclass, create 'thread' object, start(), join())What happens under the hoodDivide-and-conquer approach and whyMap & ReduceAnalysis (including Amdahl's Law)Design decisionsAbility to ask questions about problem to inform solutionHow to analyze/justify a decisionTime efficiencySpace efficiencyHow parallelizable (in a few cases)Fluency with data structures & algorithms concepts/knowledge Purposes a data structure is well-suited for and whyAvailable operationsEfficiency of basic operationsSpace usage (conceptually)Pro's and con's of different algorithmsCSE 373: Topics Covered (pre-midterm: June 19 – July 19, 2017) (Note that this is only a big-picture overview – it leaves out a lot of detail)Abstract Data Types (ADTs) and Data StructuresStacks and Queues Linked list implementationArray implementations (including circular arrays)Asymptotic AnalysisBig-O of code snippetsInductive ProofsRecurrence Relations (and when to apply them)Formal definition of Big-OBig-O and -Omega, Theta, little-o and -omega Amortized AnalysisDictionary ADTHash TablesHash functions, hash values, and indexinginsert, find, removeCollisionsSeparate chainingOpen addressing / probingLinear probingQuadratic probingDouble hashingRehashingGeneric treesTerminologyBinary treesTerminologyRepresentationCalculating the heightTraversalsBinary Search Tree (BST)findinsertdelete (3 cases)buildTreeTerminology (e.g. successor, predeccessor)Balanced vs unbalanced treesAVL TreesBalance conditionsAVL balance conditionRotationsinsert (4 cases)Priority Queue ADTHeapsinsert & deletePercolations Array representation/implementationbuildTree (client version and Floyd's Method /heapify)d-heapsFor each data structureWays to implementPros, Cons, and other reasons to choose one over the other ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download