• Current Week: 16

Weekly Notes	Topics	Reading	Assignments
Week 1	Syllabus and survey Chapter 1 (ppt) and Math Background (Appendix A) Homework 1 is ready. Don't do the red ones.	Appendix A and Chapter 1	Homework 1 for Spring 2020
Week 2	Finish Math Background (Appendix A) Prove loga x = logb x * loga b, summation Chapter 2 Algorithm Analysis (ppt) Wed: Finish Chap 2, and start Brute Force Chapter 3 (ppt) : Algorithms based on definition Fri: Chap 2: Kinds of algorithms and growth rate. More brute Force Chapter 3 (ppt) Other stuff: log2^3 32 = (log2 32) / 3 = 5/3 A proud father (Poem Author: Hannah Senesh) Interesting Presentation: Nvidia and SPARK Ada Information on C and C++ (for students in OS): ITEC 198D - C ITEC 198G - C++ C++ Essentials for Ada Programmers - Updated version (PDF) (Feedback welcome)	Chapters 1, 2, and 3	Homework 1 due Tues. 1/28/20 Homework 1b due Tuesday 2/4/20
Week 3	Brute Force: Chapter 3 (ppt) Weekend Report: Apollo's Fire: Sugarloaf Mountain The Winner! (Brugh Coffee)	Chapter 3	Homework 1b due Tuesday 2/4/20 Homework 2 is available
Week 4	Today and More Today Don't you love LaTeX and TikZ?! Programming assignment 1 available. More Chapter 2 Algorithm Analysis (ppt) Finish Brute Force Chapter 3 (ppt) : Graph Algorithms Back to Chapter 2 (ppt): Algorithm Analysis Divide and Conquer Chap. 5 (ppt) Notes from ealier years: Graph Algorithms Graph Terminology Elementary Algorithms - BFS and DFS An interesting article on programming: (html)   (pdf)	Chapters 3 and 4	Homework 2 is available
Week 5	Weekend report: Followup, Lavender Hill Mob President's Day ... More performance (Ch 02) More Chapter 4 Decrease and Conquer - Chap. 4 (ppt) : Insertion sort (Top down/Bottom Up). DAG. Dec & Con: Topo sort, minimal perms (superperms) Dec & Con: Grey code, binary search, Mon/Wed: Recurrences: Forward/backward subs, Master Method Recursive Algorithms and Recurrence Equations Chapter 2 Asymptotic Analysis (ppt) More on asymptotic analysis Fri: More Divide & Conquer - Ch 5 (ppt) : P1 and Closest pair	Chapter 4	Homework 3a. Due Fri 2/22/19 Programming assignment 1 available.
Week 6	More Decrease and Conquer Chap. 4 (ppt): Quick select and BST Binary Search: It's not as simple as you think! Divide & Conquer (Ch 5 ppt): Closest Pair, Mergesort, Quicksort Animal Week: Dry mouse Wet snake Mrs. Tiggy-Winkle Players Miss Potter (2006) And from my daughter this: Calling a wild swan Winter drives A winter theme my daughter found: Singing Ice		Homework 3b is available. Due Thursday 2/27/20 Programming assignment 1 available. Exam 1 ???.
Week 7	MFT: 4/18/20 Homework coming P2 coming Divide & Conquer (Ch 5 ppt): Mergesort, Closest Pair, Quicksort Master Method Exam after break (Topics list ) Weekend report: More animals and winter (above) Sweet dreams!? Notes from previous years: Divide and Conquer Java uses a relatively new Quicksort that uses two pivots! Dual Pivot Quicksort JDK Sort		Homework 4 for Spring 20 Programming assignment 1 available.
Week 8	SPRING BREAK! ENJOY!		Homework 4 for Spring 20 Programming assignment 2 available.
Week 9	Extended Break		Homework 4 for Spring 20 Programming assignment 2 available.
Week 10	Information on ITEC 360 via distance Break Report Program 2 notes (and with expanded answers) Exam Next week (Topics list - spring 20 draft ) Zoom review session: Sunday at 2:00 p.m. Divide & Conquer (Ch 5 ppt): Closest Pair, Multiply Recurrence trees and Master Method MFT: Tentative date: 4/25/20 (4/18/20 POSTPONED)		Homework 4. Due Tues 11:59:59 p.m. 3/24/20 Programming assignment 2 available.
Week 11	Pass/Fail: CS Requirement: Grade of CRH or C or better in all ITEC courses applied to the major Major Field Test FAQ (Sneak Preview - which style do you prefer) For Spring or Summer 2020 CSCS graduates. I will be sending out an email next week Dynamic Programming: Chapter 8 (ppt) Some more notes: Dynamic Programming: Overview. Rod Cutting Chained Matrix Multiplication Longest Common Subsequence Optimal Binary Search Tree Knapsack Problem All Pairs Shortest Path (Floyd's Algorithm) Exam this week: Topics list (updated for spring 2020) Exam Instructions Exam 1 pdf	Chapters 6 and 7	Homework 5 Homework 6 Program 2
Week 12	Continue Dynamic Programming: Chapter 8 (ppt) Some more notes: Dynamic Programming: Overview. Rod Cutting Chained Matrix Multiplication Longest Common Subsequence Optimal Binary Search Tree Knapsack Problem All Pairs Shortest Path (Floyd's Algorithm) Transform and Conquer: Chapter 6 (ppt)		Homework 6 for Spr 19
Week 13	Notes on Phase 2 Homework 5 is up: due Saturday morning! MFT: You should have a scheduling email from ETS. Complete by end of exam week. Program 3 Exam 2? Other: Check your checks, TweetNaCl in SPARK, "implementation defined"! Forbes, Christiansburg, Drones, Mockingbird, Lunch Exam 2 Monday week 4/27/20 . (Topics list (from last year) Major Field Test: Ordering now - more info soon Continue Dynamic Programming: Chapter 8 (ppt) Some more notes: Dynamic Programming: Overview. Rod Cutting Chained Matrix Multiplication Longest Common Subsequence Optimal Binary Search Tree Knapsack Problem All Pairs Shortest Path (Floyd's Algorithm)		Homework 7 Program 2 DRAFT.
Week 14	Exam 2 Friday Canceled . Material will be covered on final. (Topics list (from last year) Other: Restored lives Knuth: Collected Papers, Errors of TeX Programming Pearls - Common Words - Tries and more on Tries Wither[s|spoon], Chipping Norton, ... Yikes: You need a homework - I'll get one out today Greedy Algorithms: Chapter 9 (ppt) Minimum Spanning Trees (Prim's and Kruskal's Algorithms) [Greedy] Single Source Shortest Paths (Dijkstra's Algorithm) [Greedy] Independent study presentation: An Introduction to Type Theory - Wednesday 4/17/19, Whitt 214, 4:00 p.m. to 5:30 p.m. Transform and Conquer (continued): Chapter 6 (ppt) Notes on Balanced Trees 2-3-4 Trees (revisited) Red-Black Trees (B-Trees are related, but are covered with the next chapter) Heaps Horner's Method [SKIP] Problem Reduction Time and Space Tradeoffs: Chapter 7 (ppt) Forgot to say: Connection between 2-3-4 trees and Red Black trees Time and Space Tradeoffs (continued): Chapter 7 (ppt) Lower bounds & Linear Sorts (count, radix, bucket) String matching Hash Tables In the notes listed above, we looked at: Simple Uniform Hashing assumption Expected number of elements at slot j Worst case analysis of search Comparison with binary search Mapping ascii keys to integers Multiplication and division methods for hash functions Perfect Hashing definition B-Trees		Homework 5b Homework 6 Program 3 is available.
Week 15	Weekend report: Laid back (grade p2), Santa Maria, Wives and Daughters Homeworks: 6, 7 Exam: Wednesday 10:15 a.m. Review session: Sunday 2:00 p.m.? Rest of week: Minimum bounds for sorting (check) Balanced Trees (check) B Trees (check) Heaps String matching (Time/Space Tradeoff: Chap. 7 (ppt)) Recurrences: Forward and Backward Substitution P, NP, and NP-Completeness Hashing Greedy Algorithms: Chapter 9 (ppt) Minimum Spanning Trees (Prim's and Kruskal's Algorithms) [Greedy] Single Source Shortest Paths (Dijkstra's Algorithm) [Greedy] NP Completeness: Chapter 11 (ppt) NP-Completeness Notes NP-Completeness An interesting article For Knuth's opinion, see his answer to Question 17 of this Twenty Questions article The answer references Coping with Finiteness And for dicusssion, see this reddit discussion Lower Bounds - Linear Sorts Do all well defined problems have algorithms: The Halting Problem does not ITEC 420 Final Exam Topics Review session? Sorting out Sorting Sorting out Sorting		Homework 8 due Friday Program 2 due Saturday (No late programs)
Week 16	Comprehensive Final Exam: Final (with white space for answers) Final (with most white space removed) 10:15 a.m. - 12:15 p.m., Wednesday, May 6, 2020 The exam will be open book, open notes, open internet, closed neighbor. Of course you are not to communicate with anyone, other than me, during the exam. You can communicate with me via private chat. Topics (for Fall 2020) How will the exam be conducted: Around 10:05 a.m. I will start a zoom meeting (tiny.cc/nokie-meet) that you should join. We'll keep our audio off so that we don't disturb each other. I'd prefer that you have your video on, but that's not required. As someone said, it seems more like a regular exam with it on. Within the next few minutes I will send out a pdf of the exam via email I will also post the pdf here You can print the exam and answer on it directly or you can answer on separate paper. Include your name in your filename(s). Put your name (or initials) and page number on all pages, along with the page number. At or before 12:15 a.m. you should finish up by scanning or photograping your answers and sending the images to me via email. Other students have had good success with the camscanner app. Your email should say how many pages of answers that you have and how many files you are sending. In general, attachments are easier to deal with than embedded images. Do not leave the meeting until I have told you that I have received your exam. My 320 exam is 8:00 - 10:00, and so there may be some overlap of people from both classes during the transition. Exam week schedule Semesters used to be a week longer		Comprehensive Final Exam

• Check my grades


• Syllabus


• Algorithms reference book: http://www.cs.berkeley.edu/~vazirani/algorithms.html