Summary
 Class 00  24August2021
 Class 01  31August2021
 Class 02  7September2021
 Class 03  14September2021
 Class 04  21September2021
 Class 05  28September2021
 Class 06  5October2021
 Class 07  12October2021
 Class 08  19October2021
 Class 09  26October2021
 Class 10  2November2021
 Class 11  9November2021
 Class 12  16November2021
 Class 13  23November2021
 Class 14  30November2021
Return to Class Main Page
Class 00: 24August2021
 Intro (to Isaac and class)
 Class policy
 Class outline/policy
 Intro/purpose (ICPC Facts)
 Grading policy
 Calendar
 web
 mailing list (icpcpractice)
 Office hours
 Homework
 go to UVA Online judge and sign up for an account
 Send an email to class@isaac.lsu.edu with your name and your UVA ID (numeric number, not username)
 Read student code of conduct, read Faculty handbook
 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 enhinces 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
Return to Class Main Page
Class 01: 31August2021
 Class cancelled because of Hurrican Ida
Return to Class Main Page
Class 02: 7September2021
 Annoucements
 Humble Bundle
 PackT Pub books
 Person of the day  Niklaus Wirth
 Niklaus Wirth
 Competitive Programming 1 by Steven Halim, Felix Halim (local)
 Explained virtue of UVA and contest problems/particpation in relation to getting/suceeding in job interviews
 ICPC History
 Online Judge, uHunt and uDebug
 function, domain, range

In math relations are relations such as f(x) = y. In a relation, a single x can map to multiple Y values (such as in a circle). Functions are a spcial type of relation where every X value maps exactly to 1 y value. The possible values for X are called the domain. The possible values for y are called the range. So a function maps the domain to the range. In software, a program can be thought of as a function. The input is the domain and the output is the range. When trying to prove the correctness of a solution (program), it is often necessary to test the program on various domain values to ensure the correct range values are being computed. Knowing which domain values to test is very important. We typically refer to the importnat values as boundary conditions. Discovering the domain boundary conditons makes it much faster to determine if your code is correct.
Return to Class Main Page
Class 03: 14September2021
 Person of the day: Richard Stallman
 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
 Richard Stallman
 LSU Solvers
 PackT
 Humble Bundle Books
 Basically redid last week with a working online judge. Also a revamped isaac uva site with alot more information clond from onlinejudge.
Return to Class Main Page
Class 04: 21September2021
 Person of the day: Alan Kay
 Alan Kay
 LSU Solvers
 USACO
 PackT
 Humble Bundle Books
 Learn Web Development
 Binary Numbers
 (*) 594  One Little, Two Little, Three Little Endians Online Judge Cached
 (*) 575  Skew Binary Online Judge Cached
 (!) 10669  Three powers Online Judge Cached
 (!) 10851  2D Hieroglyphs decoder Online Judge Cached
 (!) 11532  Simple Adjacency Maximization Online Judge Cached
 (!) 11744  Parallel Carry Adder Online Judge Cached
Return to Class Main Page
Class 05: 28September2021
 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
 Andrew S. Tanenbaum
 (!) 143  Orchard Trees Online Judge Cached
 (!) 117  The Postal Worker Rings Once Online Judge Cached
 Probability
Shuffle a standard deck of 52 playing cards (no jokers). Draw two cards from the deck at at time. Two cards are said to be a `pair` if the the two cards have the same numerical value. If the two cards are not a pair, discard them. How many pairs should you expect to see from the 52card deck?
 Sequence
What are the next numbers in the following sequence? 3, 4, 6, 8, 12, 14, 18, 20, 24, 30, ??
Return to Class Main Page
Class 06: 5October2021
 Person of the day:
 Joe Armstrong
 Cocreator of the Erlang language

The problem with objectoriented languages is they've got all this implicit environment that they carry around with them. You wanted a banana but what you got was a gorilla holding the banana and the entire jungle.
 wikipedia
 wikiquote
 Joe Armstrong  Keynote: The Forgotten Ideas in Computer Science  Code BEAM SF 2018
 "The Mess We're In" by Joe Armstrong
 Joe Armstrong
 (*) 11877  The CocoCola Store Online Judge Cached
