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

CS4522 Final Exam Postmortem

General Comments

The exam was designed to be a cumulative take-home exam over the course of one week. Very little sample code was provided, under the assumption that having access to the course textbook, online notes, and JES software would allow students to practice finding and using relevant sample code.

The exam was intended to take 6-8 hours to complete. However, students reported spending as many as 12-16 hours (or more) working through the questions. Assuming that most of that time was spent on the programming questions, either the number or the complexity of the programming questions should probably be re-examined for future exams.

The topics on which the exam focused most heavily included:

The overall average on the exam was in the mid-B range.

Question 1, Part I

The Problem (abbreviated)

Write a function called findgtg() that takes one input: a string containing all or part of a student’s name. If the name is found in the 1315students.txt file, the function should print out the student’s name and gtg number. If multiple matches are found, the function should print the information for each potential match. If the name is not found in the file at all, the function should print "Student not found."

A Solution (courtesy of Lee Inman Farabaugh)

def findgtg(string):
  programfile = "1315students.txt"
  newfile = open(programfile,"rt")
  students = newfile.read()
  newfile.close()
  studentlist = students.split('\n')
  newstudentlist = []
  for list in studentlist:
    newstudentlist = newstudentlist + [list.split("/")]
  notFound = 1
  for line in newstudentlist:
    if line[1].find(string)<>-1:
      print line[1] + ": " + line[0]
      notFound = 0
  if notFound == 1:      
    print "Student not found."

Comments

Most students had good solutions to this question, although they varied widely in their complexity.

Many students relied on getMediaPath() when opening and reading from the data file. This approach only works when the media path has not been set or has been set to the JES directory; the solution above works in all cases.

An alternative to reading the entire contents of the file using file.read() and splitting it on the newlines using contents.split('\n') is to just use the single function file.readlines(), which does both in a single step.

Splitting the file into lines and then splitting each line on the slashes made for the most accurate implementations of findgtg() and side-stepped the problem of accidentally finding TA names as part of the search.

Question 1, Part II

The Problem

Once you have a working findgtg() function, write a second function called findgtgs() that takes one input: a list of strings, each containing all or part of a student’s name. Your findgtgs() function should use functional programming and your existing findgtg() function to print out any matching student names and gtg numbers for each name in the input list.

A Solution (courtesy of Susan Wyche; slightly modified)

def findgtgs(list):
  for i in list:
    apply(findgtg,i)

Another Solution (courtesy of Gina Calcaterra)

def findgtgs(listOfStrings):
  for string in listOfStrings:
    findgtg(string)

Comments

Although we were looking for implentations that used one of the functional programming functions apply(), filter(), or map(), the question turned out to be easily solved using a for loop (which all but one student used). Both kinds of solutions were accepted.

Question 2, Part I

The Problem (abbreviated)

Write a function named infinitePicture() which takes as its input a single Picture object. If the specified picture has a pure green rectangular region, like either of the two pictures above, then your function should replace it by scaling and copying the entire picture (the green area included) into that region. This process should continue until all of the green has been replaced. Your function should return a Picture object containing the completed "infinite" picture. (Hint: this is a problem for which recursion might be useful!)

A Solution (courtesy of Cynthia Morneweck)

def infinitePicture(picture):
  target1 = findGreenUpperLeft(picture)
  target2 = findGreenLowerRight(picture)
  targetX1 = target1[0]
  targetY1 = target1[1]
  targetX2 = target2[0]
  targetY2 = target2[1]
  print targetX1
  print targetX2
  print targetY1
  print targetY2
  if (targetY1 == -1) or (targetY2 == -1):
    return
  target = deepCopy(picture)
  copySourceToTargetArea(picture,target,targetX1,targetY1,targetX2,targetY2)
  print "One loop done."
  infinitePicture(target)
  return target

Another Solution (courtesy of Jennifer Wiley; slightly modified)

