New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Data Struct&Algor

by: Ophelia Ritchie

Data Struct&Algor EECS 281

Ophelia Ritchie
GPA 3.8

Sugih Jamin

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Sugih Jamin
Class Notes
25 ?




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.

Similar to EECS 281 at UM

Popular in Engineering Computer Science


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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.