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 Fall 2003: Name that Algorithm!

Questions, comments, answers?

Back to Fall2003 Final Exam Review

A) The function half is taking a sound as input and stretching the first half of the sound over the entire length of the original sound. You are left with half the original sound at half the original frequency. The function copyBarbsFaceLarger is taking a picture as input and copying it onto a canvas with twice the original width and height. You are left with a picture of Barb’s face four times the size of the original picture.
B) The function findInSortedList is taking a list and something to look for in the list as input. It then walks through each item in the list and if it finds the something you are looking for it returns “Found it!”; otherwise it returns “Not found”. The function turnRed takes a picture of Barbara and compares each pixel in the picture to a known color brown. If the color of the pixel is close enough to the color brown, the red is increased in that pixel by 50%. In this way all of the brown in the picture of Barbara will have a red increase of 50%.

Those are reasonable descriptions, but I'm actually looking for a single name that describes BOTH programs in A and BOTH programs in B. Mark Guzdial

The ones in A are sampling algorithms and in B are linear search algorithms. Right?
Could you please explain what those algorithms mean. What other algorithms exist? Thank you
i also would like more information here.

for a: the two programs are sampling (one with sound samples and the other with pixels) and taking each sample twice
for b: both programs are searching for a specified criterion; if (and when) it is found, the programs perform a certain action ( to manipulate the input); if it is not found, no change is made in either program
The second is more than a search – it's a particular kind of search. Remember that you know about two kinds of searches.

I'd be glad to provide more information, but as a question. What do you want to know? I did list several algorithms at Friday's review. Mark Guzdial


the particular kind of search is a linear search (vs a binary search)
coming directly from the lecture slides:

the sampling algorithm gets an index to a source and gets an index to a target, for all the elements that need to be processed: copy an element from the source at the interger value of the source index, to the target at the target index, then increment the source index by .5

look at the complexity lecture slides. they are helpful in dealing with algorithms.

From that complexity presentation, there are four algorithms mentioned: linear search, binary search, sorting, and sampling.
binary searches are more efficient...by searching in halves of the entire list...the complexity is O(log n) whereas linear searches have O(n) complexity.

B1 and B2 are both linear b/c they search each item in the list..et cetera

Link to this Page