Instructor:  John Martin, IACC 258 A13, Phone (231)-8197, email  John.Martin@ndsu.edu

Class:  MWF, 1-1:50,  Van Es 101

Office Hours:  10:30-11:30 MWF and by appointment.

Course Description:  The design, correctness, and analysis of algorithms and data structures.

Course Objectives:   By the end of the course, the student should be familiar with the "big-O" and "big-Theta" notation for describing the asymptotic behavior of quantities such as algorithm runtimes and space requirements.  He/she should be able to analyze simple algorithms and to compare quantitatively the efficiency of alternative algorithms.  He/she should be acquainted with some of the most familiar abstract data types, such as trees, binary trees, and graphs, and with the analysis of the corresponding algorithms; he/she should understand the analysis of some standard algorithms involving searching and sorting.

Prerequisites:  CSCI 161, MATH 166, and either CSCI 222 or MATH 270.

Homework:  There will be regular homework assignments, and homework will count 20% of the final grade.  For the most part the assignments will be problems from the text.   In order to be counted, homework must be turned in by the due date.

Evaluation Procedures and Criteria:    The grade will be based on hour-exam scores, homework, and final-exam score.   The overall exam grade is the larger of the two following numbers:  i) the score obtained by weighting each of the three hour-exams 24% and the final exam 28%;   ii) the score obtained by weighting each of the two highest hour-exams 28% and the final 44%.  The final total will be obtained by weighting the exam grade 80% and the homework 20%. 

At the end of the semester, an overall percentage of 85 or higher will be an A, 70 or higher will be at least a B, and 55 or higher will be at least a C.  The cutoffs for these letter grades may, but will not necessarily, drop slightly below these numbers.

Makeup exams will normally not be given, and makeup exams after the class has taken the exam will almost never be given.  If you miss an exam, then your exam grade will be computed the second way described above (weighting the two remaining exams and the final exam more), and the exam you miss will be the exam that is dropped. 

Attendance:  Although class attendance is not required, you are strongly encouraged to attend class; you are responsible for what goes on in class, including any topics that are not in the text but are discussed in class, and any changes in dates or policies described here.  

Course Calendar:   The three exams are scheduled for Monday, February 11; Friday, March 28; and Friday, April 25.   The final exam is scheduled for Tuesday, May 6, at 8AM.   

Here is a list of the chapters in the text that I would like to cover.  We will probably not get to the end of the list.   The plan is to go in order through the list until the semester comes to an end.  This list is tentative, and may be revised.  In a number of chapters, I may delete certain sections or portions of sections, and I may not present the results in exactly the same form that they are presented in the text.

     Chapter 1.  The Role of Algorithms in Computing  (I won't say much about this in class, but it's short and you should read it.)
     Chapter 2.  Getting Started
     Chapter 3.  Growth of Functions
         (Note: this is an important chapter.  In discussing it we will also look at some of the topics in Appendix A.)
     Chapter 4.  Recurrences
     Chapter 5.  Probabilistic Analysis and Randomized Algorithms
     Chapter 6.  Heapsort
     Chapter 7.  Quicksort
     Chapter 8.  Sorting in Linear Time
     Chapter 9.  Medians and Order Statistics
     Chapter 11.  Hash Tables
     Chapter 12.  Binary Search Trees
     Chapter 21.  Data Structures for Disjoint Sets
     Chapter 22.  Elementary Graph Algorithms
     Chapter 23.  Minimum Spanning Trees
     Chapter 24.  Single-Source Shortest Paths
     Chapter 31.  Number-Theoretic Algorithms
     Chapter 34.  NP-Completeness

Required Student Resources:  The text is Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (Second Edition), McGraw-Hill, 2001.

Special Needs:  Any students with disabilities or other special needs who need special accommodations in this course are invited to share these concerns or requests with the instructor as soon as possible.

Academic Responsibility Policy:  All work in this course must be completed in a manner consistent with NDSU University Senate Policy, Section 335: Code of Academic Responsibility and Conduct (http://www.ndsu.nodak.edu/policy/335.htm).