|Final Friday, June 7, 2019||10:00PM-1:00PM|
Feel free to use any code from the [Princeton Algorithms Code PortFolio]
Write Up 0 [Thur 16]
[PDF] [Write Up 0]LRU Constant Time [Thur 16]
|2||Sorting and Comparators
|[PDF]||Friend Circles [Thur 16]||[Video]|
|3||Merge Sort/Heap Sort||[PDF]||Apple Sort [Thur 16]||[Video]|
|4||Quick Sort & Quick Select||[PDF]||Nth place loser [Thur 23]||[Video]|
|5||Balance Search Trees
2-3/Red Black Trees,& B-Trees
|6||Geometric Search||[PDF]||Bird Scooters [Thu 23]||[Video]|
|7||Solving Recurrence Relations||[PDF]||[Video]|
|8||Master Theorem & Karatsuba & Substitution||[PDF1][PDF2]
|Notes from Scribe
[Recitation Work Sheet]
1 Write up [Thur 23]
[PDF] [Latex File 1]
|9||Strongly Connected Components||[PDF]||DDR Robot [Thur 30]|
|10||Minimum Spanning Trees||[PDF]|
|11||Shortest Path Dijkstra’s||[PDF]||Clustering [Thur 30]|
|12||Max Flow / Bipartite matching||[PDF]|
|14||Tries||[PDF]||Faster than a hash-map
|16||Dynamic Programming I (NL)||[PDF]||Max’s Bonus Problem
|17||Dynamic Programming II (NL)||[PDF]|
|19||Markov Models (NL)||[PDF]|
|21||Linear Programming||[PDF]||Write Up 2[June 6]
Write Up 2.zip
(P/ NP) & (Reductions)
|23||Back Tracking (NL)||Cryptarithms [June 6]|
|May 22||Midterm 1||Topics: 1 -8|
|May 29||Midterm 2||Topics 8 – 16|
Structure of the final
- Solving Recurrences & Linear Programming
- Question on Sorting similar to midterm 1
- Bipartite matching question
- Couple surprise questions.
List of Problems for the final 13 problems. Will select 3.
- 198 House Robber (DP problem)
- 269 Alien Dictionary (Topological Sort) [link]
- 139 Word Break (Trie)
- 305 Number of Islands (Union Find)
- 329 Longest Increasing Path in a Matrix (DP problem)
- 133 Clone Graph (Graph traversal)
- 336 Palindrome Pairs (Trie)
- 17 Letter Combinations of a Phone Number (might change test- BackTracking)
- 207 Course Schedule (Topological Sort)
- 46 Permutations (might change test- BackTracking)
- 75 Sort Colors (Might change to test stability)
- 70 Climbing Stairs (DP problem)
NL – New lecture
NT – Next Time
|Everyday 10:00PM – 12:45PM||Thorton D115|
Grade Break Down
Writeup 10% (break down 2% 8% 2% (Last writeup is for extra credit) )
Midterm 1: 12.5%
Midterm 2: 12.5%
Problem Portfolio: 50%
[Link to Project Portfolio]
Homeworks are due Every Monday & Thursday at 10:00pm. To submit follow the instruction in each Java Class in the portfolio. There are 20 (including 3 bonus problems) implementation problems and 3 write ups.
Head TA: Jason (firstname.lastname@example.org)
Daniel Graham Rice 411
Monday & Wednesday 2pm – 4pm
If you sign up for this class off of the waitlist, you are responsible for all homework assignments that were due before you enrolled in class. You will receive an appropriate extension on Assignment 0, however you will not receive extensions on the programming assignments. You do not need to be on the class roster to access the programming assignments, thus you are responsible for completing them and turning them in on time through the tool.
Students with disabilities or learning needs
It is my goal to create a learning experience that is as accessible as possible. If you anticipate any issues related to the format, materials, or requirements of this course, please meet with me outside of class so we can explore potential options. Students with disabilities may also wish to work with the Student Disability Access Center to discuss a range of options to removing barriers in this course, including official accommodations. Please visit their website for information on this process and to apply for services online: sdac.studenthealth.virginia.edu. If you have already been approved for accommodations through SDAC, please send me your accommodation letter and meet with me so we can develop an implementation plan together
Discrimination and power-based violence
The University of Virginia is dedicated to providing a safe and equitable learning environment for all students. To that end, it is vital that you know two values that I and the University hold as critically important:
- Power-based personal violence will not be tolerated.
- Everyone has a responsibility to do their part to maintain a safe community on Grounds.
If you or someone you know has been affected by power-based personal violence, more information can be found on the UVA Sexual Violence website that describes reporting options and resources available – www.virginia.edu/sexualviolence.
As your professor and as a person, know that I care about you and your well-being and stand ready to provide support and resources as I can. As a faculty member, I am a responsible employee, which means that I am required by University policy and federal law to report what you tell me to the University’s Title IX Coordinator. The Title IX Coordinator’s job is to ensure that the reporting student receives the resources and support that they need, while also reviewing the information presented to determine whether further action is necessary to ensure survivor safety and the safety of the University community. If you wish to report something that you have seen, you can do so at the Just Report It portal. The worst possible situation would be for you or your friend to remain silent when there are so many here willing and able to help.
It is the University’s long-standing policy and practice to reasonably accommodate students so that they do not experience an adverse academic consequence when sincerely held religious beliefs or observances conflict with academic requirements.
Students who wish to request academic accommodation for a religious observance should submit their request in writing directly to me by Piazza private message as far in advance as possible. Students who have questions or concerns about academic accommodations for religious observance or religious beliefs may contact the University’s Office for Equal Opportunity and Civil Rights (EOCR) at UVAEOCR@virginia.edu or 434-924-3200.