Summary

• Class 00 - 17-January-2012
• Class 01 - 24-January-2012
• Class 02 - 31-January-2012
• Class 03 - 7-February-2012
• Class 04 - 14-February-2012
• Deloitte Contest - 25-February-2012
• Class 05 - 28-February-2012
• Class 06 - 6-March-2012
• Class 07 - 13-March-2012
• Class 08 - 20-March-2012
• Class 09 - 27-March-2012
• Class 10 - 3-April-2012
• Class 11 - 17-April-2012
• Class 12 - 24-April-2012
• Final - 1-May-2012

Return to Class Main Page

Class 00: 17-January-2012

• No new poeople -- bummer. So no need to introduce myself or cover class rules...
• We do have Deloitte Contest coming up:
  • Feb 25
  • Reg deadline Feb 3
  • Need to pick teams (1-3)
  • Need to determine how to get there (carpool or request funds for van rental)
  • Deloitte Contest Web Site
• Talked a little about ACM
• Discussed if class start tiem should move to 5:30 PM
• problems discussed:

Return to Class Main Page

Class 01: 24-January-2012

• Did have some new folks -- very briefly covered rules.
• We do have Deloitte Contest coming up:
  • Feb 25
  • Reg deadline Feb 3
  • Need to pick teams (1-3) BY NEXT CLASS
  • Need to determine how to get there (carpool or request funds for van rental)
  • Deloitte Contest Web Site
• Problems discussed:

Return to Class Main Page

Class 02: 31-January-2012

