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

Computer Science II

by: Lisette Hodkiewicz

Computer Science II CS 1120

Lisette Hodkiewicz
GPA 3.83

Ajay Gupta

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

Ajay Gupta
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 37 page Class Notes was uploaded by Lisette Hodkiewicz on Wednesday September 30, 2015. The Class Notes belongs to CS 1120 at Western Michigan University taught by Ajay Gupta in Fall. Since its upload, it has received 9 views. For similar materials see /class/216876/cs-1120-western-michigan-university in ComputerScienence at Western Michigan University.

Similar to CS 1120 at WMU

Popular in ComputerScienence


Reviews for Computer Science II


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: 09/30/15
Sorting Algorithms Insertion and Radix Sort Insertion Sort values 0 One by one each as yet unsorted array element is inserte 39 o I s proper place with respect to the already sorted elements Insertion Sort Works like someone who inserts one more card at Ime into a hand of cards that are already sorted 01 Insertion So t Works like someone who inserts one more card at a time into a hand of cards that are already sorted To insert 12 we need to ma ke room for it by movmg rst 35 and then 24 Insertion Sort Works like someone who inserts one more card at a time into a hand of cards that are already sorted To insert 12 we need to make room for it by moving rst 36 and then 24 Insertion Sort Works like someone who inserts one more card at a time into a that are alrea hand of cards d dy sorte To insert 12 we need to make room for it by moving rst 35 and then 24 A Snapshot of the Insertion Sort Algorithm Insertion Sort mfi l v mquot 3 n m 39K u 15 pg Code for Insertion Sort vold Insertlonsorthnt value5 Jam numValues Post Sorts array valuesm I I numValuesrl nto ascendlng order by key for nt cursort0cursortltnuluVa1uescurSortoo Insertltem values cursor o3 lt aquot rf m mr Radix Sort Cost Each pass n moves to form groups Each pass n moves to combine them into one group Number of passes d moves 0 comparison However demands substantial memory Imta comparison sort Sorting Algorithms and Average Case Number of Comparisons o Radix Sort Odn Selection Sort Bubble Sort Insertion Sort Quick Sort OlN qu N Merge Sort Heap Sort Binai 39 Search Given an EIITEly A1 11 and X detennine whether X a A1 n Compare with the middle of the an ay Reel ch depending on the result of the conipaii 11 07 Sorting Algorithms Selection Bubble Insertion and adix Sod Worstcase vs Averagecase Analyses 0 An algorithm can require different times to solve different problems of the same size s harder to compute but yields a more realistic expected behavi r Selection Sort values 0 Divides the array into two parts already sorted and not yet sorted On each pass finds the smallest of the unsorted elements and swap it into sorted elements by one 01 Selection Sort Pass One values 0 a n 2 G ll In Selection Sort Encl Pass One UmIWOMZC n n In In UmIzlomzc Selection Sort Pass Two values 0 n UmIzlomzc 02 Selection Sort End Pass Two values 0 SORTED Selection Sort Pass Three values 0 lt1 Selection Sort Encl Pass Three values 0 o3 Selection Sort Pass Four values 0 Selection Sort End Pass Four values 0 Selection Sort How many comparisons WillquotS 0 4 compares for values0 3 compares for values1 n 2 compares for values2 1 compare for values3 a 4321 o4 For selection sort in general The number of compa sons when the array contains N elements is Sum N1N2 21 Notice that r i a I a l J o How ny number of swaps 0N Therefore the complexity is 0N1 Code for Selection Sort SelectionSort int ValuesU int numValueS Sorts array valuearo order by key numValues 1 into ascending int endlndex numValues for 1nt current0curren Swap Value 5 current M1nIndexvalue 5 current endlndex e 1 tltendIndexcurrent 05 Selection Sort code con d lnt MlnIndexlnt values 1 mt start lnt Post Functlon value lndex of the ln values start t t values endlt end smallest value xofMln start n n e forlnt ndex start l l ndexu lf va ndex lt end luesr lndex lt values lndexOfMln lndexOfMln n return lndexOfMln Sorting Algori nms Bubble Insertion and Radix Sort Bubble Sort Compares neighboring llies 0 pai of array elements starting with the last array eleme t and swa s neighbors whenever they are not in correct order o6 Code for Bubble Sort vold BubbleSortLnt ValuesU 1nt numValueS lnt current 1 o whlle current lt numValues e 1 BubbleUpvalues current numValuesel current Vold BubbleUplnt Values 1 int startIndex int endlndex Post at are out of orde e a etween values startlndex Values endlndex l beglnnlng at Value 5 endlndex for 1n lndex e endlndex ta tIndex lndex lndex gt s r Valueslndex n lt veluesrlndexeil Swapvalues lndex lndexrl Observations on Bubble Sort There can be a large number of intermediate swaps Can this algorithm be improved What are the besUworst cases 0 This algorithm is 0N2 in the worstcase o8 DUNM 4m re Virtual Functions Virtual functions are the answer Tells compiler Wait until used in program Then get implementation from object instance Called late binding or dynamic binding Virtua functions implement late binding Class that define virtual functions are extensible Polymorphism Polymorphism refers to the ability to associate many meanings to one function by means of the latebinding mechanism Thus polymorphism late binging and virtual functions are really all the same topic Use Virtual Functions class Sphere public virtual void displays caciscics lt I is Spheren public Sphere ublic void displayscaciscics ltlt I is Ballnquoti in main Ball myBall 0 erePtri nmysall sphezepcgt displayscacis 1cs owvu39r I is Ball Vir39ual How To write C programs Assume it happens by magic But explanation involves late binding Virtual functions implement late binding Tells compiler to wait until function is used in program Decide which definition to use based on calling object Very im portant OOP principle Overriding Virtual function definition changed in a derived class We say it s been overridden So Virtual functions changed overridden Nonvirtual functions changed rede ned Virtual Functions y Not All Clear advantages to virtual functions as we ve seen One major disadvantage overhead Uses more storage Late binding is on the y39 so programs run slower So if virtual functions not needed should not be used Not All De n39 39ons are Useful Base class might not have meaningful definition for some of it s mem bers class Employee public mployeeslng Name szlng Ssn gold printchecko const Employeemprintchecko com ltlt RROR Undifferentiated employeenquot anew Pure Vir ual Functbns class Employee public EmployeeOi Employee s ring Name sting Ssn ame consc get estn e newnecpay k0 0 ng s 11 double necpay Abstract Base Classes Pure virtual functions require no definition Forces a derived classes to de ne thei own version Class with one or more pure virtual functions is abstract base class Can only be used as base class No objects can ever be create 39om it 7 7 9 el r it ll slll If derived class fails to define all pure s It39s an abstract base class too p e Inheritance class Base public2 vircual void prin0 class Derivedone 2 public Base public2 void prin coucltlt nerivedonequot class Derived l wo 2 public Base P 2 ub 2 void prin coucltlt nerivedmquot heritance class Mulciple 2 public nerivedonepublic Derived39l wo publi 2 void prin Derived l wcn 2prin Multiple Inherhamce in main Mulciple both Derivedone one Derived39l wo two io2 array i gtprin return 0 Error c259 mbiguous conversion from class Mulciple w a to class Base V ual Base Class class Base ublic2 virtual void prin0 class Derivedone 2 virtual public Base public2 void pin coultlt neivedonequot class Derived l wo 2 virtual public Base public2 void pin coultlt neivedmquot V ual ase Class class Multiple 2 public Derivedonepub11c Derived39l wo public2 void pin Derived l wo 1n eweuLme V rtual Base Class in mai le boch Derivedone one Derived39l wo mo 11 Mulcip i 13 i array1gtprin return 0 Pointers Contd Causing a Memory Leak mt p new mt D mt pnz new mt Dtrz Leaving a Dangling Pointer int Dtr new int n 8 int DtrZ new int mm 75 Dtr Dtr2 01 D amic Array Example rrav o HoatDUmbers vrnm cta dar m r t The nt a we arrav In M Sortarray srze quortedArraWarrav srze de ete an av Pointer Arithmetic Int p 116 int10 Algor39 hm Ef cien y and Sorting Algorithms 02 Measuring the Ef ciency of Algorithms J o is the area of computer SCIence at provides tools for contrasting the efficiency of different methods of solut n Concerns with si 39 differences How To Do Comparison 0 Implement the algorithms in C and run the programs How are the algorithms coded What computer should you use What data should the programs use Analyze algorithms independent of implementations The Execution Time of Algorithms Count the number of basic operations of an algorithm Read get write put compare assignment jump arithmetic operations increment decrement add subtract multiply divide shift open close logical operations noljcomplement AN D OR XOR w Funmur Properties of bigOh Ignore loworder terms OnE 4n33nOn3 Ignore multiplicative constant 05n3On Combine growthrate functions 0fn O9n 0fngn Worstcase vs Averagecase Analyses 0 An algorithm can require different times to solve different problems of the same size Is harder to compute but yields a more realistic expected behavior o6 Inheritance Primer Inheritance asics New class inherited from another class Base class General39 class from which others derive Derived class ew class Automatically has base class39s I l l39 l Cari then ad d additional member functions and varia es 01 Example Consider a class of Emponees Salaried employees Hourly employe Don39t need type of generic employee39 Since no 0 e39 Just an employee General concept of employee helpful All have names All have social security numbers Associated functions for these basics are me among all emp oyees Base Class Employee olsss Employee ubllc netPay00 srlng tSsn namessn Employee 5 trlng tName this const w sn ouble newNetPay prlntCheck const pnvste strlng name s nng ssn double netPay l Derived Class no public HourlyEmployee 0 HourlyEmployeestring tName 39 strlng tSsn double tWageRate ouble tHours vold setRatedouble newWageRate nst prlv double wageRate double hours Derived Class SalariedEmployee class SalarledEmployeezpubllc Employee public SalarledEmployee 0 double getsalaryO c n Void prlntCheckO pnvste double salary L Derived Class 0 Derived classes from Employee class Automatically have all member variables Automatically have all member functions Derived class interface only lisE new or mbers to be redefined39 m Since all others inherited are already defined i all39 employees have ssn name etc Constructors Base class constructors are NO inherited in derived classes But they can be invoked within derived class constructor which is all we need Base class constructor must initialize all base class member variables Derived class constructor simply calls it irst39 thing derived class constructor does o3 Derived Class Constructor Exa mple Consider syntax for HourlyEmployee constructor HourlyEmployee HourlyEmploye strln tNaIu dou EmployeetName tNu wageRate tWageRate ltgt Portion after is initialization section Includes invocation of base constructor A Second Constructor A second constructor Default version of base class constructor is called no arguments Hourlymployee HoulyEmployee ployee wageRate 0 hours 0 What if Constructor not Called Derived class constructor should always invoke one of the base class39s constructors If you do not Default base class constructor automatically called Equivalent constructor defin39 39on o4 Destructors in Derived Classes 0 When derived class destructor is invoked Automatically calls base class destructor ed for explicit call So derived class destructors need only be concerned with derived class variables And any data they point39 to Base class destructor handles inherited data automatically Destructor Calling Order Consider class B derives from class A class C derives from class B A 6 B 6 C When object of class C goes out of scope Class C destmctor called 1EL Then class B destructor cal Finally class A destmctor is called Opposite of how constructors are called Example class mm puhli 12am int n imo defz Pnin10 destructnr int getXO cnnst m etYO cnnst vnid print cnnsl cunt ltlt 1 ltlt xltlt ltlt y ltlt 39x39 05 Example default cnnstnlctnr nim int xVallIe int yValn denructnr 17mm PnimO mnltlt Pain Aw printO Example class Circle public Pain puhli Chum int 0 int mam112 00 Circ 20 vnid mm mm cunt ltlt 39139 ltlt ggtxo ltlt n lt getYU ltlt quot ltltrzdiusltlt Tm i m dnnhle radius Example mm int xVallIe int yValue mug manswag mm xVallIe yValne radius armwane rclzcunm nun 12 int cnnslnlct Circle cnnstmctnr 7 15 39 a 7219 45 mm denrnctnr 72 29 Access Class Members The private Quanti er Derived class inherits private member variables But still cannot directly access them Not even through derived class member functions Private member variables can ONLY be accessed by name39 in member functions of the class they39re defined in Same holds for base member functions 07 The private Quantifier Member functions vs member variables Member variables can be accessed indirectly via accessor or mutator member functions Member functions simply not available This is reasonable39 Private member functions should be simply helper functions Should be used only in class they39re de ned The protected Quanti er New classification of class members Allows access by name in derived class But nowhere else Still no access by name in other classes Considered protected in derived class To allow future derivations The public Quantifier Allows access by name in derived class And anywhere else Violates information hiding o8


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

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"


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