Catalog Description
Design and analysis of algorithmsClassification of algorithms by time and space complexity. Algorithm design techniques such as divide and conquer, the greedy method and dynamic programming. NP-complete problems and approximation algorithms. Introduction to parallel algorithms.
Office Hours
By appointment, at 3:30-4:30 pm Tuesdays and Thursdays in the part-timer's office. I can also see you by appointment at a mutually convenient time if those hours do not work for you.Course Overview
We will start with a review of the mathematical foundations needed for a successful analysis of the efficiency and complexity of algorithms: the concepts of Big O, Big Omega, and Big Theta, and their use to characterize the worst case and average case complexity of computational problems and their algorithms. We will also briefly review material you should already know from CSCE 210 Data Structures and CSCE 230 Discrete Structures.
Following that, we will cover the major algorithm design techniques: design by induction, divide and conquer, backtracking, dynamic programming, greedy algorithms, and more.
We will also examine the class of NP-complete problems and consider how approximation algorithms can be used to deal with this class of problems.
If time permits, we will look at primality testing algorithms, with emphasis on probabilistic algorithsm.
Class Textbook
Algorithms, by Sanjay Dasgupta, Christos Papadimitriou, and Umesh Vazirani, McGraw Hill, 2008.
Schedule of Course Topics
Topics will be covered in the following order. It is the responsibility of the student to keep track of where we are in the course textbook and read ahead.
| Course Topic | Textbook/Literature Resource |
|---|---|
| Big O, Omega, and Theta | Chapter 0 |
| Divide and Conquer | Chapter 2, skip section 2.6 |
| Graph Algorithms | Chapters 3 and 4 |
| Backtracking Algorithms | Notes on backtracking algorithms |
| Dynamic Programming | Chapter 6 |
| Greedy Algorithms | Chapter 5 |
| Introduction to NP-complete Problems | Chapter 8 |
| Introduction to Approximation Algorithms | Chapter 9 |
| Introduction to Parallel Algorithms | To be determined |
Schedule of Quizzes and Tests
Tentative schedule of quizzes and tests (subject to change if circumstances warrant) is as follows.
| Test / Quiz | Date |
|---|---|
| Quiz 1 | January 21 |
| Quiz 2 | February 4 |
| Test 1 | February 18 |
| Quiz 3 | March 19 |
| Quiz 4 | March 31 |
| Test 2 | April 14 |
| Final Examination | April 28 |
Course Grading
There will be a number of homework assignments / programming projects in addition to the in-class quizzes and tests. Not all homework will be graded. The purpose of the homework, whether graded or not, is to give you a chance to test yourself to see if you understand the course material. The homework is also designed to prepare you for the in-class tests, so you should take it seriously.
If you are not sure if your work is right, you can run it by me before you turn it in to be graded. I will be happy to point out any obvious problems and suggest corrections.
Distribution of percentage points for course components is as follows. All graded homework assignments/ programming projects will be equally weighted and make up 40 % of course grade. Each quizz will be 5%, each test will be 10 %, and the final exam will be 20 % of the course grade.
Course Policy on Late Assignments, Missed Tests, and Plagiarism
Quizzes and tests missed without a legitimate excuse cannot be made up.
You can get help from the instructor, or anybody else, on homework problems. The purpose of the help must be to help you understand how to solve the problem, and not to provide you with the solution.
You should avoid googling for solutions as this will generally not help you understand the material: You are better off coming to the instructor for help instead.
Plagiarism is a very bad thing, so it should be avoided. For the purpose of this course, work will be considered plagiariazed if the student turning it in cannot explain it, or cannot solve the same or a similar problem when asked to.
All homework must be uploaded onto the K-drive by midnight on the date due. At some time after the work is due, I will make a copy of submitted work and take it home for grading. Work uploaded after I do that will be considered late. There is a 10 % penalty on late assignments. Do not rush to turn inincomplete work, or homework you know has errors just so you can beat the latet penalty, because most errors in the homework assignments will cost more than the late penalty.
All late homework assignments must be turned in by the due date of the following assignment in order to be graded. The last assignment of the term must be turned in the the due date to be graded.
No hand-written work will be accepted. All work should be neatly typed, converted to pdf, and uploaded onto your K-drive. The use of LaTex to do all non-programming homework is recommended.