Final Exam Review Fall 2004: Name that algorithim


	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

Final Exam Review Fall 2004: Name that algorithim

Someone want to help me out and post the answer to this question??
I was just curious as to what exactly "name that algorithm" means. Does it mean that we look at the function and review and explain whats going on in detail?

Describe what the it does in english and include the running time of the algorithm (Big O). Angela Liang

a) sampling algorithm

ok just taking a stab at these two..
a) both algorithms are resizing the given media.. not sure what Big O it is
b) both algorithms are having to perform a linear search (O(n)).. looking at each item in the list (or pixel in the picture) one at a time from start to finish

Are they resizing them bigger or smaller? And are you sure that each pixel is only being looked at once? Kelly Lyons

half(filename): is taking a sound file in as an input and creating it into two seperate sounds(seperate by means of name not by sound at this point). We start the index for the source at 1 and run a for loop that specifies a range from 1 to the length of target +1 (b/c of range function). Then it sets the sample value of the target sound at what ever targetIndex is (range(1, getLength(target)+1) and sets the element of target at that index to whatever the sample value of getSampleValueAt(source, int(sourceIndex)). The int is very important to the next line in the for loop block because it is being added by 0.5. When you do int(0.5) you get and this allows you to take the value of a certain index twice. after the for loop is run all the way through the program plays back the new sound created by the function and returns the value so that it could be further manipulated. The sound of the new sound of target sounds like it is slower and is at a lower pitch. In this function it is actually only going to play the first half of the sound because the array of elements has gone from a 1,2,3 sequence to a 1,1,2,2,3,3. The frequency is decreasing but the amplitude is constant in this funtion.
copyBarbsFaceLarger(): this is a function that operates much like half(filename) except there is no input in the function copyBarbsFaceLarger() and it is dealing with pictures instead of sound. The program first takes in a picture barb and a blank picture called canvas. The code is going to start by starting the sourceX (x coordinate) at 45 on barb and copy it to canvas at point 100 on the target image. It then looks at the sourceY (y coordinate) at 25 and copys it to point 100 on the target image. The code then takes the color of the pixel on barb at sourceX and sourceY using the integer function to make use of doubling, and then sets the color of the target picture at (targetX, targetY) to the color of the sourceImage at the specified coordinates. After moving through all the code the code shows barb and the canvas and returns the image. The new picture canvas is going to be an image that ranges from (100, 410) in the x coordinates and ranges from (100, 450) in the y coordinates. This is in essence doubling the x coordinates and y coordinates of the range of the source image and copying it over to the target image. It isnt actually copying the image though it is actually setting the 3byte pixel information of the source and transfering the values to the target.
In short the next two functions are actually using for loops to process lots of data and then testing that data with an if statement. If the if statement holds true it goes through with the if loops nested block. If the if block is false it skips over the block of code.
findInSortedList(something, alist): basically runs a search for the input something in a specified list (input name alist). It then runs the if statements to see if it found it if so it prints found it if not it prints not found.
turnRed(): this function takes a color brown with specified RGB values and looks in a specified picture file called picture. It then runs a for loop to look at all of the pixels in the picture and gets there color. The code then runs an if statement that compares the color of the picture in the file and the color brown which was earlier specified and preforms the distance formula. If the distance formula answer is less than 100 it runs inside the if loop if not it skips over and analyzes another pixel. If the distance is less than 100 then the function takes the Red value of the pixel and increases it by 50% and sets the color. After its done analyzing the code it shows the picture and returns the picture.

"copyBarbsFaceLarger(): this is a function that operates much like half(filename) except there is no input in the function copyBarbsFaceLarger() and it is dealing with pictures instead of sound. The program first takes in a picture barb and a blank picture called canvas." You first say that it takes in no input, and then say that it does. I am asuming you are meaning that it creates a picture from a file inside the function, but you should be more careful with your words. Mistakes like this make it hard to tell sometimes if you really understand things or if you are just guessing. Kelly Lyons

I'm a little confused with how specific you have to be in naming the algorithm. I understand that an algorithm is a description of "how a recipe works, completely apart from how it's written." Would it be enough on the exam to say for part one that the neither function takes input. They both open files from within the function, a targetFile and a sourceFile and have a targetIndex which moves independently from and twice as fast than the sourceIndex. They move information from the sourceFile at the sourceIndex to the targetFile at the targetIndex. Is that a good description of the algorithm?

You are close to the answer, but you need to look back at how you are describing what the target and source Index do... The target and source are the same file to begin with in the case of the sound and not in the picture, and the program is taking certain parts from the source and putting them into the target, the question is how–the targetIndex is not automatically twice as fast as the sourceIndex though (because for one they are the same file, and in the second program the file is not a sound)... You don't have to be quite this descriptive as to what each program does, you can be a little more concise in that they both perform the same type of operation on differnt kinds of files. Summer McWilliams

I've had a hard time deciphering which Big Os are in algorithms in the past...and in this problem. :-\
What does implemented mean?

SO what is the O of the first one, the second two sets of code are "N" correct?

For the second set of two programs, they are O(n) becuase the first goes through each item in the list once and the second goes through each pixel once. For the first one, how many times is each pixel or sound sample visited? Is it constant and not dependant on the number of pixels or samples? In this instance, the answer would be O(n). Is it a number of times dependant on the number of pixels (increase the number of pictures, and you visit each pixel more times)? This would lead to an O(n^2) or O(nlog(n)) or whatever dependant on the relation. Kelly Lyons

So then how do you determine if something's non-linear [O(n)]? For instance, the "O(n^2) or O(nlog(n)) or whatever dependant on the relation" - how do you process the relation to determine the type of Big O? (The difference between n^2 and nlogn just by looking at the algorithms.)

for the first set, is the big O O(n) and for the 2nd set is the big O O(log(n))?
i am kinda in the dark about this one, so could someone post an answer that pulls everything together?

a. the algorithm is O(n^2). don't know why, though! I ran the program and turned on the watcher, and it took somehting like 435561 actual steps (it ran 435561 lines of code) to make it larger. I can't determine though from the actual code why it is.
b. The algorithm is O(n) because each function is performing a linear search. The first function goes through each item in a list and evaluates whether the item isi equal to the ‘something’ input. Depending on the result, the function will print “Found it!” or “Not found”. The second function goes through each pixel in the picture, looks to see if it is close to the given color, and if so, returns a changed color. What’s happening with this algorithm is a straight-forward linear search, where the computer goes through all of the little parts of whatever you’re looking at, and modifies them given a certain set of conditions.

The second algorithm is O(n^2) because it has nested loops (nested loops of O(n) –> O(n^2)!
The next two have O(n) because they go through each pixel or sample.

I just don't know what or how to determine the Big O of the first one! :-\

It looks to me like part a is O(2n) because it's copying the input exactly 2 times larger.

Link to this Page

Fall2004 Final Exam Review last edited on 29 January 2006 at 7:14 pm by r80h18.res.gatech.edu