DOC PREVIEW
WSU CPTS 223 - Lecture Notes

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 notesCalculators 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 ComprehensiveTopics include:Topics include: Math introElementary data structures–array, list, stack,Elementary data structures array, list, stack, queue Asymptotic notation and complexity analysis Trees Binary Search TreesAVL TAVL 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 seriesSeries: Definitions, manipulations, arithmetic and geometric series closed form  Proofs: Know definition, components, and how to use the following Proof by inductionProof by induction  Proof by counterexample  Proof by contradiction RiRecursion  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 referenceReference variable (&x) and call by reference  Copy constructor, operator overloading, operator= p Templates STL for different data structures6STL 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 fLine-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 BSTKnow how to perform these on a BST and show resulting BST  Know worst-case and average-case analysis of performance  Balanced BST (AVL trees)DefinitionDefinition  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 casesTry 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)Differences10Differences  How to use them Cpt S 223. School of EECS, WSUGood Luck !11Cpt S 223. School of EECS,


View Full Document

WSU CPTS 223 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?