×

### Let's log you in.

or

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

×

or

by: Katie DeRose

112

0

5

# Computer Science CS:1110:0AAA

Katie DeRose
UI
GPA 3.4
Introduction to Computer Science
Denise Szecsei

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

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

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

×
Unlock Preview

These are Lecture notes from February 9th- February 13th.
COURSE
Introduction to Computer Science
PROF.
Denise Szecsei
TYPE
Class Notes
PAGES
5
WORDS
KARMA
25 ?

## Popular in Department

This 5 page Class Notes was uploaded by Katie DeRose on Monday February 16, 2015. The Class Notes belongs to CS:1110:0AAA at University of Iowa taught by Denise Szecsei in Spring2015. Since its upload, it has received 112 views.

×

## Reviews for Computer Science

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/16/15
I Lecture 210 A Sorting Algorithms continued need to know rst pass for bubble sort insert sort and selection sort 1 Insertion Sort a you have a list and a group b the list starts with one number from the group c then using an index you take the next random number from the group and insert it where it belongs in the list d seems more efficient than bubble sort because it is less work 1 have to grow through short list each time instead of going through whole list every time to nd place 2 but still have a nested loop that you have to pass through so it is still not that efficient a only going to ask about the rst pass through for insertion sort 2 Selection Sort a take the minimum rst number in list go through next number and see if it lessif it is then it is the new minimum 1 continue to go through until you nd the actual minimum and puts it in new list 2 if the number after minimum is not lower you swap that number and put it after the minimum b then go through the group again in same way until you nd the next minimum and then insert it into its correct place in the new list c eventually the group will be in order and you insert them each into new list until you have full list 3 Merge Sort a example list want to sort with merge sort 32469805 merge sort makes copywhich requires memory and breaks in half 3246 9805 then breaks these in half 32 46 98 05 breaks it down again 3 2 4 6 9 8 O 5 now all of these lists have one item and are therefore sorted in themselves then it is like war compare the two together then order them 23 46 89 05 now you want to but two closest together but theyre already in order so just put em together 2346 then O589 then compare the two ending lists and order them against each other until each is in order 2 vs 0 0 wins put zero rst is 2 smaller than 5 yep so it goes next then 3 vs 5 three wins and so on 1 better than all of the sorting algorithms we have looked at so far gtknow for exam 2 only problem is that it is memory intensiveltknow for exam 4 Quick sort 1 you should use this because it is fast like merge sort but does not take the memory 5 Which algorithms to choose from bestworst quick merge insert or selection bubble B Analyses of Algorithms 1 O 1 means the amnt of work you do is not affected by length of the input It means constant runtime def swapaList ij temp aListi aListi aListj aListj temp return aList 2 Logarithmic RunTime Ologn a binary search is perfect example of this runtime i lookin g through phonebook for hawkeye plumbing 1 a lphabetical 0 you open up maybe to middle and see k s h is before k so you don t care about latter half of the phone book 4 s tart with midpoint of half you do care about 5 9 et f so you delete the rst half and look from f through k nd mid point again until you nd it ii divide and conquer algorithm iii proble m is that you need to start with sorted list otherwise it doesn t work 3 Linear RunTime On a perfect example is sequential search i deck of cards look for Ace of spades ii pick from top of stack until you nd it iii theref ore length of stack is going to affect the amount of work you have to do iv worst case scenario it is the last card on bottom best case is that it is on top b should know how to write a formula 1 go through length of list if you nd something that matches what im looking for say this 4 Merge Sort Onlogn 5 bubble insert selection On2 C Rules for Runtime Analysis 1 sequential code a line 1 line 2end line 1 each line has a runtime complexity 1 l ine 1 Oa 2 l ine 2 Ob 3 l ine 24 02 11 run time Max of Oa ObOz 1 w hichever complexity is the bottle neck the way it is judged 111 exam ple def myfunn step a 0n2 step b 01 step c0n 1 O n2 is the bottleneck because it is the worst part of function and that is how the function is judged 2 conditional code if Oa code Ob else code Oc a max Oa Ob 00 3 Iterative a amount of work you do depends on length of list forj 13911 range 011 step 1 step 2 step 3 b judges by nding worst step and multiplying by n for i in rangeon sum sum 1 would be called 01 return sum 01

×

×

### BOOM! Enjoy Your Free Notes!

×

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

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

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 material...plus I made \$280 on my first study guide!"

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

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com