def infinitePicture(image):
  picture = deepCopy(image)
  topleftX = 1
  while(topleftX <> -1):
    topLeft = findGreenUpperLeft(picture)
    topleftX = topLeft[0]
    printNow(topleftX)
    topleftY = topLeft[1]
    printNow(topleftY)
    bottomRight = findGreenLowerRight(picture)
    bottomrightX = bottomRight[0]
    printNow(bottomrightX)
    bottomrightY = bottomRight[1]
    printNow(bottomrightY)
    if topleftX <> -1:  
      newpicture = copySourceToTargetArea(image, picture, topleftX, topleftY, bottomrightX, bottomrightY)
  return(newpicture)

Comments

Most students came up with a working implementation of this problem, as well. Although most of the solutions did use recursion (as in the first example), it was possible – and very tractable, in this case – to use a while loop to accomplish the desired effect as well (hence the second example).

For a recursive solution, the idea was to simplify the problem (by copying the original picture into whatever green rectangle was left in the current picture) and then using recursion to solve the "simpler" case – a picture with a smaller (or non-existent) green rectangle.

The key to solving this problem was determining what condition indicates that the problem is solved. In this case, if either findGreenUpperLeft() or findGreenLowerRight() returned (-1, -1), then all the green had been replaced from the picture and the function could exit. Note that it isn't necessary to check both, as they both sequentially walk through all the pixels in the image, just in a different order. If one comes up empty, then both will.

The only other trick to solving the problem was knowing where to use the deepCopy() function, which was provided to get around parameter-passing side-effects.

In retrospect, the name of the question/problem probably could have been clearer. There may have been some confusion between the idea of "infinite pictures" and the programming problem of "infinite loops."

Question 2, Part II

The Problem

Add a comment to your program file (on its own line, before the program code begins) describing the complexity (in "Big-O" notation) of your algorithm.

Comments

For each step of creating the "infinite picture", the algorithm should have taken something on the order of 3n or 4n steps, where n is the number of pixels in the image. It takes at most n steps to walk through the picture and find the upper left corner of the green rectangle, at most n steps to walk backward through the picture to find the lower right corner of the rectangle, and at most n steps to copy the original picture into the green rectangle's area. If a new copy of the original picture wasn't being loaded from disk during each recursion, a call to the deepCopy() function was also needed at some point, which adds at most another n steps. Regardless whether the number of steps is 3n or 4n, the complexity of one pass through the function is linearly proportional to the number of pixels in the image, hence O(n).

