Course Review for Midterm Exam 1Midterm Exam 1Cpt S 223Fall 20121Cpt S 223. School of EECS, WSUMidterm Exam 1 When: Wednesday (10/10) 9:10 -10am Where: in class Closed book, closed notesCalculators will be allowed.Noother accessoriesCalculators will be allowed. No other accessories will be allowed. Comprehensive Materialfor preparation:Material for preparation: Lecture slides & in-class notes Homeworks & program assignments 2 Weiss book Cpt S 223. School of EECS, WSUSyllabus ComprehensiveTopics include:Topics include: Math introElementary data structures–array, list, stack,Elementary data structures array, list, stack, queue Asymptotic notation and complexity analysis Trees Binary Search TreesAVL TAVL TreesCpt S 223. School of EECS, WSU 3More on the test… Generally speaking, questions in the test will tend to be modeled after classtest will tend to be modeled after class room exercises and homework problems. But also expect to see someproblems. But also expect to see some new types of questions.Cpt S 223. School of EECS, WSU 4Math Review Floors, ceilings, exponents and logarithms: Definitions and manipulations Series: Definitions manipulations arithmetic and geometric seriesSeries: Definitions, manipulations, arithmetic and geometric series closed form Proofs: Know definition, components, and how to use the following Proof by inductionProof by induction Proof by counterexample Proof by contradiction RiRecursion Know definition and rules Analyze running time of recursive algorithm Tail recursion removal5Cpt S 223. School of EECS, WSUI won’t ask you questions in the test that are just C++ specificC++ Review Know definitions and how to use the following Class, method, encapsulation ,,p Constructor, destructor, accessor, mutator Reference variable (&x) and call by referenceReference variable (&x) and call by reference Copy constructor, operator overloading, operator= p Templates STL for different data structures6STL for different data structuresCpt S 223. School of EECS, WSUAsymptotic Analysis Why analyze an algorithm? TIME & MEMORYWhat do we measure and how do we measure it?What do we measure and how do we measure it? Time: Look at the worst-case input and check for dominant termsMemory: Focus on the peak memory usageLibli l i fLine-by-line analysis of a program Best-case, worst-case and average-case analysis Rate of growth: Definitions and notation (O, Ω, Θ, o, w) Proofs for specific examples (be familiar with the table approach) Properties of asymptotic notation – e.g., symmetry, transpose symmetry, transitivity, etc.7 Maximum subsequence subproblemCpt S 223. School of EECS, WSUAbstract Data Types Lists Operations: Insert, Delete, Search Implementations: vectors, singly-linked lists, double-linked lists, sentinel nodes Analysis of operations for each implementation Stacks (LIFO) Operations: Push, Pop, Top Implementations: linked-list, vector (tradeoffs) Analysis of operations for each implementation Queues (FIFO) Operations: Enqueue, dequeue Implementations: linked-list, vector (tradeoffs) Analysis of operations for each implementation Standard Template Library (STL) Use of vector, list, stack and queue template classes Use of iterators Know all the tradeoffs (in time & space) between all these data structures8Know all the tradeoffs (in time & space) between all these data structuresCpt S 223. School of EECS, WSUTrees (in memory) Definitions: general m-way tree, root, leaf, child, parent, ancestor, descendant, path, height depthheight, depth Binary tree: Definition, traversals Storing/representation:gp1. All children: use array or list2. Store pointers to only Leftmost child and right siblingsb g Tree traversals Inorder, postorder and preorder9Cpt S 223. School of EECS, WSUSearch Trees Binary search tree (BST) Definition Operations: Insert, Delete, Search, FindMin, FindMax, traversals Know how to perform these on a BST and show resulting BSTKnow how to perform these on a BST and show resulting BST Know worst-case and average-case analysis of performance Balanced BST (AVL trees)DefinitionDefinition Operations: Rotations & Cases, Insert, Remove, Search, FindMin, FindMax Know how to perform these on an AVL tree and show resulting AVL tree Insertion – remember all four casesTry out an example AVL deletion like worked out in the class (non-lazy method)Try out an example AVL deletion like worked out in the class (nonlazy method) Know worst-case performance STL set and map classes (not in syllabus for Midterm Exam I)Differences10Differences How to use them Cpt S 223. School of EECS, WSUGood Luck !11Cpt S 223. School of EECS,
View Full Document