Data Struct&Algor EECS 281
Popular in Course
Popular in Engineering Computer Science
This 35 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 281 at University of Michigan taught by Sugih Jamin in Fall. Since its upload, it has received 11 views. For similar materials see /class/231525/eecs-281-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Data Struct&Algor
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
Outline Last time 0 Review of asymptotic analysis 0 Empirical performance evaluation 0 Review of foundational data structures Today 0 Review of basic ADTs o PA1 Walk Through Sugih Jamin Gamineecsumich edu Abstract Data Type Abstract Data Type ADT a higherlevel data representation that helps us conceptualize and manipulate a problem at a higherlevel than array and linkedlist Almost any problem in computer science can be solved by another layer of representation Objectoriented ADTs come with predefined interfaces How ADTs are implemented is hidden from the users Sugih Jamin Gamineecsumich edu Vector ADT What is a vector How is a vector different from an array Interfaces isempty size ithelt insertatith replacejth deleteith etc Possible implementation as an array Sugih Jamin Gamineecsumich edu Queue ADT What is a queue Example usage Sugih Jamin Gamineecsumich edu Queue ADT What is a queue A line of items with FIFO access the first item into the queue is the first one out Example usage line at the bank line at the bus stop Operations on queue Fig 64 enqueue dequeue head create size Sugih Jamin Gamineecsumich edu Queue ADT Implementation As a circular array Fig 65 0 head tail indices to keep track of front and end of line 0 keep a count to disambiguate a full queue from an empty queue 0 use modulo array length to wrap around at the end of array As a linked list 0 enqueue add to tail 0 dequeue remove from head 0 head element head points to Sugih Jamin Gamineecsumich edu Example Queueing Problems in CS Job scheduling in CPU Packet scheduling in network router Usual queueing diagram CH Sugih Jamin Gamineecsumich edu Deque ADT Deque pronounced deck doubleended queue Items can be inserted and removed from both ends of the deque Fig 68 Operations head enqueuehead dequeuehead tail enqueueiail dequeueiail create size etc Implementation Fig 69 as a doublylinked list Sugih Jamin Gamineecsumich edu Stack ADT What is a stack Example usage Sugih Jamin Gamineecsumich edu Stack ADT What is a stack A pile of items where new objects are put on top of the pile and the top object is removed first LIFO Example usage cafeteria tray a pile of paper napkins CDROM on spindle Operations on stack Fig 62 push pop top create size Sugih Jamin Gamineecsumich edu Stack ADT Implementation As an array 0 push add item to end of array 0 0 pop remove item from end of array 0 0 top look at item at end of array 0 As a linkedlist 0 push append prepend item 0 0 pop remove item from tai head 0 0 top look at last first item 0 Sugih Jamin Gamineecsumich edu Example Usage of Stack RPN Calculator Usual math infix notation 5 9 2 6 5 Can you use a stack to implement a calculator Order of operations is determined by operator precedence parentheses used to override precedence rules 5 9 2 6 5 Polish prefix notation does not require operator precedence rules therefore does not require use of parentheses 5 9 2 6 5 Or equivalently ReversePolish postfix Notation 5 9 2 65 Now the calculator can be implemented on a stack Fig 63 Sugih Jamin Gamineecsumich edu Example Usage of Stack RPN Calculator cont Reverse Polish notation is a more minimalist notation in math minimal elegant However parentheses may be used as syntactic sugar ie eye candy to ease legibility but not required for correctness So 5 9 2 6 5 can be written as 5 9 2 6 5 What does this look like Sugih Jamin Gamineecsumich edu Example Usage of Stack Function Call Stack How is the function call stack implemented Push formal arguments on stack call function push local variables on stack pop stack on return from function push return value on stack See Figs A8 A10 from PattersonampHennesy Sugih Jamin Gamineecsumich edu Buffer Overflow Attack Further reading optional Smashing the Stack for Fun and Pro t by Aleph One httpwwwphrackorgshowphpp49ampa14 Try this at home but NOT on the Internet Already done Internet Worm 1988 Sugih Jamin Gamineecsumich edu PA1 Programming Assignment 1 Topic path finding one of the primary areas of game programming Due date 104 1 PM Report due 109 140 pm in class To be done individually No STL Always get the latest revision of the spec Sugih Jamin Gamineecsumich edu The Game Rescue a victim from a building or defuse a bomb in the building whichever of the victim or the bomb is closer The Building n levels 0 g n g 9 Each level is an MXM square M 2 4 Each level can have different dimension and orientation Sugih Jamin Gamineecsumich edu Input File version28lFO7i nlevelsl levell dimension8 this is a comment map Vxxxxxx B x xxx x x xx x Sx XXXXZXXX N N N N N N Sugih Jamin Gamineecsumich edu Loca ons Starting position 8 Bomb location B Victim location V The target the closer of the bomb or victim All case sensitive Sugih Jamin Gamineecs umichedu Tile Types Open tiles quot Walls x You cannot walk through walls Some walls may have crumbled if you step off the MXM grid of each level you have a long fall in your grade Digits 09 staircases Rubbles r Sugih Jamin Gamineecsumich edu Staircases Each level can be connected to another level by a staircase Staircases are bidirectional if both levels exist the staircase connecting them must exist on both levels It is ok for a level to be inaccessible It is ok for a staircase to lead to a nonexistent level Two levels cannot be directly connected by more than one staircase Sugih Jamin Gamineecsumich edu Directions Top of file is north Direction markers n north 5 south e east 10 west h northwest j southwest k northeast l southeast Most northwesterly tile is coordinate 00 Staircases do not have to start and end at the same coordinate at both levels Sugih Jamin Gamineecsumich edu Path Marking Starting from the tile adjacent to the S tart position mark each tile with the direction taken in the previous step Ovenvrite the target tile with the direction of the final step taken Upon stepping on a staircase tile ovenvrite the staircase tile with the direction of the previous step taken If the stairs are taken do not ovenvrite the staircase tile on the exit level When standing on a staircase tile all adjacent tiles on both levels are visible Sugih Jamin Gamineecsumich edu Output File output for file testtxt version28lFO7o pathcost7 nlevelsl levell dimension8 map Vxxxxxx kee xnxxx x hx xxn h x Sx XXXXZXXX N N N N N N Sugih Jamin Gamineecsumich edu Map Representation Each level can be stored as a multidimensional array A multidimensional array must be implemented as a single contiguous chunk of memory you can call new only once though you may use other helper structures to access the array As you read in the map remember where the staircases at each level are You are not to record the location of the bomb and victim for direct access ie you are to search for them on the map Sugih Jamin Gamineecsumich edu Path Finding Implement three algorithms 1 queue based 2 stack based 3 variablecost algorithm Sugih Jamin Gamineecsumich edu Queuebased Algorithm enqueue start position loop dequeue next tile enque all unique adjacent tiles until target reached or queue is empty if queue is empty search failed if target reached show path taken Pick one of multiple possible paths Sugih Jamin lamineecsumich edu Stackbased Algorithm Stackbased same as before except use push and pop instead of enqueue and dequeue One of queueor stackbased must find the path with the lowest cost least number of tiles traversed Do NOT discuss or post on the forum which one is the better data structurealgorithm Sugih Jamin Gamineecsumich edu Variablecost Algorithm Different tile types now have different costs to move into 0 an open tile the bomb orthe victim costs 1 o a rubblefilled tile costs 5 o a staircase tile but staying on same level costs 2 o a staircase tile and taking the stairs between levels 139 and j costs 2 leveli leveljD a wall tiles are still impassable 00 cost Adapt the more optimal of your queue or stackbased algorithm to find lowest cost path with the above cost function and report the resulting pathcost according to the same cost function Sugih Jamin Gamineecsumich edu Timing Your Code Measure only the time it takes your pathfinding algorithm to run don t include time to do lO For example initstuff readmap gettimeofdayampstart0 pathfind gettimeofdayampend0 timing 2 end start PSEUDO CODE reporttiming Time all three algorithms for N differentsized maps then plot the results using gnuplot Sugih Jamin Gamineecsumich edu Command Line Options q run queuebased algorithm s run stackbased algorithm v run variablecost algorithm i ltstringgt take string as input file name default stdin o ltstringgt take string as output file name default stdout e run timing analysis must be used with one of q s or v h help q s and v are mutually exclusive How do you read the command line options Never seen main argc argv Sugih Jamin Gamineecsumich edu Error Codes If you run into an error print out an error message and call exit with the appropriate error code EBADOPT lO EBADFILE 20 EBADVERSION 21 EBADFTYPE 22 EBADMAP 3O EMULTS 3l EMULTB 32 EMULTV 33 EMULTC 34 ENOSTART 35 ENOBOMB 36 ENOVIC 37 Sugih Jamin Gamineecsumich edu Exit Codes Upon correct exit also call exit with the appropriate exit code NOERR O NOPATH 2O PATHTOB 21 PATHTOV 22 Sugih Jamin Gamineecsumich edu Other Items Coding style Empirical efficiency Start immediately Don t debug with coutprintf s Help stop 48 hours to due date Testing your code may post test cases and outputs Your code MUST run on CAEN Linux machine don t wait till last minuteday to port best to work on the system from the start The autograder is NOT a debugger Grade composition What to turn in Sugih Jamin Gamineecsumich edu Reminder Course Grading Policy Course grade composition 0 Final 20 o Midterm 20 o Homeworks HWs 12 0 Programming Assignments PAs 46 0 Class Participation 2 A total of four free late days incl weekends and holidays You must keep track of your own late days Sugih Jamin Gamineecsumich edu
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'