From here, the answer gets fuzzier (a by-product of the fact that we wanted to have students analyze a function's complexity, but also keep the number of overall problems in the exam down to a minimum).

One could reasonably argue that the number of times the recursion (or iteration through a while loop) needs to happen is a small, finite number – say, for example, k. Assuming that's true, the overall complexity of the algorithm is k * O(n) or O(kn), which just reduces to O(n).

Another plausible explanation would be that the green rectangle represents a fraction of the pixels in the image. Supposing that about half of the image is made up of green pixels, after one pass through the algorithm, the whole of the picture will be squeezed into that area and the remaining amount of green will be about one fourth of the pixels in the image. This follows the same logic as splitting the phone book in halves to find a name, so the overall complexity would also be approximately the same: O(ln n). This has to be multiplied by the complexity for each of the individual passes, so we arrive at O(ln n) * O(n) = O(nln n). (Technically, the base of the log (ln) likely won't be two, but will instead be related to the proportion of the pixels in the original picture that are green – a fairly fine point.)

While either of these answers would be fine, many students simply explained that the complexity would be close to O(n) and certainly less than O(n2). This is also acceptable, given the scope of complexity covered in the course. As long as students understand that this is a reasonably tractable solution (i.e. it won't take forever to run), that's probably sufficient for their purposes.

Question 2, Extra Credit

The Problem

Create your own self-similar image using your infinitePicture() function and a source image of your own design. (Hints: (1) Keep the pure green pixels away from the edges of the source picture. (2) Save your source picture in GIF format, since JPG compression creates artifacts in large, solid-colored regions.)

The Solutions

Uploaded Image: gtg021k.jpg
(courtesy of Lee Inman Farabaugh)

Uploaded Image: gtg010z.jpg
(courtesy of Andrew Miller)

Uploaded Image: gte836p.jpg
(courtesy of Jennifer Wiley)

Question 3, Part A

The Problem

How does Google News generate its news page if Google employs no reporters? Explain both how Google gets the stories and how the page is generated.

A Solution (courtesy of Cynthia Morneweck)

Google news does not need reporters because they pull news from other web sources and input that into their site. Google just writes code that looks at other web pages' news. If they want the three top international news headlines from CNN, they write code that actually goes to CNN, reads the page and looks for certain html code that can be grabbed and put into a Google page. Google can "wrap" other html around the grabbed text to make it look naturally integrated into the Google page. The reader can not tell that it is from CNN.

Comments

Any explanation that captured the notion of a program "mining" other news sites and then aggregating that infomation into a web page served by Google was acceptable.

Question 3, Part B

The Problem

Why does Java typically compile to a machine language for a CPU that doesn’t physically exist? What is the market advantage of such a scheme? What is a disadvantage?

A Solution (courtesy of Susan Wyche)

Java programs typically don't compile to machine language. Every processor has its own machine language. The people who invented Java also invented a "make-believe" processor a virtual machine. Java compiles to run on a the virtual machine - the Java Virtual Machine (JVM).

A virtual machine is software that creates an environment between the computer platform and the end-user in which the end user can operate software1. Note Java can be compiled to a machine language - it's just not typical2.

ADVANTAGES

DISADVANTAGE

1 http://en.wikipedia.org/wiki/Virtual_machine
2 p. 315, Media Comp. Textbook
3 http://en.wikipedia.org/wiki/Java_virtual_machine

Question 3, Part C

The Problem

Name three characteristics of object-oriented programming that set it apart from traditional, procedural programming. Explain (briefly!) why these characteristics make the object-oriented paradigm a useful way to design programs.

A Solution (courtesy of Gina Calcaterra)

Three characteristics that set it apart from traditional, procedural programming are 1) Encapsulation - you have objects which encapsulate data and behavior, allowing you to change the name of an instance variable and all the methods that use it, for example, all in one place. Having the variables and methods all in the same places faciliates changes that need to be made. 2) Aggregation - We can have lots of objects doing useful things, and objects are easy to create. 3) Polymorphism - we can declare classes that are inherited by other classes, and the instances of the child class automatically have all the data and behavior of the parent class, and can also add additional behavior. Thus, we can use the same object type to accomplish different goals.

Another Solution (courtesy of Susan Wyche)

1) Procedural programing is about verbs - tell the computer to do this. It is about actions. Object-oriented programming is noun-oriented programming.
2) One of the principal advantages of object-oriented programming techniques over procedural programming techniques is that they enable programmers to create modules (or part of a program) that do not need to be changed when a new type of object is added. A programmer can simply create a new object that inherits many of its features from existing objects. This makes object-oriented programs easier to modify, more flexible, and more adaptable1.
3) In OOP code and data are merged into an indivisible item or an object. In procedural programming the code and data are separate.

1 http://www.webopedia.com/TERM/M/module.html

Comments

Any of these type of respsonses were accepted. The three from the first example nice answers since they help to define other terms often affiliated with O-O programming; the three from the second are more practical differences between procedural and O-O programming.

Question 3, Part D

The Problem

What is meant by "digitizing media?" Why would some audiophiles shun digital media, such as CDs, and instead prefer analog recordings, such as vinyl records?

A Solution (courtesy of Lee Inman Farabaugh)

To digitize sound means to take the flow of waves that make up the sound and convert them to numbers. Digitizing sound creates samples. Samples look like very narrow rectangles placed next to each other that follow the same line as the original sound curve. Audiophiles might shun digitial media because the samples are just an approximation (albeit an almost completely accurate one) of the true sound waves. Analog recordings, such as records, produce sounds based on sound waves, while digital recordings, such as CDs, produce sounds based on digital samples.

