Summary
- Class 00 - 24-August-2021
- Class 01 - 31-August-2021
- Class 02 - 7-September-2021
- Class 03 - 14-September-2021
- Class 04 - 21-September-2021
- Class 05 - 28-September-2021
- Class 06 - 5-October-2021
- Class 07 - 12-October-2021
- Class 08 - 19-October-2021
- Class 09 - 26-October-2021
- Class 10 - 2-November-2021
- Class 11 - 9-November-2021
- Class 12 - 16-November-2021
- Class 13 - 23-November-2021
- Class 14 - 30-November-2021
Return to Class Main Page
Class 00: 24-August-2021
- Intro (to Isaac and class)
- Class policy
- Class outline/policy
- Intro/purpose (ICPC Facts)
- 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
- 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: 31-August-2021
- Class cancelled because of Hurrican Ida
Return to Class Main Page
Class 02: 7-September-2021
- 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: 14-September-2021
- 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: 21-September-2021
- 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: 28-September-2021
- 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 52-card 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: 5-October-2021
- Person of the day:
- Joe Armstrong
- Co-creator of the Erlang language
-
The problem with object-oriented 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 Coco-Cola Store Online Judge Cached
Return to Class Main Page
Class 07: 12-October-2021
- 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: 19-October-2021
- 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: 26-October-2021
- Person of the day:
- Edsger W. Dijkstra
- Famous for
- He coined the phrase structured programming
- goto considered harmful
- Algorithms
- Dijkstra's algorithm
- DJP algorithm
- Dijkstra-Scholten algorithm
- Dekker's algorithm (generalization)
- banker's algorithm
- smoothsort
- shunting-yard algorithm
- tri-color marking algorithm
- concurrent algorithms
- distributed algorithms
- deadlock prevention algorithms
- mutual exclusion algorithms
- self-stabilizing 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: 2-November-2021
- Person of the day: Brian Kernighan, Dennis Ritchie and Ken Thompson
- Brian Kernigham
- Dennis Ritchie
- Ken Thompson
- Creator/co-creator of Unix, B (predecessor of C), GO, Plan 9, QED, ed, utf-8,
- 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: 9-November-2021
- 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: 16-November-2021
- 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 constant-time algorithm does not depend on the input size. A typical constant-time 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(n2) 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(n3) 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(2n) 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: 23-November-2021
- 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
- Tim Berners-Lee
- 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: 30-November-2021
- Final Today
Return to Class Main Page