Summary

• Class 00 - 24-August-2011
• Class 01 - 31-August-2011
• Class 02 - 7-September-2011
• Class 03 - 14-September-2011
• Class 04 - 21-September-2011
• Class 05 - 28-September-2011
• Class 06 - 5-October-2011
• Class 07 - 12-October-2011
• Practice Contest - 15-October-2011
• Class 08 - 19-October-2011
• Class 09 - 26-October-2011
• Class regional - 29-October-2011
• Class 10 - 2-November-2011
• Class 11 - 9-November-2011
• Class 12 - 16-November-2011
• Final - 30-November-2011

Return to Class Main Page

Class 00: 24-August-2011

• Welcome!
• Introduce myself (short bio)
• More or less covered the course outline and handed it out
• Things to talk about:
  • ACM International
  • ACM Local Chapter
  • Contest in General
  • Our Regional
  • Why this class
  • talk about coaching?
• Things to do:
  • Made sure to point out that class members MUST check the web site each week (if for no other reason, so that they know where class meets).
  • Register at the Online Judge
  • Read the Class Web Site
  • Read the SCUSA Web Site
  • Join ACM local chapter
  • Learn Linux, command line, vi/vim, at least
problems discussed:

Return to Class Main Page

Class 01: 31-August-2011

• Talked about this book a little:
  The Psychology of Computer Programming - Silver Anniversary Edition
  Author: Gerald M. Weinberg
  Publisher: Dorset House
  ISBN: 0-932633-42-0
  Description: This book was first written over 25 years ago - and it is possibly more correct now than when it was written. Even though some of the examples seem a little dated, if you plan to make a living in the computer field, you should read this book. The Silver Anniversary Edition includes chapter-by-chapter updates by the original author.
• Software/programs are written by people (sometimes an individual, but often a group). People have personalities. It is natural to expect some of their personailty to show up in their code. Does the fact that most large projects are written by groups account for the variances that exist in the user interface/operation of a program?
• Quick reference to conscious mind a single core with very deliberate execution, linear computer vs subconscious as multi-core (many, many cores) with no control over what thread is running where.
• Writers learn to write by reading other writers. Why don;t programmers spend more time reading other folks code? Is there little to be learned? Are we doomed ot repeat the smae mistakes since we don't learn from others (by reading htie code)?
• Explained old time Lab and pyramid.
• Talked about letting folks explain their code to me -- producing an almost exhaustive list of all the wrong ways to do my homework.
• Mentioned Donald Knuth. Briefly mentioned TeX.
• First Program due by September 7
  Submission Process (version 0.1)
  • Create an account at the UVa Online Judge
  • Write a working solution for one of the problems handed out last week or this week
  • Submit it to the online judge and get back a correct
  • Make sure source code includes:
    • Your name
    • problem number
    • Problem name
  • Mail your source to class@isaac.lsu.edu
• I mentioned the Large Number Library for C++ that was written in the past. Also, here is an example Sieve of Eratosthenes implementation.
• Problems covered:

Return to Class Main Page

Class 02: 7-September-2011

• Steve Brandt was a guess in our class and is encouraging his kids to come
• Due date for first program. Observations:
  • Most folks did not submit
  • Most did not read the sumamry page explaining how/what to submit. So here we go again:
    Submission Process (version 0.2)
    • Create an account at the UVa Online Judge
    • Write a working solution for one of the problems handed out last week or this week
    • Submit it to the online judge and get back a correct
    • Make sure source code includes:
      • Your name
      • Problem number
      • Problem name
      • Date
    • Send mail to class@isaac.lsu.edua
      • In the body of the message include: your name, problem number, problem name
      • ATTACH your single source code file that you submitted
