Algorithms

Final Friday, June 7, 2019 10:00PM-1:00PM

[Seiden’s:_Theoritical Computer Science Cheat Sheet]

[Link to Project Portfolio]

Feel free to use any code from the [Princeton Algorithms Code PortFolio]

9Strongly Connected Components[PDF]DDR Robot [Thur 30]

 

Lecture Topic Slides
/Notes
Assignment Video
1  Union-Find [PDF] Overleaf.com 
Write Up 0 [Thur 16]
[PDF] [Write Up 0]LRU Constant Time [Thur 16]
[Video]
2 Sorting and Comparators
(+Graham Scan(NT))
[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
[PDF] Notes from Scribe
[Substitution]
[Video]

[Video]

6 Geometric Search [PDF] Bird Scooters [Thu 23] [Video]
7 Solving Recurrence Relations [PDF] [Video]
8 Master Theorem & Karatsuba (NL)  (Solve multiple) [PDF1][PDF2]
[Notes]
[Recitation Work Sheet]
1  Write up [Thur 23]
[PDF] [Latex File 1]
[Video]
9 Back Tracking (NL) [PDF] Cryptarithms [Thur 30]
10 Minimum Spanning Trees [PDF]
11 Shortest Path Dijkstra’s [PDF] Clustering [Thur 30]
12 Max Flow / Bipartite matching [PDF]
13 Radix Sorts [PDF]
[Paper]
14 Tries [PDF] Faster than a hash-map
[June 6]
15 SubString Search [PDF]
16 Dynamic Programming I (NL) [PDF] Max’s Bonus Problem
[June 6]
17 Dynamic Programming II (NL) [PDF]
18 Belman Ford [PDF]
19 Markov Models (NL) [PDF]
20 Reductions [PDF]
21 Linear Programming [PDF] Write Up 2[June 6]
Write Up 2.zip
22 Intractability I
(P/ NP) & (Reductions)
[PDF]
23
24
May 22 Midterm 1 Topics: 1 -8
May 29 Midterm 2 Topics 8 – 16

Structure of the final

  1. Solving Recurrences & Linear Programming
  2. Question on Sorting similar to midterm 1
  3. Bipartite matching question
  4. Couple surprise questions.

List of Problems for the final 13 problems. Will select 3.

  1. 198 House Robber (DP problem)
  2. 269 Alien Dictionary (Topological Sort) [link]
  3. 139 Word Break (Trie)
  4. 305 Number of Islands (Union Find)
  5. 329 Longest Increasing Path in a Matrix (DP problem)
  6. 133 Clone Graph (Graph traversal)
  7. 336 Palindrome Pairs (Trie)
  8. 17 Letter Combinations of a Phone Number (might change test- BackTracking)
  9. 207 Course Schedule (Topological Sort)
  10. 46 Permutations (might change test- BackTracking)
  11. 75 Sort Colors  (Might change to test stability)
  12. 70 Climbing Stairs (DP problem)

NL – New lecture

NT – Next Time

Meeting Times:

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%
Final: 15%
Problem Portfolio: 50%

Break down of grading for portfolio:
Grade for portfolio is square root(number problems solved/ total number of problems) * 100 [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.

All written homework assignments can be found on collab.
All programming homework assignments are located on https://autogradr.com. To access them, please make an autogradr student account and enroll in CS 4102: Algorithms using course code: HE206Y . You are responsible for all assignments posted to this course throughout the semester. You can enroll in and begin submitting assignments even if you are on the waitlist of the class.

Office Hours:

[Office Hour Tool: Written by Maxwell Patek

Head TA: Jason (jaa8r@virginia.edu)

Daniel Graham Rice 411
Monday & Wednesday 2pm – 4pm

Info:

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:

  1. Power-based personal violence will not be tolerated.
  2. 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 portalThe worst possible situation would be for you or your friend to remain silent when there are so many here willing and able to help.

Religious accommodations

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.