Question 3, Part E

The Problem

What does the notation "Big-O" represent? Why would a programmer care whether a particular algorithm was O(n) or O(n2)? Why might an information architect or interface designer care?

A Solution (courtesy of Gina Calcaterra)

The "Big-O" notation is used by computer scientists to refer to the magnitude of the running time of an algorithm; in other words, its computational complexity. The Big-O notation gives you an idea of how much slower the program will run as the input data gets larger. The reason a programmer would care about the computational complexity of an algorithm is because if a particular program can be written with an algorithm that is of complexity O(n) rather than O(n2), it means the program will a) run faster and b) take up less memory. Programmers who are working with media may be especially concerned about complexity, because a large amount of memory is required to hold this type of data. An information architect or interface designer would care about the complexity of the algorithms because the complexity influences the response time to user interactions with the interface. That is, if a highly complex O(n2) algorithm is generating the interface, then if the user makes a button selection and expects feedback from that selection, they may be waiting for the response for quite a while as the program is chugging away. This could impair the user experience, which makes it a large concern for UI designers.

Comments

I (Steve) think that the most important part of this question is the last part – why should HCC students care about complexity? Any thoughtful answer was fine; the point is that the limitations of the computer have a significant impact on human-computer interaction and computer-mediated human-human interaction.


Question 4, Part I

The Problem (abbreviated)

Write a class called SlideShowFrame that subclasses ImageFrame and provides a slide show of a single directory of images. SlideShowFrame should include (at a minimum) the following class methods:
SlideShowFrame will necessarily have several instance variables; you can define as many as you need and name them whatever you’d like. However, you must implement and maintain an instance variable named isDone. When your SlideShowFrame is showing any picture except the last JPG image in the slide show directory, isDone should be equal to 0. When your SlideShowFrame is showing the last JPG image in the slide show directory, isDone should be equal to 1.

A Solution (courtesy of Andrew Miller)

class SlideShowFrame(ImageFrame):
  def __init__(self,directory):
    self.index=0
    self.listing=[]
    for file in os.listdir(directory):
      if file.endswith(".jpg") or file.endswith(".gif"):
        self.listing.append(str(file))
        self.index=self.index+1
    self.total=self.index
    self.directory=directory
    self.isDone=0
    printNow(self.total)
    self.index=0
    self.jesImage=makePicture(directory+"""//"""+str(self.listing[self.index]))
    ImageFrame.__init__(self,self.jesImage)

  def next(self):
    if self.total-self.index-1!=0:
      self.index=self.index+1
      self.jesImage=makePicture(self.directory+"""//"""+str(self.listing[self.index]))    
      self.setImage(self.jesImage)
      self.isDone=0
    else:
      self.isDone=1

  def prev(self):  
    if self.index!=0:
      self.index=self.index-1
      self.jesImage=makePicture(self.directory+"""//"""+str(self.listing[self.index]))    
      self.setImage(self.jesImage)
    self.isDone=0

Comments

Solving this part of the problem was probably – and perhaps unwisely – the hardest of the four. Coming up with a reasonable solution required that students figure out what data items would need to be stored in the class for the required methods to work properly, recall the syntax to initialize those data items and recall them in the class methods, keep track of which picture was being displayed, correctly compute the next and previous pictures relative to the current one, and maintain a "flag" variable so that programs using this class could determine when all pictures had been displayed. This was probably too much to ask in a time-bound exam, given the lack of closely-related sample code and the interdependence of the requirements – particularly in a single step. While several students did come up with very close solutions, it was apparent that many of them struggled with all of the syntax and housekeeping issues related to writing a class like this one.

For future exams, providing an implementation of this class would probably be a reasonable starting point to a question asking for solutions to the other three parts.

Question 4, Part II

The Problem (abbreviated)

Write a function named musicalSlideShow() that uses your SlideShowFrame class to display an automated slide show of all the pictures in a directory, playing the same sound as each is displayed. musicalSlideShow() should take two parameters: the path of the directory containing the images to be displayed, and a Sound object that should be played in the background during the slide show.