• Spent a little time looking briefly at some of the submissions (should have referenced the concept that reading code has value). I think folks got the idea that sticking comments in code with anme and problem info is wise.
• Mentioned that I had added a couple of C templates to the homework page -- not a lot of interest.
• In the past I have recommended that a team should have a consistent style to reduce distraction when debugging code.
• Additional suggestions:
  • Modular code - If your short term memory is 5-9 items, maybe each block of code should match this limit (so all of the steps of a piece of code can fit into short-term memory at the same time). Others suggest one screen full is a good max size for a routine (logic being if the entire routine won't fit on a single screen, you can't "see" it all and hence will "forget" part of it).

    Another perspective is that most computing types train themselves to organize hierarchically, we should write code in the same manner: a simple base (main program) that calls a few modules (5-9) that intern call modules until the entire program can be viewed as a tree.

  • Go look into structured programming. Basic ideas include:
    • Single entry/single exit loops
    • priming reads
    • ...
• Question was asked about the overhead associated with objects/methods (sould they be avoided to improve runtime). My answers included several items -- but started with a joke that is often attributed (without proof) to Winston Churchilli, George Bernard Shaw, Groucho Marx and/or Mark Twain:

  Churchill: Madam, would you sleep with me for five million pounds?
      Socialite: My goodness, Mr. Churchill… Well, I suppose… we would have to discuss terms, of course…
      Churchill: Would you sleep with me for five pounds?
      Socialite: Mr. Churchill, what kind of woman do you think I am?!
      Churchill: Madam, we’ve already established that. Now we are haggling about the price.

  The purpose of this "joke" was to point out that efficiency is a continuum -- not a single point. Since we do not chose to code solutions in optimized machine language, we clearly are willing to sacrifice some efficiency. How much is up the individual and the case.

  Based on that observation, the fact that I have recommended modular code, and structured programming shows that efficiecy of run time is less important to me that code reliabilty, provability and ease of reading/debugging.

• Problems covered:

Return to Class Main Page

Class 03: 14-September-2011

• Requests to try and code a problem were made
• So a couple of people tried, discovered these issues:
  • Not as easy as it looks at first glance
  • problem was a little more involved that it looked
  • syntax of language libraries and data type translation is sticky
