Comp 550 Algorithms and Analysis (Spring 2015)

Announcements

• [NEW] Final Exam: 8:00 - 11:00 May 4, 2015 at FB009. Please arrive 5 minutes earlier.
  • I plan to email (separately) your score (of the final) and grade (of the course) by 23:59 May 5.
• Office hours during exam period have been decided (Apr 29 11:00 - 12:00, May 1 16:30 - 17:30; May 6 11:00 - 12:00)
  
  

General Information

• Instructor: Zhishan Guo (zsguo [at] cs.unc.edu)
• Office Hours: Mo 10:00 - 11:00, We 10:00 - 11:00, We 14:30 - 15:30 (Jan 7 - Apr 24), or by appointment, in SN126
  • Office Hours during final-exam period: Apr 29 11:00 - 12:00, May 1 16:50 - 17:50; May 6 11:00 - 12:00
• Lecture Time/Location: Mo We Fr 09:05 - 09:55, in FB 009
• Course Website: http://www.cs.unc.edu/~zsguo/comp550.html, Piazza: https://piazza.com/unc/spring2015/comp550/home
• Travel: I will be out of town during Mar 14-21 and Apr 14-17.
  Co-Instructor Kecheng Yang (yangk [at] cs.unc.edu) will be in charge of the course during that period.
  
  

Syllabus

Click here to see the official course syllabus.

The syllabus for this semester is here.

Powerpoint Slides & Schedule

A link to each file will be added once ready.

• (Week 1) Chapter 1, 2 -- Introduction, CLRS Ch. 1-3
• (Week 2) Chapter 3, Appendix A -- Asymptotic Notations, Example, CLRS Appendices
• (Week 3 & 4) Chapter 2.3, 4 -- Divide and Conquer
• (Week 5) Chapter 7 -- Quicksort
• (Week 6 & 7) Appendix C, Chapter 5, 7.3 -- Randomized Algorithms (note)
• (Week 7) Chapter 8 -- Linear Time Sort*
• (Week 8) Chapter 9 -- Order Statistics
• (Week 8 & 9) Chapter 11 -- Hashing (note) (More on hashing: More analysis of Linear Probing, 2-Choice, Cuckoo(wiki), Cuckoo w/ Stash)
• (Week 9 - 11) Chapter 12,13 -- Binary Search Tree (BST deletion examples), Red-Black Tree
• (Week 12 & 13) Chapter 22 -- Graph Algorithms (More on sparse graphs: Planar Graph)
• (Week 13 & 14) Chapter 15 -- Dynamic Programming (LCS in-class example, LCS online video, O(n log n) Algorithm for Matrix Multiplication)
• (Week 14 - 16) Chapter 16, 23, 24 -- Greedy Algorithms (Greedy_Stays_Ahead)
• Chapter 29 -- Linear Programming*
• Chapter 34, 35 -- NP-Complete* (* = may or may not be covered)

Acknowledgement: The power point slides and HWs are modified from the slides/materials made by previous instructors Profs. Mark Foskey, Ming Lin, Dinesh Manocha, Ketan Mayer-Patel, David Plaisted, Jack Snoeyink and Dr. Umamaheswari Devi. I also used some examples from Prof. Jeff Erickson's Algorithm course materials.

Homeworks

HW1, due on 9:05 Jan 23, 2015
HW2, due on 9:05 Feb 2, 2015
HW3, due on 9:05 Feb 11, 2015
HW4, due on 9:05 Feb 23, 2015
HW5_Part_A, due on 9:05 Mar 16, 2015 (Self Study: Ch 12.1 - 12.3 BST)
HW5_Part_B, due on 9:05 Mar 20, 2015
HW6, due on 9:05 Apr 6, 2015
HW7, due on 9:05 Apr 10, 2015
HW8, due on 9:05 Apr 24, 2015

Course Project (Optional)

Project Information, due on 23:59 Apr 26, 2015

Quizes & Exams

Quiz1, Quiz2 (Pancake Sorting Links: i,ii,iii), Quiz3, Quiz4 (Prof. G is correct), Quiz5, Quiz6

Mid-Term 2 on 9:00 Mar 18 Mar 23, 2015 (Sample Test); 2 pieces of Cheat sheet are allowed

Mid-Term 3 on 9:00 Apr 17, 2015 (Sample Test); 3 pieces of Cheat sheet are allowed

FINAL on 8:00 May 4, 2015; 4 pieces of Cheat sheet are allowed

You may ask for hard copy solutions to HWs and Exams from the instructor.
You may print or write whatever you want on both sides of the cheat sheet.