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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- chapter 5 euler circuits
- decision tree analysis in litigation the basics
- process name 232 223f underwriting punch list
- decision making in the board room
- active learning techniques and descriptions
- dayton regional stem center science technology
- the ben franklin t
- cse 373 topics covered post midterm july 24 august 16
Related searches
- ar 600 20 dated 24 july 2020
- july 16 holidays and observances
- june july august calendar printable
- june july august calendar template
- ar 600 20 24 july 2020
- printable june july august calendar
- june july august calendar 2020
- 90 days from july 24 2017
- july and august 2020 calendar
- june july august 2020 calendar
- printable june july august 2020
- july and august printable calendar