• Teams chosen for Deloitte Contest -- see Deloitte Contest Info for team info.
• The topic for today was Flood Fill
  • Wikipedia link
  • I explained the flood fill with the example of pouring a liquid (chocolate suace) on to a surface (bowl of ice cream)
  • We started with simple problems that could be solved with flood fill and moved toward more difficult ones.
  • I stepped through my solution for problem572 - Oil Deposits.
  • General ideas about flood fill:
    • You need a way to determine what cells are "adjacent" to your current location. Simple examples include left, right, up, down or the the 8 pixels around a center one in a square grid. But the idea extends easily to anything (3D - 532 - Dungeon Master, hexes - 260 - Il Gioco dell'X ...).
    • You also need to decide whether to do breadth first or depth first. Depth first can be implemented with a very simple recursive method:

      fill(int x, int y)
       BEGIN
          map(x,y) = FULL
          FOR x1,y1=neighborOf(x,y)
              if (EMPTY == map(x1,y1))
                  fill(x1,y1)
       END
      

      This method will look to the first neighbor and if it is empty, it will call fill with that neighbor. This results in filling in one direction as far as possible, and then backing out of the recursion.
  • The flood fill can also be used to solve mazes. If you were to not merely mark the spots as full, but marked them with a distance, you could find the optimal answer. Take the following conditions:
    • empty spots have a 0
    • Walls have a negative value
    Consider this code:

    fill(int x, int y, int level)
     BEGIN
        map(x,y) = level
        level = level + 1
        FOR x1,y1=neighborOf(x,y)
            if ((0 == map(x1,y1)) OR (level < map(x1,y1))
                fill(x1, y1, level)
     END
    

    This algorithm should work. Whatever value is stored in the goal position after it completes is the minimum number of steps.

    The problem with this algorithm is that it will often have to redo steps. The code level < map(x1,y1) accomplishes the backtracking by replacing longer paths with shorter ones.

    This is a drawback of a depth first approach. If we do breadth first, we should avoid this problem (look at all neighbors of the current point before going on to the next point). To do this, we are going to have to make a FIFO queue to store neighbors in.

    fill(int x, int y, int level)
     BEGIN
        level = level + 1
        FOR x1,y1=neighborOf(x,y)
            if (0 == map(x1,y1))
                map(x1,y1) = level
                enqueue(x1, y1)
        WHILE NOT EMPTY(queue)
            x1,y1 = dequeue()
            fill(x1, y1, map(x1, y1))
     END
    

    By setting all the values of all the neighbors, before processing any of the neighbors, you should eliminate the need for backtrack.
• Problems discussed:

Return to Class Main Page

Class 03: 7-February-2012

• Contest at Deloitte coming up
  • Talked about approach to contest
  • Time/Computer allocation
  • How as you tire it becomes difficult to start a problem from scratch, so it may be advisable sacrifice time up front and develope "solutions" for all problems you intend to solve
  • Mentioned value in typing in stubs and creating directory structure to hold each problem. My approach would be:
    • Make a directory for each problem
    • Possibly put a stub in each directory, certainly type in a stub that can be copied
    • Use free time to type in input data for each problem (at least the ones that you are planning to try)
  • Discussed taking a stapler and bursting the problem set to individual problems. COnsider taking a notebook or folders to organize with
  • Always print what you have when you leave the keyboard
  • Consider breaking each problem into pieces
    • Basic stub
    • Get data read in
    • Dump routine to ensure data was loaded correctly
    • Solve problem
  • I referred to the Approach web page to show some ideas related to approaching a programming contest. This page has been updated a lot. You should visit it again.
  • Then did a VERY brief overview of Floyd-Warshall Algorithm.
  • Here are the basic steps:
    • Algorithm calculates shortest path between each pair of points
    • Build an adjacency matrix
    • Run algorithm on matrix
    • Look up answer
  • Algorithm can be modified to display actual path for each best answer)
  • Dynamic programming - calculated knowledge retained for later use avoiding redundant computation
• Problem discussed:

Return to Class Main Page

Class 04: 14-February-2012

• Contest at Deloitte coming up
  • Once more discussed the upcoming contest
  • Revamped Approach web page
• Problem discussed:

Return to Class Main Page

Class contest: 25-February-2012

• Nice uneventful ride to Hattiesburg (after late start)
• Food was good
• I was able to compete (started late, talked a lot), solved 3 problems

Return to Class Main Page

Class 05: 28-February-2012

• Covered the Deloitte Contest problem set
• Refer to Deloitte Page for the problem set.

Return to Class Main Page

Class 06: 6-March-2012

• Discussed Programming as an art or a science
• Covered several stories

Return to Class Main Page

Class 07: 13-March-2012

• Greedy Algorithms
  • Mandatory Wikipedia definition of Greedy Algorithm
  • My definition: an algorthm that takes the best current choice at all times
  • Classic example: Making change

Return to Class Main Page

Class 08: 20-March-2012

• Discussed software distribution, what percentage a publisher gets.
• Number Theory
• Problem discussed:

Return to Class Main Page

Class 09: 27-March-2012

• Took a first cut at Computational Geometry
• Computational Geometry
• Problem discussed:

Return to Class Main Page

Class 10: 3-April-2012

• Vim Intro - spent some time on VIM. Covered the basics.
• ACU Contest 2 review

Return to Class Main Page

Class 11: 17-April-2012

• Upcoming events:
  • Register for class -- 6 folks so far
  • April 19 -- Election Meeting
  • April 26 -- ACM/IEEE BBQ
  • April 27 -- third ACU contest
  • May 1 -- Final
• Timeline for next Regional:
  • Summer practices - continue on Tuesday night
  • Aug 20 - classes begin
  • Aug 21 - first contest class
  • Aug 28 - second contest class
  • Sep 1 - North Texas Football Game (home)
  • Sep 3 - Labor Day Holiday
  • Sep 4 - third contest class
  • Sep 8 - Washington Football Game (home)
  • Sep 11 - fourth contest class
  • Sep 14 - teams picked
  • Sep 15 - Idaho Football Game (home)
  • Sep 22 - Auburn Football Game (away)
  • Sep 22 - practice contest (tentative)
  • Sep 29 - Towson Football Game (home)
  • Oct 6 - Florida Football Game (away)
  • Oct 6 - practice contest (if Sep 22 does not work)
  • Oct 13 - South Carolina Football Game (home)
  • Oct 18-19 - Fall Holiday
  • Oct 19-20 - tenative date for regional (maybe 27)
  • Oct 20 - Texas A&M Football Game (away)
• How do you get better?
  • As an individual?
    • Solve more problems at UVA
    • Solve problems systematically (by category)
    • Study things like Algorithms book, Programming Challenges, ...
    • Study math
    • practice editing, syntax, debugging
    • study libraries
    • Show someboady else
    • develop templates
    • develop a library
    • arithmetic
  • As a team?
    • Solve problems with others
    • compete
    • solve problems jointly with others
    • discuss problems
    • look at other peoples' code
  • What other skills can you improve?
    • Linux skills
    • vi/emacs
    • debuggers
    • IDEs (eclipse, ...)
    • svn?
    • Other languages (python, perl, php, C, C++, ...)

Return to Class Main Page

Class 12: 24-April-2012

Return to Class Main Page

Class 13: 1-May-2012

Return to Class Main Page