A Solution

def musicalSlideShow(directory, sound):
  win=SlideShowFrame(directory)
  blockingPlay(sound)
  while win.isDone==0:
    win.next()
    blockingPlay(sound)

Comments

This section was a relatively straightforward demonstration of using a class, given knowledge of its methods and attributes (programming by contract). Even without a working implementation of the SlideShowFrame class, it was assumed that students would be able to come up with at least a first draft of such a function, given the description of SlideShowFrame given in Part I.

It was interesting that nobody used the isDone instance variable/attribute to figure out when all of the pictures in the directory had been displayed, especially since it was such a blatant requirement for Part I. Instead, everyone either used other class variables or manually counted the files or pictures in the directory to determine when they were finished.

Question 4, Part III

The Problem (abbreviated)

Write a class called ArtisticSlideShowFrame that subclasses SlideShowFrame, providing all of the original class’ functionality as well as the additional capability to display pictures either in their original format or with one artistic effect (such as grayscale, posterization, or some other image manipulation) applied to all of them.

Your implementation of the ArtisticSlideShowFrame class should include three additional methods over and above the methods defined in the SlideShowFrame superclass: a setArtistic() method, an isArtistic() method, and a "helper" method that takes a single Picture object as input and modifies it artistically in some way using the object-oriented methods provided by the Picture and Pixel classes (see pages 346 349 in the book for some examples).

A Solution (courtesy of Andrew Miller)

class ArtisticSlideShowFrame(SlideShowFrame):
  def __init__(self, directory):
    SlideShowFrame.__init__(self, directory)
    self.displayMode=0

  def grue(self, pic):
    for p in getPixels(pic):
      pblue=p.getBlue()
      p.setBlue(p.getGreen())
      p.setGreen(pblue)
    return pic

  def setArtistic(self, displayMode):
    self.displayMode=displayMode
    if self.displayMode==1:
      self.grue(self.jesImage)
      self.setImage(self.jesImage)

  def isArtistic(self):
    if self.displayMode==0:
      return 0
    return 1

  def next(self):
    if self.total-self.index-1!=0:
      self.index=self.index+1
      self.jesImage=makePicture(self.directory+"""//"""+str(self.listing[self.index]))
      if self.isArtistic()==1:
        self.grue(self.jesImage)    
      self.setImage(self.jesImage)
      self.isDone=0
    else:
      self.isDone=1

  def prev(self):  
    if self.index!=0:
      self.index=self.index-1
      self.jesImage=makePicture(self.directory+"""//"""+str(self.listing[self.index])) 
      if self.isArtistic()==1:
        self.grue(self.jesImage)         
      self.setImage(self.jesImage)
    self.isDone=0

Comments

Completing this section of the problem required five steps: remembering to call the superclass constructor inside this class' __init__() function, addition of a new instance variable in the constructor to keep track of which mode (normal/artistic) the instance is in, implementing a setArtistic() method to change that instance variable and re-call setImage(), implementing an isArtistic() method to return the instance variable's value, and modification of either prev() and next() or setImage() to render the proper version of the picture, based on the instance variable's value.

Most students who got past Part I were able to complete this part, since it represented a relatively minor difference from the SlideShowFrame code. The specification of the problem was a bit muddled about what should happen when setArtistic() was called, with regards to repainting the current image, and this caused the biggest variation in the solutions.

Question 4, Part IV

The Problem (abbreviated)

Write a function named interactiveSlideShow() that uses your ArtisticSlideShowFrame class to display an user-controlled multimedia slide show of all the pictures in the directory. interactiveSlideShow() should take two parameters: the path of the directory containing the images to be displayed, and a Sound object that the user may play in the background during the slide show.

Modification to the Problem (abbreviated)

Andrew Miller pointed out a problem in Question 4, Part IV and how it interacts with Part III of the same problem. In order to minimize everyone's grief in solving this problem (sorry!!), I want to offer three suggestions, any of which would be acceptable for solving this problem.

