CSCI 321 - Analysis of Algorithms Fall 2007

Instructor   Dr. Bonnie McVey

Course Description

This course studies effectiveness, efficiency and clarity considerations; divide and conquer, greedy methods, dynamic programming, backtrack, basic search and traversal techniques. It investigates general techniques for designing algorithms and emphasizes the mathematics needed by computer scientists. Tactics for measuring algorithms are studied: O-notation for comparing running times; evaluating summations and solving recurrence relations to get these run times. The course also considers computational complexity, which is the classification of the difficulties inherent in problems no matter how powerful computers will ever be.

Required Text

Introduction to Algorithms, 2nd Edition, Cormen, Leiserson, Rivest and Stein, McGraw-Hill, 2001.

CSCI 220 (Data Structures) and MATH 250 (Advanced Foundations of Mathematics).

Check website http://home.snc.edu/bonnie.mcvey/csci321/ often for news, assignments, hints, corrections, solutions, etc.

Topics to be covered (approximate)

Basic Algorithm Analysis

time and space tradeoffs, big-O analysis (and other asymptotic behaviors), recurrence relations, proof of correctness, recursion and induction

Algorithmic Strategies

brute force, backtracking, pattern matching, greedy algorithms, divide and conquer algorithms, branch and bound techniques, approximations, randomized, parallel, dynamic programming, distributed algorithms

Classes P and NP

NP-complete problems, P vs. NP, applications

Policies

1. Attendance is expected. When possible, inform me before class or lab that you will not be there. If you miss a class, you are responsible for all information from the class. You may miss one lab and still hand-in the lab report for credit. If you leave a lab meeting prior to the end of lab time without first completing the lab, you will be considered absent from the lab.
2. Homework and lab reports will be turned in at the beginning of lab on Wednesday of each week. Due dates for other assignments will be announced. A forgotten assignment (an assignment is not forgotten if you are not in class!) may be handed in within 30 minutes after class to my office.
3. Assignments MUST contain your signature indicating that you followed the SNC Academic Honor Code. All documents are assumed not submitted without your signature. Course work must be completed individually; discussion of topics and ideas is encouraged but be sure to write up your solutions separately.
4. SNC ACADEMIC HONOR CODE (adapted from dcp) I actively enforce the Academic Honor Code. By your registration in this course, you agree to abide by the Academic Honor Code. All materials handed in for grading are subject to the code. Each document must bear your signature after the label Honor Code Signature.  It is understood that your signature means that you followed the SNC Academic Honor Code for that assignment. Any document that does not contain your signature is considered not submitted. Below are some guidelines for following the honor code:
   1. No outside sources or references are allowed on exams given "in-class."
   2. Research papers, programs, homework, lab reports must fully document another's ideas and works.
   3. Programming can be a social activity. Indeed, industry often demands that project teams collaborate. You may share your ideas on assignments, but you may not share program code. For example, if Travis and Jared (my nephews) work together on part of an assignment, then both must acknowledge this in the documentation for that program. If Travis asks Jared for help and Jared complies, then it is Jared's responsiblity to make sure that Travis understands the problem and its solution. It is Travis's responsibility to acknowledge Sony's assistance in the program documentation. Neither's grade will be affected.
   4. Students must do their own work on their own directory and memory device. You are in violation of the Academic Honor Code if you share your own or copy another's program code or parts of a program in any form (printed, screen, file, etc). Never leave your work on the disk drives of lab machines or forget to pick up your printouts.
   5. Discussing written assignments with others is often a good experience since there are often many solutions to one problem, but again, the written report is an individual effort. Writing your solutions to the assignment yourself not only helps you more fully understand and but also keeps you from violating the SNC Academic Honor Code.
   6. If in doubt, don't!

Important Dates

In keeping with the St. Norbert College mission to help students develop their full potential, and in compliance with the Americans with Disabilities Act, the College provides supportive services to students with disabilities. For enquiries and further details, please visit the Academic Support Services Office located on the lower level of the John Minahan Science Building (JMS) or contact Karen Goode-Bartholomew, Coordinator of Services to Students with Disabilities (Phone: 403-1326), or visit the website www.snc.edu/academicsupport/disabilities.html.

Another opportunity to teach an algorithms course is finally here! I can't tell you how much I have been looking forward to this (probably even more than you!). Algorithms and data structures have long been interests of mine; in fact, I took every course in algorithms available while a graduate student at Purdue. Although somewhat a result of my endeavors in mathematics, my interest in algorithms truly stems from my life-long interest in puzzle solving.

This course takes puzzle solving one step further, for we are not only interested in how to solve a problem, but also how best to solve the problem. And our definition of "best" may change as we consider all instances, only typical instances, or instances of a large size of the very same problem. And we will learn that sometimes, the "best" solution is really lousy.

Visit the SNC CS catalog web page where an algorithm is defined as "a sequence of unambiguous steps that performs a task." Devising such a sequence is fun. Determining its correctness for any instance of the problem can be challenging. Analyzing its use of time and space and comparing the result with other algorithms helps to determine what is the "best" algorithm.

Read your textbook, ask questions in class and in office hours, work hard. By the completion of this course, you will be armed with strategies for solving lots of problems in computer science as well as in other areas of study. You will be able to defend your algorithm's efficiency and correctness. And you will have some experience identifying intractable problems, those whose only known algorithms are horribly inefficient. I am prepared and excited to help you succeed in this course but the choice to succeed is made by you. Enjoy!