Department of Computer Science
North Central College

Spring 2020

CSCE 340 Design and Analysis of Algorithms


Dr. Godfrey Muganda

Catalog Description

Design and analysis of algorithms
Classification 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.