A Solution (courtesy of Andrew Miller; follows suggestion 1)

class InteractiveSlideShowClass(ArtisticSlideShowFrame):
  def __init__(self,directory,sound):
    ArtisticSlideShowFrame.__init__(self,directory)
    self.sound=sound
    win2=swing.JFrame("Control Panel", size=(275,100))
    s=swing.JButton("Play Sound", actionPerformed=self.playSound)
    r=swing.JButton(">", actionPerformed=self.next)
    l=swing.JButton("<", actionPerformed=self.prev)
    c=swing.JButton("Grue/Bleen", actionPerformed=self.artsy)
    win2.contentPane.layout = java.awt.BorderLayout()
    win2.contentPane.add(s,java.awt.BorderLayout.SOUTH)
    win2.contentPane.add(r,java.awt.BorderLayout.EAST)
    win2.contentPane.add(l,java.awt.BorderLayout.WEST)
    win2.contentPane.add(c,java.awt.BorderLayout.CENTER)
    win2.visible=1

  def next(self,event):
    if self.total-self.index-1!=0:
      self.index=self.index+1
      self.jesImage=makePicture(self.directory+"""//"""+str(self.listing[self.index]))
      if self.isArtistic()==1:
        self.grue(self.jesImage)    
      self.setImage(self.jesImage)
      self.isDone=0
    else:
      self.isDone=1

  def prev(self,event):  
    if self.index!=0:
      self.index=self.index-1
      self.jesImage=makePicture(self.directory+"""//"""+str(self.listing[self.index])) 
      if self.isArtistic()==1:
        self.grue(self.jesImage)         
      self.setImage(self.jesImage)
    self.isDone=0

  def artsy(self, event):
      self.grue(self.jesImage)
      self.setImage(self.jesImage)
      if self.isArtistic()==0:
        self.displayMode=1
      else:
        self.displayMode=0
  
  def playSound(self,event):
    play(self.sound)

Another Solution (follows suggestion 2)

class GUIFrame:
  def __init__(self, artisticSSInstance, sound):
    self.artisticSSInstance = artisticSSInstance
    self.sound = sound
    
    win = swing.JFrame('Control Panel')
    win.setSize(275,100)
    win.contentPane.layout = java.awt.BorderLayout()
    prevButton = swing.JButton('<<', actionPerformed=self.prev)
    nextButton = swing.JButton('>>', actionPerformed=self.next)
    artisticButton = swing.JButton('Toggle effect', actionPerformed=self.switch)
    soundButton = swing.JButton('Play Sound', actionPerformed=self.soundOff)
    win.contentPane.add(prevButton, java.awt.BorderLayout.WEST)
    win.contentPane.add(nextButton, java.awt.BorderLayout.EAST)
    win.contentPane.add(artisticButton, java.awt.BorderLayout.CENTER)
    win.contentPane.add(soundButton, java.awt.BorderLayout.SOUTH)
    win.visible = 1

  def prev(self, event):
    self.artisticSSInstance.prev()

  def next(self, event):
    self.artisticSSInstance.next()

  def switch(self, event):
    if self.artisticSSInstance.isArtistic():
      self.artisticSSInstance.setArtistic(0)
    else:
      self.artisticSSInstance.setArtistic(1)

  def soundOff(self, event):
    play(self.sound)

def interactiveSlideShow(directory,sound):
  slideShow = ArtisticSlideShowFrame(directory)
  gui = GUIFrame(slideShow, sound)


Comments

The final part of the question was intended to be an exercise in creating a Swing GUI, using a layout manager, and directly connecting the buttons to the class methods of the previously constructed ArtisticSlideShowFrame (skills that should come in very handy for the follow-on course, CS 6452). However, the very limited sample code demonstrating the creation of interactive GUIs and the difference in specification between the parameterless next() and prev() methods in ArtisticSlideShowFrame and event-handling methods which take the event as a parameter made the problem more complicated than it was intended to be.

The provided hint and two sample approaches demonstrate the two main approaches for solving the problem.

Link to this Page