COMPSCI 531 Algorithm Paradigms

Schedule | Resources | Sakai | Piazza

 

Description

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.

 

Lectures will focus on introducing major algorithmic principles of design and analysis, along with mathematical analysis of algorithmic problems. The weekly lab section will build on that material to explore questions of implementations and applications to real world problems.

 

Prerequisites

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), and we assume you have prior experience with basic programming at the COMPSCI 201 level. 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 an instructor.

 

Meetings

All regular meetings will take place in LSRC B101 from 11:45am - 1:00pm. Lectures will be held on Tuesdays and Thursdays. Labs will be held on Mondays. You can see the full schedule here. You can view recordings of class meetings here.

 

Instructors

Professor John Reif (Lectures)

Office:

 

D223 LSRC Building

Phone:

 

919-660-6568

Email:

 

reif at cs.duke.edu

Web page:

 

www.cs.duke.edu/~reif

Office hours:

 

TBD

 

Brandon Fain (Lab)

Office:

 

D311 LSRC Building

Email:

 

btfain at cs.duke.edu

Web page:

 

www.cs.duke.edu/~btfain

Office hours:

 

1:30 – 2:30 pm on Tuesdays and 1:00 – 2:00 pm on Wednesdays in LSRC D309

 

Teaching Assistants

Shalin Shah

Office:

 

D104 LSRC Building

Email:

 

shalin at cs.duke.edu

Web page:

 

http://people.duke.edu/~sns37/

Office hours:

 

5:00 – 7:00 pm on Thursdays in LSRC D309

 

Xinghao Cheng

Office:

 

N021 North Building

Email:

 

xhcheng at cs.duke.edu

Web page:

 

https://www.cs.duke.edu/people/graduates/764

Office hours:

 

4:30 – 5:30 pm on Tuesdays and 2:00 – 3:00 pm on Wednesdays in LSRC D309.

 

Text Books

      [CLRS] Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, McGraw-Hill, third edition, 2009. Be sure to get the third edition (ISBN: 0262033844)

      Solutions to Selected exercises and problems in CLRS

      Bug Reports in CLRS

      [DPV] Dasgupta, Papadimitriou, and VaziraniAlgorithms, McGraw-Hill, first edition, 2006. (ISBN: 0073523402)

 

Other References

      G. Brassard and P. Bratley. Algorithmic - Theory and Practice. Prentice Hall, 1988.

      D. Kozen. The Design and Analysis of Algorithms. Springer Verlag, 1991.

      A. Aho, J. Hopcroft, and J. Ullman. Design and Analysis of Algorithms. Addison Wesley 1974.

      R. Tarjan. Data Structures and Network Algorithms. SIAM Publications, 1983.

      C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994.

 

Course Topics

      Mathematical Analysis of Algorithms: growth of functions, summations, recurrences, average-case and randomized analysis

      Worst case versus average case analysis

      Sorting and selection: divide-and-conquer and randomized techniques

      Search trees

      Hashing in theory and practice

      Amortized analysis

      Priority queues

      Cryptography algorithms

      Greedy algorithms

      Dynamic programming

      Graph algorithms

      Clustering techniques and community detection in social networks

      Matrix and algebraic algorithms

      Approximation algorithms

 

Homework assignments

There will be two types of homework assignments: theory homeworks and lab homeworks. All assignments will be released to Students on the course Sakai webpage, and all solutions should similarly be submitted on the course Sakai webpage. No credit is given for late solutions. You should turn in what you have on time for partial credit rather than receive a 0. For exceptional circumstances, see the instructor in advance, rather than after the due time. Our policy is that one (and only one) homework during the entire term is allowed not to be handed in, at no loss of credit. Furthermore, if you hand in all the homework, then we will drop the lowest graded homework.

 

In the theory assignments, students will be asked to design algorithms for classic problems and provide mathematical analysis of correctness and asymptotic efficiency. Students will turn in a written set of solutions. It is strongly encouraged that students should type their solutions using LaTeX (we will have a tutorial on LaTeX in the lab section). If handwritten solutions are illegible, they will not be graded. Details about proper style for writing up homework solutions and some guidelines for grading are available.

 

In the lab mini projects, students will work in teams of between one and three people to implement algorithms in software and provide data driven analysis that gives insight into problems motivated by real world applications. In other words, students will be to go beyond just coding up an algorithm from class. Students will turn in a pdf with data and discussion, along with source code written in java, c++, or python (students may write in any of the three languages they prefer). Each team should give a single submission, and all students on that submission will receive the same grade. Students are not required to work with the same group for each assignment, and may complete the lab homeworks alone if they prefer. 

 

Academic Integrity

For theory 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. For details about what is acceptable, see this honesty matrix.

 

For the lab mini projects, students may not work together if they are not in the same group, meaning that you should not discuss or share any material with people outside of your group. Furthermore, you may not use code from the internet or other students outside of your group. Source code will be analyzed for plagiarism.

 

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.

 

Grading

      Class interaction (10%)

      Theory homework (15%)

      Lab homework (15%)

      Quiz exam 1 (5%)

      Midterm exam (15%)

      Late-term exam (15%)

      Final exam (25%)

 

There will be no make-up exams for missed exams. Missing one of the three midterm exams will result in the remaining midterms and final exam grades being re-weighted proportionally. By University Policy, missing the Final exam results in a grade X.

 

Anonymous course feedback

Anonymous comments