• Discovered the proposed division by 17 algorithm must actually work
• Talked a little about continuum of data and code. I believe that a given problem can be solved many ways. Each of these ways could be put on a line where one extreme is minimum data use and the other extreme is minimum code use.

  Example: Suppose you need to add random amounts to a total based on a value. Here are three examples that do that:

  Nested If Statements

  if (1 == i)
   { total = total + 17; }
  elseif (2 == i)
   { total = total + 29; }
  elseif (3 == i)
   { total = total + 99; }
  

  Case Stratement

  switch (i)
   { // switch
   Case 1: total = total + 17; break;
   Case 2: total = total + 29; break;
   Case 3: total = total + 99; break;
   } // switch
   

  Array Implementation

   int ary[4] {0, 17, 29, 99};
  
  
   total = total + ary[i];
   

  Example: You wish to test each of the 8 locations around the current location in an array.

  Classic method

   for (i=-1; i<2; i++)
    { //for i
       for (j=-1; j<2; j++)
        { // for j
           if ((0 < ary[i][j) && (0<>i) && (j<>j))
            { // sum up value
               total = total + ary[i][j];
            } // sum up value
        } // for j
    } //for i
  

  Array Method

  int i[7] {-1, -1, -1, 0, 0, 1, 1, 1};
  int j[7] {-1, 0, 1, -1, 1, -1, 0, 1};
  
  /* assume we are processing ary[x][y] */
  
  for (k=0; 8>k; k++)
   { // for k
      if (0 < ary[x+i[k]][y+j[k]])
       { // add it up
          total = total + ary[x+i[k]][y+j[k]];
       } // add it up
   } // for k
  

• Problems covered:

Return to Class Main Page

Class 04: 21-September-2011

• Started with a little Harry Chapin and talked a little about the meaning
• looked at numerous ways to appraoch the 2 problems we talked about
• Revisited the code/data continuum idea.
• Tried to explain the spiral implementation code I did...
  Imagine an array that was 11 x 11 (0..10 are the indicies) and that you are 5,5 (the exact center).
  The 4 points closest to (5,5) are (5,4), (5,6), (4,5) and (6,5) (left, right, down and up)
  The 4 next closest points are (4,4), (4,6), (6,6) and (6,4) -- the diagonal points are a little further away
  

                    F E D E F    
                G D C A 9 A C D G 
                D B 8 7 6 7 8 B D  
              F C 8 5 4 3 4 5 8 C F
              E A 7 4 2 1 2 4 7 A E
              D 9 6 3 1 0 1 3 6 9 D
              E A 7 4 2 1 2 4 7 A E
              F C 8 5 4 3 4 5 8 C F
                D B 8 7 6 7 8 B D
                G D C A 9 A C D G
                    F E D E F 
  
  id  dist   dist    points
  -- ------- -----   ----------------------------------------------------------
  0  sqrt(0) 0     = 0,0
  1  sqrt(1) 1     = 1,0   0,1  -1,0   0,-1
  2  sqrt(2) 1.414 = 1,1  -1,1  -1,-1  1,-1
  3  sqrt(4) 2     = 2,0   0,2  -2,0   0,-2
  4  sqrt(5) 2.236 = 2,1   1,2  -1,2  -2,1  -2,-1 -1,-2  1,-2  2,-1   
  5  sqrt(8) 2.828 = 2,2  -2,2  -2,-2  2,-2
  6  sqrt(9) 3     = 3,0   0,3  -3,0  -3,-3
  7 sqrt(10) 3.162 = 3,1   1,3  -1,3  -3,1  -3,-1 -1,-3  1,-3  3,-1
  8 sqrt(13) 3.606 = 3,2   2,3  -2,3  -3,2  -3,-2 -2,-3  2,-3  3,-2
  9 sqrt(16) 4     = 4,0   0,4  -4,0  -4,-4
  A sqrt(17) 4.123 = 4,1   1,4  -1,4  -4,1  -4,-1 -1,-4  1,-4  4,-1
  B sqrt(18) 4.243 = 3,3  -3,3  -3,-3  3,-3
  C sqrt(20) 4.472 = 4,2   2,4  -2,4  -4,2   -4,-2 -2,-4  2,-4  4,-2
  D sqrt(25) 5     = 5,0   4,3   3,4   0,5   -3,4  -4,3  -5,0  -4,-3 -3,-4  0,-5  3,-4  4,-3
  E sqrt(26) 5.099 = 5,1   1,5  -1,5  -5,1   -5,-1 -1,-5  1,-5  5,-1
  F sqrt(29) 5.385 = 5,2   2,5  -2,5  -5,2   -5,-2 -2,-5  2,-5  5,-2
  G sqrt(32) 5.657 = 4,4  -4,4  -4,-4  4,-4
  

  As you can see, a spiralis a real pain in the you know what to implement. If you tried to do this programatically, the calculations would kill you. With offset arrays:

  x[]={ 0, 1, 0,-1, 0, 1,-1,-1, 1, 2, 0,-2, 0, 2, 1,-1,-2,-2,-1, 1, 2 ...
  y[]={ 0, 0, 1, 0,-1, 1, 1,-1,-1, 0, 2, 0,-2, 1, 2, 2, 1,-1,-2,-2,-1 ...
  
  for (k=0; 17>k; k++)
   { // loop for each spot of the spiral
      process ary[i+x[k][j+y[k]]
   } // loop for each spot of the spiral
  
  

• Problems covered:

Return to Class Main Page

Class 05: 28-September-2011

• what does a programmer do?
  • write code
  • documentation
  • debug
  • design code
  • learn additional languages
• What do we do in class? -- Solve Problems, Listen to stories
  1. Read Problem Statements
  2. Evaluate problem Statements
  3. Look for "issues"
  4. Discuss Implementation Ideas, Algorithms, Data Structures
  5. Designs
  6. Coding
• top down vs bottom up design
  
  • Design evloution over time
    • Beginners tend to do bottom up design because they lack the knowledge to solve a large problem top down.
    • Experienced programmers/software designers tend to do top down.
    • Over time, as a programmer becomes very experienced and the problems become similar, they tend to shift back to bottom up.
  • Bottom up properties
    • write little pieces of code to solve small parts of the problem
    • tend to have multiple different data structures holding same data (because the different small pieces seemed to imply different organization methods)
    • Tendency to write unnecssary code. As more code gets written because obvious that some routines that you thought you would need are not necessary
    • Considerable time spent adjusting calling and parameter passing to make the pieces fit together
    • Final code often lacks coherent design
  • top down properties
    • Consistent code usually (since design flows form center down to edges)
    • APIs get created for calling between major sections of the design
    • Redundant code becomes more obvious so that less code that is more general can be developed
    • Takes longer (apparently) to design but less time to code and debug
• Asked again about reading code...
• compiler -- delete and start over story
• Problems covered:

Return to Class Main Page

Class 06: 5-October-2011

• Class was derailed (for more than a few minutes) as news of Steve Jobs death pushed onto the various mobile devices in the classroom
• Folks urged (begged) to go to icpc.baylor.edu and register.
• Folks urged to divide up into teams
• Talked a little about the regional
• Problems covered:

Return to Class Main Page

Class 07: 12-October-2011

• Check out the NEW view option under upload on the menu on the left. This allows you to browse any uploaded code.
• a little late starting due to ACM meeting that preceeded us
• We discussed the view option
• We talked a good bit about contest
• Urged people to let me know about team membership and team names
• Taalked about practice contest on Oct 15
• Problems covered:

Return to Class Main Page

Class practice00: 15-October-2011

• Practice Contest in Ceba lab
• Problems covered:

Return to Class Main Page

Class 08: 19-October-2011

• Meeting in Ceba Lab
• Problem sets from the Saturday practice were distributed. Folks were teamed up and used the lab linux image and PC^2 to solve some of the problems.
• These problems (from class tonight and Saturday practice) have been added to the homework list -- so you may submit them as homework. Understand that if you wrote a solution jointly, it oes not count as your homework.
• Problems covered:

Return to Class Main Page

Class 09: 26-October-2011

• Discussed stratedgy for upcoming regional
• Discussed swchedule for regional
• Demoed LittleFe, showed TigerTrap Trophy and coin

Return to Class Main Page

Class regional: 29-October-2011

• ACM South Central Regional Programming Contest
• Friday night was the scripting contest
• Saturday was the 5 hour real contest
• Problems covered:

Return to Class Main Page

Class 10: 2-November-2011

• Discussed the Regional
• Best
  • Food
  • well organized
  • Stuff worked
• Worst
  • Food (one person, their lunch was missing its sandwich)
  • errata with the problem set
  • difficulty of problems
• We looked at some of the problems
• Announced that problems from Regional could be turned in as homework

Return to Class Main Page

Class 11: 9-November-2011

• Had each person list something they learned from class this year
• Tried to explain difference between programming (act of implementing in code an existing design) and Analyst (act of starting from problem statement and proceeding through at least design)
• Referenced Slashdot articles:
  • How Do I Get Back a Passion For Programming?
  • Career Advice: Don't Call Yourself a Programmer
• Talked about Peter Principle (Wikipedia reference)
• Added regional problem set to the homework pool
• Covered problems:
  
• Mentioned that I would not be present for class next week but that it would a good time for folks to catch up on any missing homework. Andre has confirmed he will be there working on his. Obviously, it is an opportunity to work and get help without going to the extreme of duplicating code...
• I also kept forgetting to mention something that many might find useful (maybe would have been useful for the contest). With a little searching and testing, you can find numerous "cheat sheets" that are designed to be printed (double sided) and/or folded into pamplets for topics from vim commands to unix commands to language syntax. You can also do your own with code snippets (sort example, template, ...). I find having things like this (maybe even laminate them) can be used much faster than searching through a book (although you should put bookmarks or postit notes at often referenced sections of books..

  Look at the class references page for sample links to cheat sheets (if you find better send them to class).

Return to Class Main Page

Class 12: 16-November-2011

• No official class -- I will be in Seattle at Super Computing.`

Return to Class Main Page

Class 13: 30-November-2011

Return to Class Main Page