## Algorithms

 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] 2 Sorting and Comparators (+Graham Scan(NT)) [PDF] Friend Circles [Thur 16] 3 Merge Sort/Heap Sort [PDF] Apple Sort [Thur 16] 4 Quick Sort & Quick Select [PDF] Nth place loser [Thur 23] 5 Balance Search Trees 2-3/Red Black Trees,& B-Trees [PDF] 6 Geometric Search [PDF] Bird Scooters [Thu 23] 7 Solving Recurrence Relations [PDF] 8 Master Theorem & Karatsuba & Substitution [PDF1][PDF2] [Notes] Notes from Scribe [Substitution] [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] 13 Radix Sorts [PDF] [Paper] 14 Tries [PDF] Faster than a hash-map [Thur 30] 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 Back Tracking (NL) Cryptarithms [June 6] 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

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%

Git 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:

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 the 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.

# Honor

I trust every student in this course to fully comply with all of the provisions of the University’s Honor Code. By enrolling in this course, you have agreed to abide by and uphold the Honor System of the University of Virginia, as well as the following policies specific to this course.

· All graded assignments must be pledged.

· All suspected violations will be forwarded to the Honor Committee, and you may, at my discretion, receive an immediate zero on that assignment regardless of any action taken by the Honor Committee.

Please let me know if you have any questions regarding the course Honor policy. If you believe you may have committed an Honor Offense, you may wish to file a Conscientious Retraction by calling the Honor Offices at (434) 924-7602. For your retraction to be considered valid, it must, among other things, be filed with the Honor Committee before you are aware that the act in question has come under suspicion by anyone. More information can be found at http://honor.virginia.edu. Your Honor representatives can be found at: http://honor.virginia.edu/representatives. Additionally, [Support Officer, if any enrolled], an Honor support officer enrolled in this class, is also available for questions.