In this course, you will learn about (1) how to design fast algorithms, and (2) why they work correctly.
We will discuss several fundamental paradigms in designing algorithms, and how to rigorously argue their correctness. In each paradigm, we will cover several important algorithms, highlight the common ideas shared by them, and see how to apply these algorithms to other seemingly unrelated problems.
There is no programming in this course, but you can, and are encouraged to, attend the NCSU competitive programming practice organized by Dr. David Sturgill, where you will learn how to implement many of the algorithms covered in this course and how to use them to solve other problems. It can be taken as a course (CSC 295) and can be useful for job interviews.
You are expected to be familiar with topics covered in Discrete Math (CSC 226), Data structures and Algorithms (CSC 316). In particular, it is important to refresh your memory on the following concepts before coming to class:
The free book "Mathematics for Computer Science" by Lehman, Leighton, and Meyer is an excellent resource for learning these concepts. It also comes with a set of online lectures.
To give you an idea of whether you have met the prerequisites, a Homework 0 will be assigned and graded before census day.
Slides will be provided. A primary reference will be the textbook [CLRS] "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein. An ebook can be accessed via NCSU libraries.
Any of the following activities can be counted towards class participation:
There will be 4-6 questions for each problem set. You have 2 weeks to complete each of them.
Homework policy:
You will submit your homework solution as a PDF to Gradescope. You are strongly encouraged to typeset your solutions, but clearly legible handwritten solution will also be accepted. To keep your solutions clear and concise, you should develop your solutions in draft form before writing/typing it down. Overleaf is a popular online editor for typesetting math equations.
You are encouraged to discuss homework questions with others in the class, but only after spending some reasonable amount of time (~30 mins) on each question on your own. You must write down your own solutions in your own words, without consulting others while you are writing them. You must list the names of your collaborators (if there are any) for each problem. If you are not sure about what a question is asking, you should ask on Ed immediately.
Each student has a total of 8 late days for homework submission for the whole semester, of which you can use up to 2 days on any problem set. Each late day is exactly 24 hours and cannot be subdivided, that is, a 5-minute late is counted as 1 late day. No request is required for these 8 late days, but any extension request beyond them will be subject to Academic Absence Verification. When late days are used up and a problem set is submitted L days late, the grade for that problem set will be multiplied by 0.9L.
To ensure that homeworks are graded and solutions are posted in a timely-manner, no problem set will be accepted after 4 days have elapsed from the initial due date.
Exam policy:
Exams must be taken in-person and cannot be taken virtually. Any rescheduling request will be subject to Academic Absence Verification.
Regrade policy:
If you dispute the grade received for a problem set, you must submit, in writing through Gradescope, a detailed and clearly stated argument for what you believe is incorrect and why, within 5 days after the homework was returned to you.
All regrade requests will be reviewed by the instructor. Requests of regrade of a specific problem may result in a regrade of the entire assignment. This regrade and written response is final. Keep in mind that a regrade request may result in the overall score for an assignment being lowered.
The following tentative schedule is subject to change according to the pace and interest of the class.
| Lecture | Date | Topics |
|---|---|---|
| 0 | 8/20 (Tue) | Logistics, Topics preview |
| 1 | 8/22 (Thu) | Computation model, "Time" complexity |
| 8/27 (Tue) | No class | |
| 8/29 (Thu) | No class | |
| 8/30 (Friday) | Census Date | |
| 2 | 9/3 (Tue) | Divide and Conquer |
| 3 | 9/5 (Thu) | Divide and Conquer |
| 4 | 9/10 (Tue) | Divide and Conquer |
| 5 | 9/12 (Thu) | Graph algorithms |
| 9/17 (Tue) | Wellness Day (No class) | |
| 6 | 9/19 (Thu) | Graph algorithms (HW1 due) |
| 7 | 9/24 (Tue) | Graph algorithms |
| 8 | 9/26 (Thu) | Graph algorithms |
| 9 | 10/1 (Tue) | Greedy algorithms |
| 10 | 10/3 (Thu) | Greedy algorithms (HW2 due) |
| 11 | 10/8 (Tue) | Review |
| 12 | 10/10 (Thu) | Midterm exam |
| 10/15 (Tue) | Fall break (No class) | |
| 13 | 10/17 (Thu) | Greedy algorithms |
| 14 | 10/22 (Tue) | >Greedy algorithms |
| 15 | 10/24 (Thu) | Dynamic Programming (HW3 due) |
| 10/29 (Tue) | No class | |
| 16 | 10/31 (Thu) | Dynamic Programming |
| 17 | 11/5 (Tue) | Dynamic Programming |
| 18 | 11/7 (Thu) | Dynamic Programming (HW4 due) |
| 19 | 11/12 (Tue) | Hard problems |
| 20 | 11/14 (Thu) | Hard problems |
| 21 | 11/19 (Tue) | Hard problems |
| 22 | 11/21 (Thu) | Hard problems |
| 23 | 11/26 (Tue) | Practices (HW5 due) |
| 11/28 (Thu) | Thanksgiving (No class) | |
| 24 | 12/3 (Tue) | Review |
| 12/5 (Thu) | Final exam |
This is a standard course in most universities worldwide. So an overwhelming amount of resources are available online. The following textbooks provide a more detailed account, or a different take, on the topics covered in this course.