Return to Class Main Page
Class 07: 12October2021
 Humble bundle, packt
 44th ICPC World Finals
 Person of the day:
 Sonic Pi
 Should have brought up Music stuff
 Talked about geometry some
 Talked about vectors and clockwise vs counterclockwise (more detail coming soon  I hope)
 Revisted (!) 143  Orchard Trees Online Judge Cached in light of above
 Talked about finding vertices of convex hull
 revisted (!) 117  The Postal Worker Rings Once Online Judge Cached with some ideas on simplification
Return to Class Main Page
Class 08: 19October2021
 Person of the day:
 Donald Knuth
 Stanford web page (where he is Professor Emeritus)
 Wikipedia
 Art of Computer Programming
 WikiQuotes
 More quotes
 xkcd
 ACM Turing Award
 Brief biography
 Books
 Amazon  Knuth books
 Kindle Store
 Articles about "The Art of Computer Programming"
 Overleaf (One of many online TeX services for collaboration)
 Donald Knuth
 Frustration
 Number Theory
 Continuum
 Array
 Problem Categories
Return to Class Main Page
Class 09: 26October2021
 Person of the day:
 Edsger W. Dijkstra
 Famous for
 He coined the phrase structured programming
 goto considered harmful
 Algorithms
 Dijkstra's algorithm
 DJP algorithm
 DijkstraScholten algorithm
 Dekker's algorithm (generalization)
 banker's algorithm
 smoothsort
 shuntingyard algorithm
 tricolor marking algorithm
 concurrent algorithms
 distributed algorithms
 deadlock prevention algorithms
 mutual exclusion algorithms
 selfstabilizing algorithms
 wikipedia
 wikiquote
 Awards:
 Member of the Royal Netherlands Academy of Arts and Sciences
 Distinguished Fellow of the British Computer Society
 The Association for Computing Machinery's A.M. Turing Award
 Harry H. Goode Memorial Award from the IEEE Computer Society
 Foreign Honorary Member of the American Academy of Arts and Sciences
 Doctor of Science Honoris Causa from the Queen's University Belfast
 Computer Pioneer Charter Recipient from the IEEE Computer Society
 ACM/SIGCSE Award for Outstanding Contributions to Computer Science Education
 Fellow of the Association for Computing Machinery
 local copy of "goto considered harmful".
 Famous for
 Edsger W. Dijkstra
 Problem Categories has been updated
 Local mirror of UVA Has been updated
 Flood Fill
Return to Class Main Page
Class 10: 2November2021
 Person of the day: Brian Kernighan, Dennis Ritchie and Ken Thompson
 Brian Kernigham
 Dennis Ritchie
 Ken Thompson
 Creator/cocreator of Unix, B (predecessor of C), GO, Plan 9, QED, ed, utf8,
 grep
 Lot of work on regular expressions
 Wikipedia
 Awards include: Turing Award, IEEE Richard W. Hamming Medal, Fellow of the Computer History Museum, National Medal of Technology, Tsutomu Kanai Award, Japan Prize
 Chess
 Creation of endgame tablebase
 Creator of Belle
 Wrote "chess" for Unix (early chess program)
 Wikiquote
 Reading Code
 Programming Style
 Solving Programming Problems
Return to Class Main Page
Class 11: 9November2021
 Person of the day:
 Ted Talks are a great way to expand your Horizons. Take a look at this list of Ted Talks.
 Problems:
 (*) 394  Mapmaker Online Judge Cached
 (*) 739  Soundex Indexing Online Judge Cached
 (*) 10305  Ordering Tasks Online Judge Cached
 (*) 439  Knight Moves Online Judge Cached
 (*) 11942  Lumberjack Sequencing Online Judge Cached
 (*) 122  Trees on the level Online Judge Cached
 (*) 12592  Slogan Learning of Princess Online Judge Cached
 (*) 12541  Birthdates Online Judge Cached
 (*) 12195  Jingle Composing Online Judge Cached
 (*) 11597  Spanning Subtree Online Judge Cached
 Talked about next 4
 (*) 10790  How Many Points of Intersection? Online Judge Cached
 (*) 278  Chess Online Judge Cached
 (*) 10784  Diagonal Online Judge Cached
 (*) 10302  Summation of Polynomials Online Judge Cached
