CS 621

Algorithms and Complexity

[ Canvas | Slides ]

Course Description

Starting with graph basics, this course mainly consists of two components: (1) algorithmic design patterns, including greedy methods, divide-and-conquer, and dynamic programming; and (2) complexity theories, including reductions, problem classes (P, NP, and beyond), and other related topics.

Instructor

Prof. Lei Jiao, jiao@cs.uoregon.edu

Lectures and Office Hours

Lectures: Monday and Wednesday, 2:00-3:20 PM, 471 MCK.
Office Hours: By appointment in Fall 2023. Please feel free to drop an e-mail anytime if you want to meet.

Textbooks and Readings

(Required) Kleinberg and Tardos, Algorithm Design, Addison-Wesley, 2006. (Book slides)

This course involves Chapters 1-9, except Chapter 7, of this textbook.

(Further reading) Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd Edition, MIT Press/McGraw-Hill, 2009.
(Further reading) Dasgupta, Papadimitriou, and Vazirani, Algorithms, McGraw-Hill, 2008.

Learning Outcomes and Acquired Skills

The course investigates several algorithmic techniques, and demonstrates the application of such techniques to a range of problems in diverse scenarios. The course also studies theoretical knowledge and tools in terms of problem classes and complexity analysis. Upon completion of the course, students will be able to explain, analyze, and implement fundamental algorithmic techniques, including greedy algorithms, divide-and-conquer, and dynamic programming, and to understand, interpret, and apply relevant complexity theories to different problems and algorithms.

(Tentative) Schedule

Date	Topic	Slides
Week 1	Graph representation, searching, and matching.	1, 2, 3, 4
Week 2	Greedy methods: Minimum spanning tree, Dijkstra.	1, 2, 3
Week 3	Greedy methods: Minimize lateness, Interval scheduling.	1, 2, 3
Week 4	Greedy methods: Interval partitioning, Huffman codes, Matroid.	1, 2, 3
Week 5	Divide and conquer: Master method, Merge sort, Inversion.	1, 2, 3, 4, 5
Week 5	Dynamic programming: Knapsack, Floyd-Warshall, Bellman-Ford.	1, 2, 3, 4, 5
Week 6	Dynamic programming: Memorization, weighted intervals.
Week 7	Dynamic programming: Sequence alignment, CYK, order in problems.
Week 8	Complexity: Polynomial reductions, other reductions, characterizations of NP.
Week 9	Complexity: Satisfiability, 3SAT/3COL, Cook-Levin, below NP, P-completeness.
Week 10	Complexity: Beyond NP, co-NP, and PSPACE.

Assignments, Exam, and Grading

Grading will be based on the following criteria:

Percentage	Component
75%	5 written assignments
25%	1 take-home final exam

Letter grades will be given based on the following scale:

A+ [97, 100]	A [94, 97)	A- [90, 94)
B+ [87, 90)	B [84, 87)	B- [80, 84)
C+ [77, 80)	C [74, 77)	C- [70, 74)
D+ [67, 70)	D [64, 67)	D- [60, 64)
F [0, 60)

All assignments will be distributed via Canvas. Submissions will need to be done via Canvas as well. You are strongly suggested to type your work (e.g., using LaTeX, and Microsoft Word) and submit it as a PDF, instead of using handwritings and/or photocopies. The take-home final exam paper, similar to the written assignment in terms of the format, will be made available on Canvas in Week 11, for which you will have 48 hours to finish and submit your solutions.

Academic Honesty and Other Policies

All projects turned in for the course must be your own work. Copying from others is not acceptable. If you collaborate with someone, you must indicate such on the work you turn in.
Generative AI tools are in general not expected to be used for the homework of this course. If you use such tools in your homework, you are required to explicitly state in detail in your homework which generative AI tools you use and how you use them.
Turning in someone else's work or codes is collusion, and is a particularly heinous form of plagiarism; if collusion is detected, all individuals involved (i.e., the copyee and all copyers) will be given an "F" for the course.
You are also responsible for protecting your work. That is, you must take reasonable precautions to prevent your work from being copied. This means that if you store your assignment solutions on a shared server, the file permissions must be set to keep others from accessing your files. If you are working on assignments on a public machine, you need to remove your files on that machine before leaving.
Academic honesty is expected and cases of suspected dishonesty will be handled according to university policy. In particular, copying someone else's work, including materials found on the web, will not be tolerated. If any part of the solutions are obtained from external sources, the sources must be cited.