Limited time offer 20% OFF StudySoup Subscription details

WSU - CSC 1500 - Study guide Fundamental Structures Exam 2 - Study

Created by: Alyssax2 Elite Notetaker

> > > > WSU - CSC 1500 - Study guide Fundamental Structures Exam 2 - Study

WSU - CSC 1500 - Study guide Fundamental Structures Exam 2 - Study

School: Wayne State University
Department: Computer Science and Engineering
Course: Fundamental Structure in Computer Science
Professor: Areej Salaymeh
Term: Winter 2018
Tags: Fundamental and structures
Name: Study guide Fundamental Structures Exam 2
Description: This study guide will help you review for the second hand of the exam
Uploaded: 03/20/2018
This preview shows pages 1 - 3 of a 11 page document. to view the rest of the content
background image Fundamental Structures Study Guide Exam 2   Sorting  The sorting problem is to  rearrange  the items of a given list in  nondecreasing order.  Why would we want a sorted list?  –  can be a required output of a task (example: Ranking 
students by their GPA scores) 
–  makes many questions about the list easier to 
answer(example: searching in dictionaries, class list, etc) 
–  used as an auxiliary step in several important algorithms  A sorting algorithm is called  stable  if it preserves the  relative  order of any two equal elements in its input.  An algorithm is said to be  in-place  if it does not require  extra memory, except, possibly, for a few memory units.  Bubble Sort  Compare adjacent elements of the list and exchange them if 
they are out of order. By doing it repeatedly, we end up 
“bubbling up” the largest element to the last position on the 
list. The next pass bubbles up the second largest element, 
and so on, until after n − 1 passes the list is sorted. 
Pass i (0 ≤ i ≤ n − 2) of bubble sort can be represented by 
the following diagram: 
background image Bubble Sort- Example  Bubble Sort Algorithm  Insertion Sort  The simplest sorting algorithm, but it is not the most 
efficient. 
background image To sort a list with n elements, the insertion sort begins with 
the second element. 
– The insertion sort compares this second element with the 
first element and inserts it before the first element if it does 
not exceed the first element. 
– At this point, the first two elements are in the correct order. – The third element is then compared with the first element, and if
it is larger than the first element, it is compared with the second 
element; it is inserted into the correct position among the first 
three elements. 
Greedy Algorithms  • Optimization problems The goal of such problems is to find a solution to the given problem that either minimizes or maximizes 
the value of some parameter. 

This is the end of the preview. Please to view the rest of the content
Join more than 18,000+ college students at Wayne State University who use StudySoup to get ahead
11 Pages 61 Views 48 Unlocks
  • Better Grades Guarantee
  • 24/7 Homework help
  • Notes, Study Guides, Flashcards + More!
Join more than 18,000+ college students at Wayne State University who use StudySoup to get ahead
School: Wayne State University
Department: Computer Science and Engineering
Course: Fundamental Structure in Computer Science
Professor: Areej Salaymeh
Term: Winter 2018
Tags: Fundamental and structures
Name: Study guide Fundamental Structures Exam 2
Description: This study guide will help you review for the second hand of the exam
Uploaded: 03/20/2018
11 Pages 61 Views 48 Unlocks
  • Better Grades Guarantee
  • 24/7 Homework help
  • Notes, Study Guides, Flashcards + More!
Join StudySoup for FREE
Get Full Access to WSU - CSC 1500 - Study Guide - Midterm
Join with Email
Already have an account? Login here
×
Log in to StudySoup
Get Full Access to WSU - CSC 1500 - Study Guide - Midterm

Forgot password? Reset password here

Reset your password

I don't want to reset my password

Need help? Contact support

Need an Account? Is not associated with an account
Sign up
We're here to help

Having trouble accessing your account? Let us help you, contact support at +1(510) 944-1054 or support@studysoup.com

Got it, thanks!
Password Reset Request Sent An email has been sent to the email address associated to your account. Follow the link in the email to reset your password. If you're having trouble finding our email please check your spam folder
Got it, thanks!
Already have an Account? Is already in use
Log in
Incorrect Password The password used to log in with this account is incorrect
Try Again

Forgot password? Reset it here