This course introduces the design and analysis of algorithms, a fundamental aspect of computer science. Throughout the course, we will get to know fundamental algorithm concepts, exploring a range of topics including greedy algorithms, divide-and-conquer algorithms, dynamic programming, and graph algorithms. In addition, we will apply these techniques to both the development and analysis of algorithms for significant problems, such as scheduling, caching, sorting, the knapsack problem, matrix multiplication, shortest path algorithms, minimum spanning tree algorithms, and more. Moreover, the course will cover the limitations of algorithms, including concepts like NP-completeness theory and approximation algorithms. By the end of this course, you'll have a solid understanding of these essential algorithms and their applications, as well as an appreciation for the theoretical insights that guide algorithmic design and analysis.
Lecture Time: Mon-Wed-Fri 04:00PM - 04:50PM
Lecture Location: Nsc 201
Credits: 3
Please sign up for the course on Piazza.
Instructor: Kelin Luo
Office Location: 306 Davis Hall
Office Hour: Mon-Wed-Fri 09:00AM - 09:50AM (Except for the office hours provided for Algorithm course Section B and Section C, you can also schedule an appointment with me via email for additional office hours.)
Email: [first name][last name][at][buffalo][dot][edu]
|
Teaching Assistants: Davoud Moradi Xiaoyu Zhang Xuelu Feng Ibrahim Bahadir Altun Yuxin Liu |
Office Hour: Tue, Thu: 11:10AM - 12:00AMWed, Fri: 03:00PM - 03:50PM Mon, Wed: 02:00PM - 02:50PM Tue, Thu: 10:00AM - 10:50AM Tue, Wed: 10:00AM - 10:50AM |
Email: [davoudmo][at][buffalo][dot][edu][zhang376][at][buffalo][dot][edu] [xuelufen][at][buffalo][dot][edu] [ialtun][at][buffalo][dot][edu] [yuxinliu][at][buffalo][dot][edu] |
You should have taken CSE250 (data structure) or similar courses before. We expect you to have certain levels of mathematical maturity: You should have basic understanding of calculus (e.g., limit, differentiation, integration) and linear algebra (e.g., matrix, vector space, linear transformation); You should be comfortable to read and write mathematical proofs, understanding common proof strategies (e.g., proof by induction, contradiction). We also expect you to have some programming experience: know what is a computer program, and be able to read and write code.
Master the fundamental concepts in algorithm analysis and design.
| Learning Outcomes | Method of Assessment |
|---|---|
| 1. Proficiently understand and apply asymptotic notations and analysis | Quiz, Homeworks, Exam |
| 2. Have a good overall picture of algorithm analysis and design techniques | Quiz, Homeworks, Projects, Exam |
| 3. Solve simple to moderately difficult algorithmic problems arising in applications | Quiz, Homeworks, Projects, Exam |
| 4. Understand the notions of NP-completeness and approximation algorithms | Quiz, Homeworks, Exam |
| 5. Be able to demonstrate the hardness of simple NP-complete problems | Homeworks, Exam |
Your final grade will be computed as follows:
* Class Participation: 5% = 1% × (5 quizzes). Quizzes will be given randomly during the lectures.
* Homeworks: 40% = 8% × (5 homeworks). We choose the best 5 scores out of 6 homeworks.
* Programming Projects: 20% = 10% × (2 programming projects).
* Final Exam: 35%.
Note: (1) Each component will receive a numerical score. The course grade will be based on the weighted total of all components. (2) Class participation includes attendance, participation in class discussions, or quizzes. We will choose the best 5 scores out of a total of 8-10 quizzes for grading. (3) The final exams will be closed-book, and closed-notes.
The following outlines the grade breakdown that will be utilized for assigning grades in the course. Please note that these ranges may be subject to adjustment at the end of the semester to address any inconsistencies or hardships that may arise. It is important to emphasize that grades will not be curved/adjusted during the semester.
| Grade | Percentage |
|---|---|
| A | 90% - 100% |
| A- | 85% - 89.99% |
| B+ | 80% - 84.99% |
| B | 75% - 79.99% |
| B- | 70% - 74.99% |
| C+ | 65% - 69.99% |
| C | 60% - 64.99% |
| C- | 55% - 59.99% |
| D | 50% - 54.99% |
| F | Below 50% |
If you have a question about the grading of any piece of work, please consult on Piazza. Any questions about the grading of a piece of work must be raised within one week (and the regrade deadline posted on Piazza) of the date that the work was returned by the teaching assistant or the instructor.
Please see the University rules on an Incomplete. Assignment of an ''I'' grade is at the discretion of the instructor.
* Collaboration and Discussions: You are permitted to engage in discussions with your classmates regarding homework problems. However, it is strongly recommended that you invest sufficient time thinking about each problem independently before engaging in discussions. All solutions must be written in your own words and produced by you individually. If you collaborate with fellow students, you must provide their names when submitting your work.
* Use of Artificial Intelligence Technologies: The use of generative artificial intelligence, large language models (LLMs), and other artificial intelligence-related technologies is generally prohibited. This encompasses tools like OpenAI's ChatGPT, Google Bard, and AI models within search interfaces like Google or Bing. Utilizing these tools for course content creation, debugging assistance, idea generation, or similar purposes constitutes a breach of academic integrity. All work submitted for evaluation in this course must be exclusively your own.
* Consequences for Violations: Failure to follow to the aforementioned rules will be treated as cheating and a violation of academic integrity. In addition to receiving an immediate grade of F for the course, further actions in alignment with theDepartment's Academic Integrity Policy and theUniversity's Academic Integrity Policy will be taken.
There are no required textbooks, but most of the contents we will discuss are covered in the following books:
Similar courses taught in other universities:
| HWs/Projects | Releasing Date | Deadline |
|---|---|---|
| HW1 | Sep 11 | Sep 25 |
| HW2 | Sep 25 | Oct 09 |
| HW3 | Oct 09 | Oct 23 |
| HW4 | Oct 23 | Nov 13 |
| HW5 | Nov 13 | Nov 27 |
| HW6 | Nov 27 | Dec 06 |
| Project 1 | Oct 02 | Oct 30 |
| Project 2 | Nov 06 | Dec 04 |
| Week | Date | Topic | Contents | Other Notes |
|---|---|---|---|---|
| 1 | Aug 28 | Introduction | course syllabus | |
| Aug 30 | asymptotic notations (KT 2.2) | |||
| Sep 01 | running times and exercise problems (KT 2.4) | |||
| 2 | Sep 04 | Labor Day Observed, no class | ||
| Sep 06 | Graph Basics | graph basics (KT 3.1, 3.2) | ||
| Sep 08 | representation and types of graphs | |||
| 3 | Sep 11 | connectivity and traversal (KT 3.4) | HW1 Released | |
| Sep 13 | topological order (KT 3.6) | |||
| Sep 15 | Greedy Algorithms | basics, interval scheduling (KT 4.1) | ||
| 4 | Sep 18 | interval scheduling (KT 4.1) | ||
| Sep 20 | optimum caching (KT 4.3) | |||
| Sep 22 | optimum caching and exercise problems | |||
| 5 | Sep 25 | huffman code (KT 4.8) | HW 1 Deadline HW 2 released |
|
| Sep 27 | More Greedy Algorithm Exercise Problems | |||
| Oct 29 | Divide and Conquer | basic merge sort (KT 5.1, 5.3) | ||
| 6 | Oct 02 | merge sort and counting inversions (KT 5.1, 5.3) | Project 1 released | |
| Oct 04 | counting inversions and quick sort (KT 5.3, KT 13.5) | |||
| Oct 06 | selection problem and Exercise problems (KT 13.5) | |||
| 7 | Oct 09 | Fall Break, no class | HW 2 deadline HW 3 released |
|
| Oct 11 | solving recurrences and fibonacci number (KT 5.2) | |||
| Oct 13 | More Divide-and-Conquer Algorithm Exercise Problems | |||
| 8 | Oct 16 | Dynamic Programming | weighted interval scheduling (KT 6.1) | |
| Oct 18 | subset sum problem (KT 6.4) | |||
| Oct 20 | knapsack problem (KT 6.4) | |||
| 9 | Oct 23 | sequence alignment (KT 6.6) | HW 3 deadline HW 4 released |
|
| Oct 25 | shortest paths | |||
| Oct 27 | matrix chain multiplication | |||
| 10 | Oct 30 | Optimum binary search tree | Project 1 deadline | |
| Nov 01 | More Dynamic Programming Algorithm Exercise Problems | |||
| Nov 03 | Graph Algorithms | minimum spanning tree and Kruskal's algorithm (KT 4.5) | ||
| 11 | Nov 06 | Reverse-Kruskal's algorithm and Prim's algorithm for MST (KT 4.6) | Project 2 released | |
| Nov 08 | shortest paths and Dijkstra's algorithm (KT 4.4) | |||
| Nov 10 | Dijkstra's algorithm and exercise problems (KT 4.4) | |||
| 12 | Nov 13 | shortest paths with negative weights and Bellman-Ford algorithm (KT 6.8) | HW 4 deadline HW 5 released |
|
| Nov 15 | all-pair shortest paths and Floyd-Warshall algorithm | |||
| Nov 17 | More Graph Algorithm Exercise Problems | |||
| 13 | Nov 20 | NP-Completeness | P, NP, Co-NP (KT 8.1-8.3) | |
| Nov 22 | Thanksgiving Break, no class | |||
| Nov 24 | Thanksgiving Break, no class | |||
| 14 | Nov 27 | polynomial time reductions and NP (KT 8.4) | HW 5 deadline HW 6 released |
|
| Nov 29 | circuit-SAT, 3-SAT (KT 8.5) | |||
| Dec 01 | independent set problem and more exercise problems (KT 8.5) | |||
| 15 | Dec 04 | HW solutions, Q & A | Project 2 deadline | |
| Dec 06 | HW 6 deadline | |||
| Dec 08 | ||||
| 16 | Dec 11 | Last Day of Classes, Q & A | ||
| Dec 19, Tuesday, 15:30-18:30: Final Exam, at Nsc 201 | ||||