- Class 00 - 18-January-2022
- North American Qualifier - 22-January-2022
- Class 01 - 25-January-2022
- Class 02 - 1-February-2022
- Class 03 - 8-February-2022
- Class 04 - 15-February-2022
- Class 05 - 22-February-2022
- Mardi Gras - 1-March-2022
- ACM South Central Regional Programming Contest - 5-March-2022
- Class 06 - 8-March-2022
- Spring Break - 15-March-2022
- Class 07 - 22-March-2022
- Class 08 - 29-March-2022
- Class 09 - 5-April-2022
- Class 10 - 12-April-2022
- Class 11 - 19-April-2022
- Class 12 - 26-April-2022
- Class 13 - 3-May-2022 (Final)
Return to Class Main Page
Class 00: 18-January-2022
- Intro (to Isaac and class)
- Class policy
- Class outline/policy
- Intro/purpose (ICPC Facts (pdf))
- Grading policy
- Calendar
- web
- mailing list (icpc-practice)
- Office hours
- 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 (numeric number, not username)
- Read student code of conduct, read Faculty handbook (pdf)
- Review class summary (which you are doing now)
- Class outline/policy
- Typical Class
- Annoucements
- Humble Bundle
- PackT Pub books
- Person of the day -- importance of history, context
- Lecture/discussion
- Problem Analysis
- Annoucements
- Game - most things can be considered a game (if not all). Games tend to have the following attributes:
- Goal
- Rules
- Skill enhanced with practice
- Knowing the rules often enhances chances of succeeding in a game (for example: Reading the student handbook is a good way to improve your chances at succeeding at being a student).
- Quote: 20 hours at the keyboard can save you 2 hours of planning
- Upcoming ICPC North America Qualifier -- Let me know if you are interested in competing (individually or as a group), You will need to be registered with ICPC, then send me an e-mail with the name(s)/e-mail address(es) for you (or you team) and a team name.
- Updates to web pages:
- Added box at bottom of appropriate pages to explain meaning of green, yellow, and red check marks
- Added sort options to local mirror of problems
- fixed link to uHunt on lsu-solvers page
- Added padding to quotes on main class page
- Added sortable column to local mirrorpages to show run time of 20th fastest solution
- I sent a request to have class moved to another room with more seats -- check page for possibility of new location
- UVA Yearly submisson statistics
Return to Class Main Page
North American Qualifier: 22-January-2022
Return to Class Main Page
Class 01: 25-January-2022
Annoucements
Person of the day
- Tim Berners-Lee
- Network design, World Wide Web, HTTP
- wikipedia
- wikiquote
- Cool URIs don't change
- Awards:
- Knighted by Queen Elizabeth
- Turing Award
- LSU at NAQ
- NAQ Problems - F, H, (A, c?, G, E, H)
- Talk about Kattis Scoreboard
- Explained virtue of UVA and contest problems/particpation in relation to getting/suceeding in job interviews
- ICPC History
- Online Judge, uHunt and uDebug
- Update on latest UVA mirror changes/capabilities
Return to Class Main Page
Class 02: 1-February-2022
Annoucements
Person of the day
- Andrew S. Tanenbaum
- Operating Systems, Minix, Linux, microkernels
-
A refund for defective software might be nice, except it would bankrupt the entire software industry in the first year. - Notion of "intelligent design", as applied to software
- Isolate components from each other so that they cannot interfere with each other - or even communicate unless there is a reason to do so
- Stick to the "principle of least authority"; no component should have more privilege than it needs to get the job done
- The failure of one component should not cause others to fail
- The health of components should be monitored; if one stops operating properly, the system should know about it
- One must be prepared to replace components in a running system
- wikipedia
- wikiquote
Class Discussion
- Update on latest UVA mirror changes/capabilities (themes, ascii charts, c-limits, toolbox redo
- Looking at Official textbook
- Sum Formulas (page 10)
- sum of 1 to n: (n)(n+1) / 2
- sum of 12 to n2: (n)(n+1)(2n+1) / 6
- arithmetic progression - sum of a sequence of numbers that each increase uniformly and n is the sequence length (3 + 6 + 9 + 12 + 15): n*(first+last) / 2
3 + 6 + 9 + 12 + 15 = 45 5 * (3 + 15) / 2 = 45
- Geometric progression (each turn is n times the previous term): ((last * n) - first) / (n - 1)
3, 6, 12, 24, 48 first=3, last=48, n=2 ((48 * 2) - 3) / (2 - 1) = (96 - 3) / 1 = 93 1, 3, 9, 27, 81 first=1. last=81, n=3 ((81 * 3) - 1) / (3 - 1) = (243 - 1) / 2 = 242 / 2 = 121
- Set Theory
- Logic (boolean)
- Functions
- Logarithms: logk(x) = a ⇒ ka = x
logk(ab) = logk(a) + logk(b) logk(xn) = n * logk(x) logk(a/b) = logk(a) − logk(b) logu(x) = logk(x) / logk(u)
- Big O (pages 17-20)
- Complexity Classes (page 20)
- Estimating Efficiency (page 21)
input size required time complexity n≤10 O(n!) n≤20 O(2n) n≤500 O(n3) n≤5000 O(n2) n≤106 O(n log n) or O(n) n is large O(1) or O(log n)
- Maximum subarray sum
Return to Class Main Page
Class 03: 8-February-2022
Annoucements
Person of the day
- Robert Metcalfe
- Designer of ethernet
- Founded 3com
- wikipedia
- Metcalfe's law - the value of a telecommunications network is proportional to the square of the number of connected users of the system (n2)
- The History of Ethernet
- Living legends: Ethernet inventor Bob Metcalfe
- The birth and rise of Ethernet: A history
- Awards:
Class Discusssion
Return to Class Main Page
Class 04: 15-February-2022
Annoucements
Person of the day
Class Discusssion
- SCUSA Regional
- To participate in the Regional:
- Problem Categories
- Problems discussed:
- (!) 288 - Arithmetic Operations With Large Integers Online Judge Cached
- (!) 133 - The Dole Queue Online Judge Cached
- (*) 136 - Ugly Numbers Online Judge Cached
Return to Class Main Page
Class 05: 22-February-2022
Annoucements
Person of the day
Class Discusssion
Return to Class Main Page
Mardi Gras: 1-March-2022
Return to Class Main Page
ACM South Central Regional Programming Contest: 5-March-2022
Return to Class Main Page
Class 06: 8-March-2022
- Class cancelled - University closed for storm weather.
Return to Class Main Page
Spring Break: 15-March-2022
Return to Class Main Page
Class 07: 22-March-2022
- Class cancelled due to ba weather
Return to Class Main Page
Class 08: 29-March-2022
- Byte Magazine - I suggest lookiing at one a year to see evolution
- Binary number storage
Return to Class Main Page
Class 09: 5-April-2022
Annoucements
Person of the day
- Kenneth Iverson
- wikipedia
- wikiquote
- IBM Selectric (golf ball) typewriter was side project
- Awards:
- IBM Fellow, IBM
- Harry H. Goode Memorial Award, IEEE Computer Society
- Member, National Academy of Engineering (USA)
- Turing Award, Association for Computing Machinery
- Computer Pioneer Award (Charter recipient), IEEE Computer Society
Class Discusssion
- Brief demo of some APL (Dyalog - free for personal use), Dyalog APL Primer (PDF)
- Continuum - Compared multiple ways to implement solution for same problems
- Arrays - Some aarray tricks
Return to Class Main Page
Class 10: 12-April-2022
Annoucements
Person of the day
Class Discusssion
- Music
- Flood Fill
- (*) 352 - The Seasonal War Online Judge Cached
- (*) 469 - Wetlands of Florida Online Judge Cached
Return to Class Main Page
Class 11: 19-April-2022
Annoucements
Person of the day
- Richard Stallman
- Fundamental idea: Free as in beer
In a nutshell, the word "free" has a couple of meanings and it's not always possible to tell in context which one the user meant. "Free as in beer" refers to the cost (i.e. money) of the software, while "free as in speech" refers to what you are allowed to do with the software.
- His personal Page
- Wikipedia
- WikiQuote
- GNU Project
- Free Software Foundation
- Fundamental idea: Free as in beer
Class Discusssion
Return to Class Main Page
Class 12: 26-April-2022
Annoucements
Person of the day
- Vint Cerf
- Network design, TCP/IP
- wikipedia
- wikiquote
- Awards:
- Fellow of the ACM
- Turing Award
Class Discusssion
Return to Class Main Page
Class 13: 3-May-2022 (Final)
- Final!
Return to Class Main Page