Problem Set 10
CIS 166 & CMP 230, Introductory Programming
Lehman College, City University of New York
Fall 2012

Due Date: midnight, Friday, 14 December.

This assignment focuses on basic searching and sorting from Chapter 13.

Submit the following programs via Blackboard:

1. Write a program that asks the user for a name of a file, and a keyword and then prints out the first line the keyword appears.
   Note: you can use the search from this chapter or built-in python functions.


2. Modify the selectionSort (from Chapter 13 of the book or Zelle's website) to sort lists of string ignoring case. For example, the list, ["Amy", "aardvark", "Amsterdam", "ape", "Alice"] should be alphabetized as ["aardvark", "Alice", "Amsterdam", "Amy", "ape"].


3. Implement the Insertion Sort algorithm

   	    function insertionSort(array A)
   	       for i from 1 to length[A]-1 do
   	          value := A[i] 
   		  j := i-1
   		  while j >= 0 and A[j] > value do
   		     A[j+1] := A[j]
   		     j := j-1
   		  done
   		  A[j+1] := value
   	       done
            

   (pseudocode from Rosetta Code )

   Write a main program that demonstrates that your insertion sort function works.

   (Hint: this does not have to be a graphics program, printing the list before and after is fine.)

4. Turtle graphics are a built-in module of python that allows you to draw by moving a "turtle" (the cursor) around the screen. The basic functions are:
   • left(degs): turns your turtle left degs degrees
   • right(degs): turns your turtle left degs degrees
   • forward(s): moves your turtle forward s steps
   • backward(s): moves your turtle forward s steps

   The following program uses recursion to draw a square spiral:

               #From http://interactivepython.org/courselib/static/pythonds/Recursion/graphical.html
   
   	    import turtle
   
               #This function draws a line, turns right, and calls itself
   	    #  to draw a shorter line:
   	    def drawSpiral(t,lineLength):
                  if lineLength > 0:
                     t.forward(lineLength)
                     t.right(90)
                     drawSpiral(t, lineLength-5)
   
   	    def main():
   	       #Set up a turtle:
   	       myTurtle = turtle.Turtle()
   
   	       #Set up a graphics window:
   	       myWin = turtle.Screen()
   
   	       #Call the function that will draw a spiral
   	       drawSpiral(myTurtle,150)
   
   	       #After mouse click, close window
   	       myWin.exitonclick()
   
   	    main()
            

   Modify the program so that it draws a triangular spiral.

   (Hint: Think about the difference about between a square and a triangle. You only need to modify one line of code.)

5. Chapter 13, #8. - (Hint: use the turtle module from above, instead of implementing each function as suggested in the last paragraph.)

For more information on using Blackboard, see the first lab.