Return to Class Main Page
Class 12: 16November2021
 Person of the day:
 Conway's Game of Life
 Class Text: Competitive Programmer's Handbook  Chapter 2: Time Complexity
 The following list contains common time complexities of algorithms:
 O(1) The running time of a constanttime algorithm does not depend on the input size. A typical constanttime algorithm is a direct formula that calculates the answer.
 O(log n) A logarithmic algorithm often halves the input size at each step. The running time of such an algorithm is logarithmic, because log2 n equals the number of times n must be divided by 2 to get 1.
 O(√n) A square root algorithm is slower than O(logn) but faster than O(n). A special property of square roots is that n = n/ n, so the square root n lies, in some sense, in the middle of the input.
 O(n) Alinearalgorithmgoesthroughtheinputaconstantnumberoftimes.This is often the best possible time complexity, because it is usually necessary to access each input element at least once before reporting the answer.
 O(n log n) Thistimecomplexityoftenindicatesthatthealgorithmsortstheinput, because the time complexity of efficient sorting algorithms is O(nlogn). Another possibility is that the algorithm uses a data structure where each operation takes O(log n) time.
 O(n^{2}) A quadratic algorithm often contains two nested loops. It is possible to go through all pairs of the input elements in O(n2) time.
 O(n^{3}) A cubic algorithm often contains three nested loops. It is possible to go through all triplets of the input elements in O(n3) time.
 O(2^{n}) This time complexity often indicates that the algorithm iterates through all subsets of the input elements. For example, the subsets of {1,2,3} are , {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}.
 O(n!) This time complexity often indicates that the algorithm iterates through all permutations of the input elements. For example, the permutations of {1,2,3} are (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) and (3,2,1).
 The following list contains common time complexities of algorithms:
 Problems:
 (*) 394  Mapmaker Online Judge Cached
 (*) 739  Soundex Indexing Online Judge Cached
 (*) 10305  Ordering Tasks Online Judge Cached
 (*) 439  Knight Moves Online Judge Cached
 (*) 11942  Lumberjack Sequencing Online Judge Cached
 (*) 122  Trees on the level Online Judge Cached
 (*) 12592  Slogan Learning of Princess Online Judge Cached
 (*) 12541  Birthdates Online Judge Cached
 (*) 12195  Jingle Composing Online Judge Cached
 (*) 11597  Spanning Subtree Online Judge Cached
 Problems covered:
 (*) 170  Clock Patience Online Judge Cached
 (*) 11743  Credit Check Online Judge Cached
 (*) 374  Big Mod Online Judge Cached
Return to Class Main Page
Class 13: 23November2021
 Person of the day:
 Tim BernersLee
 Network design, World Wide Web, HTTP
 wikipedia
 wikiquote
 Cool URIs don't change
 Awards:
 Knighted by Queen Elizabeth
 Turing Award
 Tim BernersLee
 The surprising habits of original thinkers
 Are you a giver or a taker?
 Problems:
 (*) 394  Mapmaker Online Judge Cached
 (*) 739  Soundex Indexing Online Judge Cached
 (*) 10305  Ordering Tasks Online Judge Cached
 (*) 439  Knight Moves Online Judge Cached
 (*) 11942  Lumberjack Sequencing Online Judge Cached
 (*) 122  Trees on the level Online Judge Cached
 (*) 12592  Slogan Learning of Princess Online Judge Cached
 (*) 12541  Birthdates Online Judge Cached
 (*) 12195  Jingle Composing Online Judge Cached
 (*) 11597  Spanning Subtree Online Judge Cached
 (*) 913  Joana and the Odd Numbers Online Judge Cached
 (*) 12554  A Special "Happy Birthday" Song!!! Online Judge Cached
 (*) 674  Coin Change Online Judge Cached
 (*) 119  Greedy Gift Givers Online Judge Cached
 (*) 10533  Digit Primes Online Judge Cached
 (*) 11292  Dragon of Loowater Online Judge Cached
 (*) 10334  Ray Through Glasses Online Judge Cached
 Problems covered:
Return to Class Main Page
Class 14: 30November2021
 Final Today
Return to Class Main Page