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

CSCI 4041 Notes, Week 1

by: Lauren Arbisi

CSCI 4041 Notes, Week 1 CSCI 4041

Lauren Arbisi
U of M
View Full Document for 0 Karma

View Full Document


Unlock These Notes for FREE

Enter your email below and we will instantly email you these Notes for Algorithms and Data Structures

(Limited time offer)

Unlock Notes

Already have a StudySoup account? Login here

Unlock FREE Class Notes

Enter your email below to receive Algorithms and Data Structures notes

Everyone needs better class notes. Enter your email and we will send you notes for this class for free.

Unlock FREE notes

About this Document

This is meant to supplement the slides found on google drive. These notes cover the first week of class and introduce course material and procedure. In case you're wondering, the notes for Thursda...
Algorithms and Data Structures
Amy Larson
Class Notes
Computer, Science, CSCI, CS, cse




Popular in Algorithms and Data Structures

Popular in Computer Science and Engineering

This 2 page Class Notes was uploaded by Lauren Arbisi on Sunday September 11, 2016. The Class Notes belongs to CSCI 4041 at University of Minnesota taught by Amy Larson in Fall 2016. Since its upload, it has received 222 views. For similar materials see Algorithms and Data Structures in Computer Science and Engineering at University of Minnesota.

Similar to CSCI 4041 at U of M

Popular in Computer Science and Engineering


Reviews for CSCI 4041 Notes, Week 1


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/11/16
Written by Lauren Arbisi Week1Notes CSCI 4041 Fall 2016 Amy Larson Note: these notes are meant to supplement the slides that the instructor has posted on Google Drive, which can be accessed through Moodle. The number next to each note below corresponds to the number of the slide in the document. Tuesday, September 6, 2016 2. Problem in, solution out 3. Really, algorithms are about compromises and trade-offs. a. For example, Google maps algorithms have to take the following things into account: i. Traffic/Crashes ii. Phone computational power iii. Wait time for a route b. Predicting a brain-drug interaction for a medicine, you might take the following things into account: i. How long are potential patients willing to wait for guaranteed safety? ii. Are there similar drugs? What are their effects? iii. At what price will people buy the drug? c. Another example is the travelling salesman problem. i. All routes must be calculated to guarantee the shortest route. ii. A brute force approach may work on a small problem, but on larger ones they become essentially unsolvable. iii. Exponential growth in difficulty for each stop added. 4. Edsger Dijkstra 5. Take this example: you have a certain number of shirts, and a certain number of suits. You are somehow able to rank the individual items from each group from best for a job interview to worst for a job interview. 6. The graph shows that if you combine your worst shirt with your worst suit, the combination of the two is the worst outfit. If you combine your best shirt with your best suit, the combination of the two is your best outfit. 7. Figures from right to left, then top to bottom: a. Same as in previous slide. b. The graph shows that generally speaking, if you combine your worst shirt with your worst suit, the combination of the two is the worst outfit, and if you combine your best shirt with your best suit, the combination of the two is your best outfit. However, there is an anomaly. One medium-quality suit and one medium-quality shirt are kind of “meh” on their own. However, the combination of those two is very good. c. The graph shows that if you combine your worst shirt with your best suit, you will get a “meh” outfit. If you combine your best shirt with your best suit, the same is true. The best solution is somewhere near the higher end of each category, but not at the highest. The worst solution is somewhere near the lower end of each category , but not at the lowest. Written by Lauren Arbisi d. The graph shows local maxima and minima. There isn’t really a pattern. This is how many real-life algorithm problems will look. e. The graph shows that there are many good solutions. 8. Greedy algorithm Thursday, September 8, 2016 22. The main takeaway from this exercise (answers on slides 23-25) is that essentially, insertion sort divides the list two lists: one sorted, and the other unsorted. Because any list with length one is already sorted, we can use this truth to establish the base case for the function. 27. Loop invariant a. Prove for inner loop, then prove for outer loop. b. Prove for base case 28. A B A → B F F T F T T T F F T T T 33. Best case: already sorted. Run time O(n) Worst case: sorted in opposite order. Run time O(n )


Buy Material

Are you sure you want to buy this material for

0 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

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

Anthony Lee UC Santa Barbara

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

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

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


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.