CS494/594 -- Presentation Order
James S. Plank
Fall, 2021
Below are the requirements for your presentations, plus suggestions.
After that, I have the order of presentations, and your assignments.
You may give one of two types of presentations:
- A topcoder problem that I assign you. D1-250/D2-500 for 494, D1-500/D2-1000 for 594.
- An algorithm that we don't cover in class (or in previous classes).
Requirements
- You must send me your slides for review at least 24 hours before class. If
I suggest changes, you must make those changes or you will be deducted.
If you don't send me your slides, you will lose 5 of the 20 points.
- If you are enrolled in COSC 494, then your presentation shoue be
between 5 and 10 minutes long. If you are enrolled in COSC 504, then your presentation should
be between 7 and 15 minutes. You will be deducted if you go drastically over or under.
- Assume that your audience has taken CS302. You don't need to explain Depth-First Search,
Dijkstra's algorithm or Dynamic Programming.
- You need a title slide with your name, affiliation, name of your talk, date. This slide should also be the last slide of your presentation.
For Topcoder Presentations:
- You need to state the problem, using examples and pictures,
so that your audience has an
intuitive understanding of the problem.
- You need a slide with prototypes and variables (like mine).
- You need a slide with the constraints. This can be merged with the previous slide if everything fits cleanly. Otherwise, separate them.
- You need to present a solution. Try to make the solution intuitive, so that your audience understands it. Walk through examples. Sometimes it is helpful to present a solution that doesn't
work, but helps you to present the solution that does work.
- Sometimes, it's nice to present multiple solutions (like I did with the Christmas Tree
problem).
- I will send you an email that has hints, and often an algorithm or solution. If my email has
a solution or algorithm, you must present my solution as one of the solutions.
It doesn't have to be the "main" one, but you have to present it.
- You need to present the running time, where you describe the big-O
performance of your solution(s).
- You need a performance slide where you detail performance on a machine, and show how the performance scales with input. If you have multiple implementations, compare them. You should specify the machine and its speed. This slide must have a graph, and the graph should be very clear. You
don't want to end up on the wall of shame.
- (Optional, but always interesting): Can you solve this in other, perhaps faster ways? Or can it be solved by other algorithms that we know about?
- How did the topcoders do? If fewer than 60% of them got it, it was a hard problem.
For Algorithm Presentations:
- I have to approve the algorithm. If you want me to give you some suggestions, I can
do so.
- You need to present the problem that the algorithm is solving. It helps if you can
give concrete, real-world examples of where the algorithm is useful.
- You need to present the algorithm clearly, working through at least one, and maybe two
or three motivating examples. With pictures!
- You need to present the running time in big-O, and if that needs to be explained more
clearly (e.g. it's hard to know what the big-O is really measuring), then do so.
- You need to program the algorithm and do a performance evaluation. In other words,
you need a nice performance graph like in the Topcoder example above.
- Suggestions for algorithms (if there's no link, just use wikipedia):
Bayesian Optimization, Skip Lists and/or Splay Trees,
Reinforcement Learning (this would have to be at a high level),
Algorithm Games,
Line Sweep Algorithms,
Red-Black Trees,
Binary Indexed Trees,
Range Minimum Query and Lowest Common Ancestor,
Biconnected Components,
Tries,
Assignment Problem, Hungarian Algorithm,
Prime numbers, factorization, etc
Line intersection and its applications.
Zero Knowledge Proofs.
Suggestions
You can look up solutions to your algorithm/topcoder problems online. This is more about
the presentation than the fact that you solved the problem.
You cannot lift graphics, either from my hints or from any other source. Do your
own graphics and customize them for your talk.
If you want to talk things over, go to office hours or schedule a time to talk with the TA or with me.
Repeat after me: "Pictures are better than text."
"Pictures are better than text."
"Pictures are better than text."
Presentation Order
9/21 isikkema -- Sikkema, Isaac Line Intersection & Apps
9/23 akrneta -- Krneta, Alexander His solution to Board Folding
9/23 jgreatho -- Greathouse, John ./Writeups/Probability/RandomPancakeStack.html
9/28 jcarmac3 -- Carmack, John LZ77 Compression
9/28 zcreech -- Creech, Zachery http://web.eecs.utk.edu/~jplank/topcoder-writeups/2018/StonesOnATree/index.html
10/5 czheng4 -- Zheng, Chaohui Aho Corasick Algorithm
10/5 sbauman2 -- Baumann, Samuel ./Writeups/Bit_Arithmetic/OrderOfOperations.html
10/7 ncreech1 -- Creech, Nicholas ./Writeups/Dynamic/SubdividedSlimes.html
10/7 cadkin17 -- Adkins, Cameron http://web.eecs.utk.edu/~jplank/topcoder-writeups/2018/Subgraphs/index.html
10/12 erush3 -- Rush, Everett http://web.eecs.utk.edu/~jplank/topcoder-writeups/2018/FrogSquare/index.html
10/12 chathawa -- Hathaway, Clark FFT Anything
10/14 hkitts2 -- Kitts, Hunter FISR (Fast Invers Square Root)
10/14 wrhodes2 -- Rhodes, William ./Writeups/Dynamic/BuildingHeights.html
10/21 nparsly -- Parsly, Nicholas http://web.eecs.utk.edu/~jplank/topcoder-writeups/2015/MaliciousPath/index.html
10/26 bhorsbur -- Horsburgh, Brian ./Writeups/Dijkstra/BuildingRoutes.html
10/26 rpatel64 -- Patel, Ravi Range Minimum Query + Lowest Common Ancestor
10/28 cchen67 -- Chen, Cheng http://web.eecs.utk.edu/~jplank/topcoder-writeups/2013/FoxAndGo2/index.html
10/28 spatel91 -- Patel, Shreyank http://web.eecs.utk.edu/~jplank/topcoder-writeups/2007/FloorBoards/index.html
11/2 jclar168 -- Clark, Joseph Algorithm X
11/2 mhasan22 -- Hasan, Mdariful Crystal stuff, beginning of November
11/4 lharri73 -- Harris, Landon Hungarian Algorithm
11/9 tcultice -- Cultice, Tyler AONT-RS
11/9 hfarahat -- Farahat, Hadeer Parallel Prime Factorization
11/9 jmandzak -- Mandzak, Joshua http://web.eecs.utk.edu/~jplank/topcoder-writeups/2017/DFSCount/index.html
11/11 rdylewsk -- Dylewski, Racheal http://web.eecs.utk.edu/~jplank/topcoder-writeups/2014/TreesAnalysis/index.html
11/16 jananth2 -- Anantharaj, Joshua Bayesian Optimization
11/16 rstewa35 -- Stewart, Ryan AES
11/16 ndrake1 -- Drake, Nickolas K means clustering
11/18 rrusitan -- Rusitanmu, Rus http://web.eecs.utk.edu/~jplank/topcoder-writeups/2018/FindThePerfectTriangle/index.html
11/18 zliu68 -- Liu, Ziming Reinforcement Learning
11/23 ajone239 -- Jones, Austin http://web.eecs.utk.edu/~jplank/topcoder-writeups/2018/DigitStringDiv1/index.html
11/30 nwest13 -- West, Nicholas Shank's babystep-giantstep algorithm
11/30 robdgrif -- Griffith, Robert Splay Trees
12/03 wcoar -- Coar, Lillian Perlin Noise
12/03 cparmale -- Parmalee, Corinne ./Writeups/Set/GreaterGame.html
12/03 khuckaba -- Huckabay, Katherine Pancake sorting
12/03 arutter1 -- Rutter, Aiden http://web.eecs.utk.edu/~jplank/topcoder-writeups/2017/PolygonRotation/index.html
12/03 dlowe13 -- Lowe, Douglas K Nearest Neighbor