Home
Outline/Policy
Summary
Homework
View
Upload
Approach
References
Problems:
Archive
Categories
Extra:
Grades
Class:
CSC 2700 Section 02
Coates 103
Wednesday
6:10 PM - 8:10 PM
|
|
Summary
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:
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:
- 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
- Read Problem Statements
- Evaluate problem Statements
- Look for "issues"
- Discuss Implementation Ideas, Algorithms, Data Structures
- Designs
- 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
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
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
|
![[ Powered by Red Hat Linux ]](/icons/rh_pb.png){kind=icon}
![[ Powered by Apache ]](/icons/apache_pb.gif){kind=icon}
![[ Powered by PHP ]](/icons/php_pb.gif){kind=icon}