Summary

Class 00 - 15-January-2019
Class 01 - 22-January-2019
Class 02 - 29-January-2019
Class 03 - 5-February-2019
Class 04 - 12-February-2019
Class 05 - 19-February-2019
Class 06 - 26-February-2019
Mardi Gras - 5-March-2019
Class 07 - 12-March-2019
Class 08 - 19-March-2019
Class 09 - 26-March-2019
Class 10 - 2-April-2019
Class 11 - 9-April-2019
Break - 16-April-2019
Class 12 - 23-April-2019

Return to Class Main Page

Class 00: 15-January-2019

Annoucements
- North American Invitational
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
  - Review class summary (which you are doing now)
- Textbook name and links have been corrected in outline.
- We also talked about problem 108 - Maximum Sum. In a one dimenstional list, the optimal sum can be solved with Largest Sum Contiguous Subarray (GeeksforGeeks) in time O(n). Unftunately, problem 108 is for a 2-d array and Kadane's does not naturally extend that way. Brute force is way to slow (I tried years ago).
  The solution I used was to create every possible 1-d array that I could from the input, apply Kadane's algorithm and take best anser of that. Making each subcase is (1/2) * n * (n+1) cases for an O(n^2) giving the entire poblem an O(n^3) which for a 100 item list is well within time expectation. Here is an example of what I mean by every possible subcase: Suppose we had an array with 4 rows (A, B, C, D). THe possible subcases would be:
```
A
A+B
A+B+C
A+B+C+D
B
B+C
B+C+D
C
C+D
D
```
  Applying Kadane's algorithm to each of these 10 1-d arrays and taking best answer wins!
- We also very briefly talked aout big O notation and its value. More tocome on this topic...

Return to Class Main Page

Class 01: 22-January-2019

Annoucements
- ACM Meetings and Meetups
- North American Invitational
Problems:
Dynamic Programming
- Wikipedia Dynamic Programming
- To solve a problem with dynamix programming, 2 conditions must be met:
  1. You must discover a recursive solution
  2. You must find a way to store cache reults to avoid redundant computation
- Typically DP comes from a recursive solution (such as a depth first search) where the tree instead of spreading out indefinitely, it folds back on itself (some of the branches converge -- think chess for a minute: four different first two move sequences can produce the exact same resultant board)
- So after you develop the recursive solution, you then look how to save partial results to avoid recomputation
- Typically, DP problems process some sort of tree, graph or matrix recursively. Once a value for a portion of the path is calculated it is saved so future visits to that point can simply use the value instead of recomputing it.
- The term memoization comes up this. This is basically a magic word for caching the partial results
- The term sub-problem also shows up -- basically this is the idea that you can define a solution to a pice (sub) of the puzzle
- Another term that shows up is Optimal substructure. This means that the problem can be solved optimally by solving sub-problems optimally.
- Summary: Develop recursive solution, figure out how to save partial results to avoid re-computation (prune the work)

Return to Class Main Page

Class 02: 29-January-2019

Annoucements
- North American Invitational
- ACM Meeting
- LSU Solvers -- do I have your id number from UVA
- PackT
- O'Reilly Programming Books
- Building toolbox, using tools so they are praticed
- Proramming contst as a tool to win over a first line recruiter
- Music people do both practice and create -- skills needed by programmers
- Started live solve of 10487

Return to Class Main Page

Class 03: 5-February-2019

Announcements
- ACM Meetup tomorrow
- ACM Meeting Next Week
- NA Invitational
- Humble Bundles
Software | Firmware | Software are all code -- just different means to edit
Implementing code via IF, CASE, Array. A piece of code can be developed many different ways. Rgw choice you make impavts how executable code you need/runtime and data. Often one can be traded for the other. Becomes really important when cache sizes are taken into account.
Talked about proessors some, the fact that data/code mught reside in:
- Cloud
- disk
- memory
- cache (maybe multiple layers)
- processor/register(s)
Whenever code/data is not in the cpu, the farther away, the longer it takes to get to the cpu
Wikipedia has a decent overview of a processor and ideas like cache, piplelining, branch prediction, out of order executopn, ...
Talked a little about context switching (Wikipedia). When a process loses its turn and the cpu moves to the next process the cpu has to store all the current registers somewhere and tehn preload the registers for the incoming process. These steps (and a few other things) happen during a context switch. This takes a while (saving and restoring all the registers).
I also talked about arrays/ I covered a technic for reducing overhead when passing a 3x3 window over a 2d array. I also talked about a technid to reduce overhead for doing a spiral search in a 2D array.

