COMPSCI 531D Introduction to Algorithms

Lectures - Teaching Assistant - Resources

Canvas Website for COMPSCI 531D  Introduction to Algorithms

Course 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:

A student taking the course should already have taken an undergraduate-level course on data structures and algorithms (e.g., 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 an instructor.

Meetings (Lectures and Recitations)

Room: LSRC A247

Times: Tues, Wends & Thurs 3:05 PM – 4:20 PM 

Lectures

Room: LSRC A247

Instructor: Professor John Reif

Office:		D223 LSRC Building
Phone:		919-660-6568
Email:		reif at cs.duke.edu
Web page:		www.cs.duke.edu/~reif
Office hours:		Weds, Fri: 9:00AM – 10:00 AM – via Zoom

 

 

TA RECITATIONS:  Room: LSRC A247

 

TA:  Vincent Li Office hours: ·      Tues 5pm-6pm and Wed Noon-1pm (please email to reserve) ·      Phone: 305-338-7289 ·      Email:  vincent.l.li@duke.edu

Course material:

• Lectures: Various lecture notes and research papers (downloadable).
• Text Books

• [E] Jeff Erickson, Algorithms (free download)
• [CLRS] Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, McGraw-Hill, fourth edition, 2022. Be sure to get the fourth edition (ISBN-13: 978-0262046305, ISBN-10: 026204630X)

·       Solutions to Selected exercises and problems in CLRS

·       Bug Reports in CLRS

Optional auxiliary reading (other good reference books):

• [DPV] Dasgupta, Papadimitriou, and Vazirani. Algorithms, McGraw-Hill, first edition, 2006. (ISBN: 0073523402)
• 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

 

Summary of topics covered and lecture notes:

Consult the schedule of Lectures for a list of topics and a copy of lecture notes for the lectures to date. See resources page for additional information.

Homework assignments:

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.    

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 recommended but not required that LaTeX be used for typesetting homework problems. 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.

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.

Honor code: For homework problems, discussion among students is permitted, but students must write up solutions independently on their own. 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.  

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 (15%)
• Homework assignments (20%)
• 4 Closed-book exams and quiz (10% each)
• Closed-book 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 appropriately. By University Policy, missing the Final exam results in a grade X. The grades will be curved when calculating the final letter grade.

Anonymous course feedback: Anonymous comments