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


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

Class Notes
25 ?




Popular in Course

Popular in Engineering Computer Science

This 25 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 Staff in Fall. Since its upload, it has received 39 views. For similar materials see /class/231539/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
3 38 Discussion slides for week of October 17 2007 The University of Michiran Agenda Constructors and Destructors PA2 questions discussion Bits and binary operations Binary IO Files iosbinary Gprof subversioncvs brief 981 DATA STKU CTU RES AND ALGORITHMS Constructors What are constructors used for Custom initialization When a variable comes into scope First space is allocated for it The variable IS initialized Constructor ca led Can a constructor have parameters Example What about new statements 112 8 1 DATA STRUCTURES 39 AND ALGORITHMS Destructors What are destructors used for Custom dealocation Can destructors have parameters When a variable goes out of scope o Destructor caled Space is dealocated Local variables are destroyed in the reverse order of creation Useful for dealocated all virtual memory used in the class 112 8 i DATA STRUCTURES 39 AND ALGORITHMS Example class Dog pub l i C 1 for the termmatmg 39 039 char name int age Dogchar name Rex int age0 I thisgtnamenew charstrlenname 1 constructor strcpythlsgtnamename thisgtageage 30th ltlt name ltlt quotis born ltlt endl Doggt destlucml cout ltlt name ltlt quotis gone ltlt endl delete name leleases clynnnncn y allocated 111611101339 back to the heap a DATA STRUCTURES 281 AND ALGORITHMS Example contd unphclt COllStl llCtOl39 call main Dog dogA Fido 3 dogB cout ltlt quotHere boy ltlt endl if true Dog dogC quotSpotquot dhudoum cout ltlt quotGood girl ltlt endl 2ck nwhwcdh Output Fido is born Rex is born Here boyl Spot is born Spot is gone Good girll Rex is gone Fido is gone 66 DFJASTRMCTURiS 39 AND ALGORITHMS Bits and Binary Why do we care a A deep understanding of computers requires an understanding of what is happening at the bit level a Common interview questions Application examples 7 Device drivers parts of operating systems a Heavily optimized code 7 Embedded devices a Lowlevel file manipulation eg compression 7 Storing arbitrary data formats efficienty 112 8 i DATA STRUCTURES 39 AND ALGORITHMS Data Representation Standard variable types hold sets of bits 7 Char 1 byte 1001 0001 7 int 24 bytes 1 001 0001 1 001 0001 7 long 4 bytes 1 001 0001 1 001 0001 1 001 0001 1 001 0001 Unsigned flag is often useful to prevent any of the bits being Interpreted as a negation ag We often inter ret chars as ASCII codes but this is only a partcu ar Interpretation of the bits Assigning 00010000 to a char 7 charx 16 decimal 7 charx 020 octal 7 charx 0x10 hexl 112 8 i DATA STRUCTURES 39 AND ALGORITHMS Bit Manipulations amp AND 1010 amp 1001 OR 1010 1001 A XOR 1010 quot1001 complement 1010 ltlt left shift 1010 ltlt 2 gtgt right shift 1010 gtgt 1 11281 DATASTKUCTUKES AND ALGORITHMS Bit Manipulations Masking 7 How to extract the middle 4 bits from 01011100 7 How to clear the middle 4 bits from 01011100 Packing 7 How do we combine 0X04 and 0X03 into a single byte 1 DATA STRUCTURES 10 I AND ALGORITHMS Bit Fields Bit fields are sometimes useful for storing bits in a compressed structure In memory Not directly useful for 10 Bit shiftsoperations can accomplish the same thing struct DISKREGISTER unsigned ready1 unsigned erroroccured1 unsigned diskspinning1 l DATA STRUCTURES 11 I AND ALGORITHMS Files are streams of bits 010010010101010101010101010100110 000100101011111101001001010100101 010100110110010010101001010101010 100000000011110100100011110010100 112 8 i DATA STRUCTURES 39 AND ALGORITHMS Symbols are just chunks of bits 010010010101010101010101010100110 000100101011111101001001010100101 010100110110010010101001010101010 100000000011110100100011110010100 11358 1 DATA STRUCTURES 39 AND ALGORITHMS IO for binary files Upen mes usmg binary mode Prevents interpretations of newlines spaces etc from causing trouble ifstream myFile quotdatainbinquot ios3939in iosbinaly l I DATA STRUCTURES 14 I AND ALGORITHMS Reading and Writing Bits Can only readwrite on byte boundaries Don t use gtgt and ltlt insertion extraction 7 These are for formatting Use readwrite functions for blocks of chars 7 No nu character appended no interpretation Just the raw bits 7 May not want to read ever thin at one time for very large files use blocks eg 1KB at a time 112 8 l DATA STRUCTURES 39 AND ALGORITHMS Reading and Writing Bits Read from a le char buffer100 ifstream myFile quotdatainbinquot ios3939in ios3939binaly myFileread buffer 100 do stuff With the data Write to a le char buffer1 00 ll the buffer With the data you want ofstream myFile quotdataoutbiuquot ios3939out ios3939binaly myFile write buffer 100 l DATA STRUCTURES 16 I AND ALGORITHMS iosbinary Used while opening les mylnStreamopen eNametxt iosin iosbinaly Does it convert the data in le to binary Trick Question The les are already in binary Duh What iosbinary does is prevent interpretation of end ofline characters etc 1 DATA STRUCTURES 17 I AND ALGORITHMS Viewing binary files A text editor interprets les as ASCII which won t work well for generic binary les 7 xxd hex ASCII 7 xxd b binary ASCII 7 hexdump C hex ASCII 1 DATA STRUCTURES 18 I AND ALGORITHMS xxd output 0006530 0000 0016 0000 0a26 000b 4601 000d c605 0006540 0001 d002 0037 2400 0f84 d002 5e84 d002 0006550 0e84 0000 5d84 0000 1184 98fe 6084 98fe 0006560 0f00 0037 2400 0f84 3804 5e84 3804 0e84 78quot8 0006570 0000 5d84 0000 1184 0000 6084 0000 0016 0006580 0000 0a26 010b 4601 000d c605 0001 a005 ampF 0006590 0037 2400 0f84 a005 5e84 a005 0e84 0000 7quot 0006cf6 00000000 00000000 01 101010 00000000 00000000 00000000 0006ch 00000000 00000000 00000000 00000000 00000001 00000000 0006d02 01001111 00000000 01101100 00000000 01100101 00000000 Oe l DATA STRUCTURES 19 I AND ALGORITHMS Profiling A profiler allows you to identify which pieces of code are taking the most time 7 Allows you to focus optimization effort where it is necessary Io maKe your program 5 faster 7 Optimizing a function that takes 1 of the total time 7 Optimizing a function that takes 10 of the total time 7 Optimizing a function that takes 50 of the total time 112 8 i DATA STRUCTURES 39 AND ALGORITHMS gprof Compile with the pg flag Run the program as usual 7 Will run somewhat slower You will have a gmonout le in your directory 7 This is overwritten each time the program is run Run gprof to examine the data gprof options executable le profiledata es gt outfie l DATA STRUCTURES 21 I AND ALGORITHMS gprof flat profile output Flat profile Each sample counts as 001 seconds cumulative self total Elm seconds calls 115quotCall LIBcall 3 50 5 43000 312 312 2 6 9 2 1 12 166667 14156 67 6 0 S 039 040 040 12 000 000 090 12 000 000 040 l 000 000 090 l 000 000 0 40 l 000 17000000 1111 Dve law IOfileoverflow IOpuc Life update volt stdicbnf39 39cverflcw inc stdicbu syswrite char const int 0519am paratnrltlt char internalimcaunt Life print void toconc void Life initialize void instructions void main K rn DATA STRUCTU RES AND ALGORITHMS m2 81 gprof call graph index time self called name 002 1212 main 2 11 425 002 015 12 updaevoid 1 015 0 00 4200043000 39 hborcuurgtttint int 4 000 017 11 3tarc 3 L2 425 000 017 1 002 015 1212 000 000 12f12 000 000 1212 000 000 11 000 000 11 L31 42 5 0 0 0 17 00 0 17 111 15 000 4500043000 Lifeupdatevoid 1 4E 375 015 000 43000 Lifeneighborcnuncint inc 4 868 l DATA STRUCTURES 23 I AND ALGORITHMS Version Control Subversion svn cvs proprietary tools Useful for individual projects crucial for multiple developers Functionality central repository for code version history rollbacks revision merging conflict detection resolution assistance cnange lists logging branch management tagging 3amp2 839 DATA STKU CTU RES 24 AND ALGORITHMS Typical Use Create a repository Import some les into it Check out a local working directory Make changes Update to latest version Fix any con icts test changes in latest version Check in your changes 1 DATA STRUCTURES 25 I AND ALGORITHMS


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."

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

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.