Summary
- Class 00 - 16-January-2018
- Class 01 - 23-January-2018
- Class 02 - 30-January-2018
- Class 03 - 6-February-2018
- Mardi Gras - 13-February-2018
- Class 04 - 20-February-2018
- Class 05 - 27-February-2018
- Class 06 - 6-March-2018
- Class 07 - 13-March-2018
- Class 08 - 20-March-2018
- Break - 27-March-2018
- Class 09 - 3-April-2018
- Class 10 - 10-April-2018
- Class 11 - 17-April-2018
- Class 12 - 24-April-2018
Return to Class Main Page
Class 00: 16-January-2018
- Class cancelled due to ice (university shut down at 3:00 PM)
Return to Class Main Page
Class 01: 23-January-2018
- Announcements
- Global Game Jam this weeked
- Class policy
- Grading policy
- Calendar
- web
- mailing list
- Homework
- go to UVA Online judge and sign up for an account
- Send an e-mail to class@isaac.lsu.edu with your name and your UVA ID
- Read student code of conduct, read Faculty handbook
Return to Class Main Page
Class 02: 30-January-2018
- Announcements
- ACM Meeting Wed (Jan 31) in PFT 1200 -- Chevron 6:30-8:30 PM
Return to Class Main Page
Class 03: 6-February-2018
- communication, first impressions, you filter what you hear based on who says it
- hardware/firmware/software are the same thing, just you edit them differently
- Mentioned Niklaus Wirth's book: Algorithms + Data Structures = Programs
- When designing a solution, you can choose to alter the code vs data balance
- 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 Statement
switch (i) { // switch Case 1: total = total + 17; break; Case 2: total = total + 29; break; Case 3: total = total + 99; break; } // switchArray Implementation
int ary[4] {0, 17, 29, 99}; total = total + ary[i];Example: You wish to sum up the 8 outer boxes of a 3x3 array for boxes where the value is greater than 0
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) && (0<>j)) { // sum up value total = total + ary[i][j]; } // sum up value } // for j } //for iArray Method
/* i and j are dx and dy -- how much you add to x and y to get the desired place (offset) */ 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
Return to Class Main Page
Mardi Gras: 13-February-2018
Return to Class Main Page
Class 04: 20-February-2018
- ACM Meeting tomorrow
- North American Invitational Programming Contest willbe March 24 (first Saturday of spring break)
- Reviewed talk of last class (code vs data)
- 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,-4As 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: 27-February-2018
- Announcements
- ACM Community Meetup tomorrow
- North American Invitational Programming Contest willbe March 24 (first Saturday of spring break)
- Possible problems: 572 -- 532
- Possible problems: 260, 352, 459, 469, 657, 776, 782, 784, 785, 852, 871, 1197, 10336, 10926, 10946, 11094, 11110, 11244, 11470, 11518, 11561, 11749, 11953
- Possible problems: 308, 705, 11101, 11200, 11585
- Halem book (version 2) Flood Fill/Finding Connected Components
- Another halem collectionof problems
- UVA toolkit problem list with category
Return to Class Main Page
Class 06: 6-March-2018
- Upcoming NA Invitational
- Redstick
- So what to do if you do not know how to solve a problem or your solution does not work?
- Put it down and then come back to it later
- Ask someone to listen for you to step through the code
- Manually step through the data and see that you get right answer
- Step through your code and make sure it gets same results you do manually
- Will a debugger catch an invalid memory reference?
- Run it on another machine
- Look at the tools below
- Tools
- uhunt
- udebug
- Forums
Return to Class Main Page
Class 07: 13-March-2018
- Announcements
- Maker faire
- North American Invitational
- ACMeetup ? meeting
- humble bundles
- Problems: 532, 784, 352. We looked at these problems and my solutions for them. Each problem was solved with a different variant of a flood fill (I know this goes against my consistency principle -- but showing the different methods is part of a learning exercise).
- 532 - wrote both breadth (a.c) and depth (slow.c) versions of this. Depth first took 7 seconds to solve a 30 x 30 x 30 maze with no walls and start/end at opposite corners. Breadth took 0.007 seconds. Depth first was written first. Much of the same code reused for breadth (which added alternating stacks) -- probably should have been done with one buffer and astack building from each end).
- 784 - this one did flood fill by repeated scans of maze until no new spaces could be filled (marked)
- 352 - this one makes a single pass through the maze, whenever it encounters a mark (war eagle artifact) it increments count and then recursively eliminates that eagle (its connected marks) and then resumes the scan. This code uses recursion and eliminates p=subtrees (that don;t have to be re-evaluated and hence it is a Dynamic Programming implementation (By eliminating the entire eagle the first time it is encountered, it is unecessary to investigate that eagle from any of its other points.
- Showed using defined constants (like WALL '#"( instead of scattering the literal throughout the code. This way, if you need to change the characer, one edit at the top does it. It can also lead to easier to read code.
- Defensive programming - the idea that you design and code to avoid problems (like in defensive driving - you make decisions that are less likely to result in wrecks).
- showed the idea of surrounding a matrix/maze with a border of guard values. This has 2 benefits:
- If you every process a guard value, you know you have blown a sibscript (cheap bounds checking)
- It allows filters to look beyond the edge so that you do not have to worry about if your subscripts are valid (if you are on the rightmost point and you algorithm says check one to the right, you would normally go beyond the bounds of the data structure, by putting a guard border, you can look their and just never find anything interesting (trading some space/memory [the guard border] for some code [the ifs to make sure that the subscripts are valid)
Return to Class Main Page
Class 08: 20-March-2018
- Announcements
- North American Invitational
- Maker Faire
- Covered more problems
- Discussed ideas on solving tree problem
- dicussed use of multiple algorithms to solve separate parts of a problem
Return to Class Main Page
Break: 27-March-2018
Return to Class Main Page
Class 09: 3-April-2018
Return to Class Main Page
Class 10: 10-April-2018
- Talked about evolution from tools user to tool maler. Learning to use tools is a
big deal and we should be proud of our ability to do so. Learning to develop new tools that
enhance and/or augment existing tools is an even greater goal to aspire to.
The ability to develop better tools that produce desired results with less impediment (frustration) allows for the production of better quality products.
Learning to use the tools in your toolbox is an essential part of advancing your career. Continuing to add tools is a necessary aspect of the field of computing. Augmenting these tools and bending them to your needs (rather bending your needs to the tool) is how you truely advance.
In other words, a tool user can become proficient at using tools to the point that they are capable of using those tools freely to solve problems. With practice, they even begin to extend the use realm of the tools. (if the only tool you have is a hammer -- then everything is a nail)
Becoming a tool user allows you to use that hammer to drive nails. Become a tool maker allows you to take that hammer and create a pry bar. Maybe even a screwdriver. Now you can solve lots of additional problems.
- Much of the advancement in computing iwes itself to the needs of the early space program. Imagine where computing might go with a renewed space program to push its limits.
- Having a job feeds the belly (a necessity). Having a career feeds the belly and the mind. Way better.
- Here are a sequence of short articles about Tim cook. Take a few minites and read them. After reading these it becomes easier to believe that society has a positive future.
- https://www.cnbc.com/2018/04/09/how-steve-jobs-convinced-tim-cook-to-join-apple.html
- https://www.cnbc.com/2018/04/06/the-lesson-steve-jobs-taught-apple-ceo-tim-cook.html
- https://www.cnbc.com/2018/01/18/apple-ceo-tim-cook-on-his-secret-to-success.html
- https://www.cnbc.com/2016/10/07/the-one-great-reason-apple-ceo-tim-cook-doesnt-care-about-being-first.html
- https://www.cnbc.com/2017/02/09/apple-ceo-tim-cook-tells-young-people-to-tune-out-cynics.html
- https://www.cnbc.com/2017/02/09/apple-ceo-tim-cook-dont-work-for-money-you-will-never-be-happy.html
- https://www.cnbc.com/2018/04/10/apple-ceo-tim-cook-on-the-importance-of-consumer-privacy.html?recirc=taboolainternal
- Elon Musk is another leader (Tesla, Space X, solar power, batteries, The Boring Company, and more). He is trying to do multiple incredible things concurrently (and not failing yet). His battery system for Australia defied the odds. Tesla has singlehanded convinced the world that electric cars are viable and can be fun to drive...
Return to Class Main Page
Class 11: 17-April-2018
- Guest instructor: Matthew Gavin
Return to Class Main Page
Class 12: 24-April-2018
- Final
Return to Class Main Page