Return to Class Main Page

Class 04: 12-February-2019

Announcements
- The North American Invitational Programming Contest 2019 is March 2.
- ACM Meeting Wednesday -- John Morello (LSU Alum) and Twistlock CEO talking
Talked about stratedgy for a programming contest
- Local cache of article by ex world finals competitor about team stratedgy
- Approach
- Talked about time slices and context switches
  - A context switch has overhead
    - computer: save all registers, program counter, load new registers and program counter, also now the cache that is full of stuff from other process is likely useless, so everythong becomes a memory reference
    - team: user must save code, request a print out, gather stuff, get up and then other user has get into their code, and settle in
  - Time slices
    - computer - a time slice is how long a process runs before the OS takes control back if the process does not do an I/O. Short time slices mean a lot of context switches (overhead). Long time slices make the machine feel sluggish. The length of the time slice probably dhould be different on a laptop vs a compute node in a cluster...
    - team: without a known time slice, attempts to change who is using the computer can result in personal conflicts, a set time slice can help a team better manage the computer resource and reduce tension, learning to better utilize the away from keyboard time is critical
- North American Championship -- our region currently is eligible for 4 teams to be invited. In other words the top 4 finishing schools would get an invite. Looking at 2018 results, the top 8 spots were occupied by 4 unique schools. In other words, the school in 9th would be the first loser. What do we have to do to be a top 4 school in the region?
- How are contests scored? (easier to win if you know the criteria for winning)
  - Essentially each team has a timer for each problem that starts when the contest starts and increments by 1 every time a minute passes. The counter for a problem stops when the team submits a solution that is judged correct. Any non-correct submission adds 15 minutes to the timer. Any problems never solved are ignored in scoring (wrong submissions for an unsolved problem do not change your score).
  - Results are sorted with 3 keys:
    1. number solved
    2. total penalty points
    3. times of solutions
  - The team that solves the most problems wins. In cases where multiple teams solve the same umber of problems, lower time/penalty points are better. In cases where number solved and penalty points are identical, the team that solved a problem first is chosen.
- What do we need to do to be a top 20 finisher? In looking at top 25 from last year, 17th through 23rd soved 5 each -- in other words you needed to solve at least 5 problems last year to be in top 25. 17th had 338 penalty points where 23rd had 801 penalty points. The difference was that 17th solved 3 in the first hour, another at time 81 and another at time 142 (essentially 2 hours in was it for them). 23rd solved 2 in the first hour, another just before 3rd hour ended, another just before 4th hour ended and their last with only 22 minites to go. While 17th is better than 23rd -- 23rd made effective use of the entire contest and continued to work with positive results for almost the entire 5 hours. 17th continued to work after the 2nd hour ended but had no additonal success.
- 5 hours is a very long time to work solid on contest problems. Unless you practice this quite a few times, you will not make good use of the second half of the time period.
- Took opportunity to quote: Two hours at the keyboard can save you twenty minutes of planning. We all have a tendency to think at the keyboard. Stopping a spending a few minutes in advance wher you plan can often dramatically shorten the time to solve a problem. At this point I referenced the Software Development Life Cycle and pointed out that a good understanding of the problem (requirements analysis) followed by a good plan for data structures and algorithms (design) dramatically reduce the time to code a solution/project (implementation). This becomes even more important in a contest where only one computer exists. Making sure you have a good requirements analysis and design completed before you take ove rth ekeyboard to do implementation is crucial to making best use of the single computer.
- Also shared my ideas on how to get better grades with less effort -- how to work smarter.
- Also shared that no win scenarios are best handled by altering the situation to provide a winnable scenario.