Change Contents of the Bubble
Welcome to CS1315. Click on the python to add comments.

Looking for the book? They have it at the Engineer's Bookstore at 748 Marietta St NW. Here is there website: http://www.engrbookstore.com/ - Monica

Hotspots: Slides and Code • TA Corner • Comments? • Announcements • FAQ • Static Webspace
View this PageEdit this Page (locked)Uploads to this PageHistory of this PageHomeRecent ChangesSearchHelp Guide

Final Exam Review Spring 2004: Name that Algorithm!

Link back to Sp2004 Final Exam Review

Questions and Answers?


i am a little confused about this question...
1st program is sampling , because it decreasing the frequency.
2nd is sampling also because it scales pictures up to make it bigger

B. def findInSortedList(something, alist): linear search
def turnRed() uses algorithms
getRed(px) which gets the red value of every pixel in the picture, getColor(px) gets all the pixel values in the picture,
makePicture(file) makes the file a picture,
getPixels(picture) goes through the whole picture and analyzes each pixel.

are all of those algorithms though?
Think linear vs. binary. Mark Guzdial
thank you! so would the first two examples be binary, because you are only looking at a certain range. and the next two are linear because you are searching through every element?
Yes, but that's not really why. Binary search is sometimes called 'binary chop' because you chop the set to be searched into two parts based on where you know the target item to be and search only in that half. It's not that there are ranges: it's that the ranges define "halves" (not really halves, because they might be different lengths – but there are two of them) and you successively divide up the search space by chopping it in two and only looking in the correct half. Colin Potts
Okay, I'm not understanding this at all. I thought that the two examples in A use scaling and the two examples in B use searching. Are those not algorithms? What's all this talk about binary v. linar searching? I know what the two are, but how do they apply to the given functions?
Scaling is a goal, not an algorithm for getting there. Searching is also a gola, but there's more than one way to search. Any given search function is implementing a single algorithm. Mark Guzdial
so when you want us to identify an algorithm, you want to know where it is linear or binary. right? that's it?
...and then explain what linear means, and binary means...of course...now is that it?
...IN english!
where is this coming from notes-wise?

I know that the second set of functions are binary searches, but wouldn't the type of algorithms they are be sorting algorithms? Aren't binary and linear searches types of sorting algorithms?
Heather Symon
In the book, it uses the word algorithim in parentheses and instead of 'program' and 'recipe' in many cases. So wouldn't that mean that any bit that is a program would fall under the category of an algorithim? so that each of the two in A would be defining something, then analyzing it (in ways to copy or whatever), and then viewing/using (whether it be showing a picture or playing a sound)?

and then in B: it is also defining something and then searching for something based on certain requirements? (sorting: either binary or linear)...

Little help...

Jennifer Garrett
The comments are not helping. So if scaling is a goal, then is sampling the algorithm? And if searching is the goal, then are binary search and linear search the alogorithms?
The ones in part A are sampling algorithms and in B are linear search algorithms. Is this correct? Melanie Nelson

Yes, both of the programs in part A are implementing a sampling algorithm, and both of the algorithms in part B are implementing a linear search algorithm. They're definitely not sorting algorithms – sorts change the order of data, but none of these programs do that. Yes, Jennifer, any program is implementing some algorithm, but there are many different programs that implement the same algorithm. That's the point of this problem. Mark Guzdial
Now, can you explain a sampling algorithm and a linear search "in English" – explain what it's doing, apart from a program implementation? That's the other part of what the problem is asking you to do. Mark Guzdial

~clears throat~ And I quote-
"The sampling algorithim is a process that can be used to shift a sound's frequency up or down or to scale a picture smaller or larger. We don't have to talk about loops or incrementing source or target indices to describe the sampling algorithm. The sampling algorithim works by changing how we copy samples or pixels from a source to a target – instead of taking every sample or pixel, we can take every other sample/pixel, or every sample/pixel twixe, or some other pattern of sampling."

Annnnnnd - "Consider how you might look up a word in the dictionary. One way is to check the first page, then the next page, then the next page, etc. That's called a linear search,... It's not very efficient. The best case (fastest the algorithim could possibly be) is that the problem is solved in one step – the word is on the first page. The worst case is n steps where n is the number of pages–the word could be on the last page. The average case is n/2 steps– the word is halfway through."

That might be more than necessary, but I thought I'd put it in order to help with the question.. :):) Good luck everyone!!
Okay, let me see if I've got this straight: Algorithms are descriptions of processes that can be used towards a goal specified for a function. The types of algorithms we've seen are: sampling, mirroring, linear search, binary search, and blending. Sampling is the algorithm, scaling would be a goal of applying it. Is this the right idea? Brittany Copeland
Really nice, Brittany! Mark Guzdial

so the types of algorithms are: sampling, mirroring, linear search, binary search, and blending? or just linear and binary searches?



Link to this Page