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

This page removed for FERPA compliance
View this PageEdit this Page (locked)Uploads to this PageHistory of this PageHomeRecent ChangesSearchHelp Guide

Final Exam Review Spring 2003: Name that Algorithm!

Questions, answers, comments?

(Back to Sp2003 Final Exam Review)

First two are sampling algorithms. Second two are linear search algorithms.
Lauren Biddle
Cool! If I asked you to name a program that implements a copying algorithm (copying something from one data structure to another) or a binary search, could you name one? Mark Guzdial
can someone explain why they are sampling and linear?
BTW (following up on that question above): Note that the questions say not only to name them, but to describe them in English. (Also recall that these weren't the only two algorithms we studied – binary search is also fair game.) Mark Guzdial

How do you explain them in English?
Ok this is REMOVED how I identify the different types than how they are explained, but...
A sampling algorithm is one that has a source value and a target value. It copies the elements REMOVEDed by the source value, moves the copies to the target value (changing them in some cases as specified by the function), and finally returns the new target elements. A linear search algorithm takes a list of items and goes through the list (beginning with the first elements) until it finds what it was supposed to and returns that element. A binary search algorithm also takes as input a list, but it divides the list in half (and half again) and searches the smaller divisions in which the element should be contained. Also I don't know if you wanted this included too, but sorting algorithms "sort" elements (or place them) into a sequence.
Student117

Your description of the sampling algorithm just sounds like a copying algorithm. It does something different than just copying. The linear and binary search ones are pretty good, but the binary search can split by halves REMOVED than twice. Mark Guzdial
Sampling algorithms increment the source index by 1/2? I'm not completely sure what that means however. Perhaps that the target is the size of 1 and a 1/2 of the source? Any suggestions?
To increase the size of a picture, you take every pixel twice. To decrease, you skip every other pixel. To half the frequency of a sound, you take every pixel twice. To double the frequency, you skip every other sample. Perhaps there's a pattern here? Mark Guzdial

If we just said that it manipulates the source value in some way before putting it in the target would that work? Or does it need to be REMOVED specific?
That would be outright wrong. Sampling doesn't change the source value. It changes the source INDEX. It's not the value that changes, but WHICH values you're copying. Read over the code again and see if you see that. Mark Guzdial

A)  This is a sampling algorithm. A sampling algorithm:
1.	Gets an index to a source
2.	Gets an index to a target
3.	For all the elements that we want to process:		
	1)  Copy an element from the source at the integer value of the source index to the target at the target index
	2)  Increment the source index by some number 
		a)  for sound:
		b)  for pictures:
	3)  Return the target when completed

B) This is a linear search algorithm. A linear search algorithm goes through each item in a set of data to find all items that match a certain given criteria. It returns every item that matches.

OTHER TYPES of algorithms discussed:
A) Binary search algorithm – Break the data into sections. Search each section separately (at different times). When the item is found, return or print “Found it” statement. Very similar to linear search algorithm, but saves time. Example: findInSortedList(something, alist)
B) Text search algorithm - Find the item you want, get one side of what you want to return or print, then get the other side. Print or return the text between the two sides. Example: FindTemperature()
This isn't really plain English, though. I don't really know how to explain the concept that much less technically. Lauren Biddle
Very nice on sampling – REMOVED detail than needed, but definitely what I mean by "in English." Binary search: Missing a key detail about "halves." Mark Guzdial

Is there an example of a copying algorithm in our slides anywhere??
REMOVEDre – splicing and basic compositing of a picture into a canvas is copying – you move the samples or pixels from one place to another, one after the other, skipping none, and modifying none. Mark Guzdial

so then isn't the algorithm of copyBarbsFaceLarger() also an example of a copying algorithm since it involves copying?
I seem to have sat with my TA way back before the last quiz and discovered that a sampling algorithm was one in which the original (data, be it picture or sound, etc.) is sampled (portions taken) and something performed on those samples.
So, a copying algorithm actually samples and copies to a new place. The main difference between sampling and copying algorithms is that the copying does just that— copy. The sampling samples and does something, such as change/alter the data.
Yes, a sampling algorithm is a kind of copying algorithm. But a sampling algorithm does NOT do a one-for-one copy. No, it doesn't alter any individual pixel or sample. But by skipping or doubling the individual pixel/sample copies, you end up with a new result that's bigger or smaller, higher or lower, than the original. Mark Guzdial

So when you sample (because you're resizing and thereby taking every other pixel) out a portion of a picture to copy it to a new place and to alter it by changing the colors of the pixel with say clearing the Red all inside the same function, what kind of algorithm is that? Is that a sampling algorithm? Doesn't that alter the pixels?
clearRed isn't sampling or copying. Nor is it linear search nor binary search. We haven't named EVERY algorithm. Mark Guzdial

Oh.
If you omit the clearRed portion and you only take a portion of a picture from one place and copy it to another by resizing it, is that a sampling algorithm? If I'm right, it can't be a copying algorithm because it's not copying exactly the portion with all the pixels within that range choosen to copy.
Sounds right to me. Mark Guzdial





Link to this Page