Henry S. Baird    Spring 2007 Course


Design & Analysis of Algorithms

CSE/Math 340     CRNs:  11264 (CSE); 13275 (Math)


Algorithms are methods for solving information processing problems. To be called an algorithm, a method must be fully automatable (e.g. can be run by a computer) and it must be provably correct---i.e. it must find the right answer for every instance of the problem.  It's also often vital that it run as fast as possible, and use as little memory as possible, even when a problem instance is huge.  Algorithms are among the central achievements of computer science research.  This course presents algorithms for searching, sorting, manipulating graphs and trees, scheduling tasks, finding shortest paths, matching patterns in strings, etc---and gives proofs of their correctness and analysis of their runtime and memory demands. General strategies for designing algorithms---e.g. recursion, divide-and-conquer, greediness, dynamic programming---are stressed. Limits on algorithm efficiency are explored through elementary NP-completeness theory.

Prerequisites:  Calculus II (Math 22 or Math 32) and Discrete Structures (CSE/Math 261); or close equivalents (in which case, check with instructor).  To review your Discrete Structures background, carefully read CLRS Appendix sections A.1-2, B.1-3,  C.1.

This is a required course for these degrees: B.S. in CS (in RCEAS), B.A. in CS (in CAS), and the B.S. in Computer Science & Business (in RCEAS & CBE).

This is also the basis for the CS PhD Qualifier exam for Algorithms.

Course objective:  On completing this course, students will be sufficiently familiar with the theory, practice, notation, and vocabulary of algorithm design and analysis to be able to locate in the literature (or design from scratch) correct and---to the extent possible---efficient algorithms to solve a wide range of problems. They will understand how to judge whether or not a problem is likely to have to have an efficient algorithm.  They will also have a grasp of engineering issues arising in the implementation, adaptation, and application of algorithms.

Textbook:  T. Cormen, C. Leiserson, R. Rivest, & C. Stein, Introduction to Algorithms, 2nd Edition, The MIT Press,  Cambridge, Massachusetts, 2001.  (Also available from McGraw-Hill; either publisher's version is fine.)  A desk copy may be consulted in the CSE Dept office PL 354 (but cannot be taken away).  Another extra copy is available in Dr. Baird's office (PL514C), when he's there; but, again, it can't be taken away.

We follow the textbook closely.  Lectures may discuss only the most important topics in a section of the textbook, but students are expected to study the corresponding section completely. Unless stated otherwise, all material in covered sections is relevant to homework and tests.

Classroom lectures:  MWF 9:10-10:00 AM in Christmas-Saucon Hall, XS 303 (the Math Dept building).

Attendance and Quizes: Attendance in class is not required.  There are, however, Pop Quizes, and a missing quiz results in zero points.

Homework:  There are weekly written homework assignments, due normally on Friday morning, to be handed in as hardcopy at the start of the class. For part of each Friday's class, students are invited to present their solutions on the blackboard, for which they will receive 5 points credit (whether or not their solution is correct); this 'presentation' credit is added to your HW+Quiz score, up to a fixed maximum---and so can make up for points lost.

Exams:  There are two hour exams and a final 3-hour exam:  all are closed-book, in-class, written exams.   Exams are not repeated: if under extraordinary circumstances a student cannot take an exam, it is assigned the average grade of the other two exams.

Grading: 80% Exams (20% 1st hour exam, 20% 2nd hour exam, 40% final exam); 20% Homeworks+Quizzes+Presentations.

Instructor:  Prof. Henry Baird, hsb2@lehigh.edu; office:  Packard Lab 514C.   Office Hour:  Wednesdays 10-11 AM or by appointment.

Teaching Assistant: Nick Moukhine, nam6@lehigh.edu.  Office Hour:  Weds 1-2 PM.  Office: PL514B (temporarily, while his student desk is being renovated). 

BlackBoard site:  Design and Analysis of Algorithms (SP07), CSE-MATH-340-010-SP07.  We will use BlackBoard in this course to email announcements and distribute lecture notes, homeworks, grades, etc. Once you enroll, browse bb.lehigh.edu, login using your Univ. email id and Portal password, and you should see that you have access to this course. If you can't login, email the Instructor immediately.

Accommodations for Students with Disabilities:  If you have a disability for which you are or may be requesting accommodations, please contact both your instructor and the Office of Academic Support Services, University Center 212 (610-758-4152) as early as possible in the semester.  You must have documentation from the Academic Support Services office before accommodations can be granted.

Topics Covered (this list, and its order, is tentative):
Algorithm Basics:
   Definition, Properties (Ch. 1)
   Algorithm Performance Analysis:
         Insertion Sort & MergeSort (Ch. 2, Appendix A)
   Growth of Functions (Ch. 3)
   Recurrences (Ch. 4)
   Recursive Algs
Brute Force:
   Bubble Sort
   Sequential Search & String Matching
   Exhaustive Search
Divide & Conquer:
   QuickSort
   Heaps & Heapsort
   Binary Search, Tree Traversals
Greedy Algorithms;
   Kruskal’s Alg
   Dijkstra’s Alg
   Huffman Trees
P, NP, NP-completeness
   The Complexity Classes P & NP
   Polynomial-time reductions among problems
   NP-complete problems, P=NP?
Miscellaneous:
   Insertion Sort
   Depth-First & Breadth-First Search
   Topological Sort
   Sorting by Counting: Radix Sort, etc
   String Matching: Boyer-Moore, etc
   Hashing
Dynamic Programming: 
   Warshall’s & Floyd’s Algs

If you have any questions, ask the instructor: hsb2@lehigh.edu.