COMPSCI 430 Algorithm Paradigms |
This course is an introductory graduate course on the design and analysis of algorithms. The course builds on an undergraduate-level study of the analysis and implementation of data structures and algorithms (COMPSCI 201). The goal is to introduce a number of important algorithm design techniques as well as basic algorithms that are interesting both from a theoretical and also practical point of view. We will cover basic algorithm design techniques such as divide-and-conquer, dynamic programming, and greedy techniques for optimization. We will cover techniques for proof of the correctness of algorithms and also asymptotic analysis of algorithm time bounds by the solution of recurrence equations. We will apply these design and analysis techniques to derived algorithms for a variety of tasks such as sorting, searching, and graph problems. Some specific algorithm topics include: deterministic and randomized sorting and searching algorithms, depth and breadth first search graph algorithms for finding paths and matchings, and algebraic algorithms for fast multiplication and linear system solving.
An undergraduate-level course on the analysis and implementation of data structures and algorithms (COMPSCI 201 or equivalent) and also four semesters of college mathematics. This course requires a certain amount of mathematical sophistication (e.g., as required to solve recurrence equations). A quiz on recurrence equations early in the course will provide you with some feedback on whether your mathematics training will suffice. If you feel that you may not have sufficient background, please talk with the instructor John Reif.
|
Times:
Tues & Thurs 11:45 PM – 1:00
PM Room: LSRC D243 |
Professor John Reif |
||
Office: |
|
D223
LSRC Building |
Phone: |
|
919-660-6568 |
Email: |
|
|
Web
page: |
|
|
Office
hours: |
|
Tues,
Thurs: 1:00 - 2:00 PM |
Office: |
|
208 North Building |
Phone: |
|
919-667-7346 |
Email: |
|
|
Web page: |
|
|
Office hours: |
|
4:00 – 5:00 PM Wednesday and
Friday |
á
Solutions to Selected exercises and
problems in CLRS
Optional auxiliary reading (other good reference books):
Consult the schedule of lecture topics for a list of topics and a copy of lecture notes for the lectures to date. Other handouts can be found in the handouts directory, and homeworks and old midterm and final exams can be found in the homework directory. See resources page for additional information.
Homeworks are
due roughly every second week and must be turned in before class on Wednesday
of the week they're due. No credit is given for late solutions. For exceptional
circumstances, see John Reif in advance, rather than after the due time. Homework assignments
will be archived in the homework
directory. The postscript version, pdf version, and source LaTeX code will
be available for each homework problem.
Details about proper
style [ps]
for writing up homework solutions and some guidelines for grading are
available.
It is
recommended but not required that LaTeX be used for typesetting homework
problems.
Honor code: For homework problems, discussion among students is permitted, but students must write up solutions independently on their own. No materials or sources from prior years' classes or from the Internet can be consulted. During every exam: all calculators, computers, cell phones, wireless or bluetooth-connected devices, and all other electronic devices must be identified and handed over to the person proctoring the exam. Breaking the rules can result in expulsion. Each student is required to make a copy of this paragraph, sign it indicating that the contents are understood, and turn it in to John Reif.
There will be no make-up exams for missed exams. Missing one of the three midterm exams due to an illness requires filing the web-based Short-Term Illness Notification Form at http://www.aas.duke.edu/trinity/t-reqs/illness, and will result in the remaining midterm exams grades being re-weighted appropriately. By University Policy, missing the Final exam results in a grade X.