Lehigh University

•  Baird Home
•  Research
•  Courses
•  Students
•  Prof'l Activities
•  Conferences
•  Publications
•  Talks
•  Patents
•  Awards
•  Miscellaneous
•  Vita (PDF)


Henry S. Baird    Spring 2006 Course

Design & Analysis of Algorithms

Algorithms are broadly applicable methods for solving information- processing problems fully automatically and as efficiently as possible. They 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---with proofs of their correctness and analysis of their runtime and memory requirements. Strategies for designing algorithms---e.g. recursion, divide-and-conquer, greediness---are introduced. Limits on algorithm efficiency are explored through elementary NP-completeness theory.

Prerequisites:  Math 22 and CSE/Math 261 (or close equivalents).

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).

It 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 also have a grasp of engineering issues arising in the implementation and application of algorithms.

Textbook:  Anany Levitin, Introduction to the Design and Analysis of Algorithms, Addison-Wesley (2003) (ISBN 0-201-74395-7).

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.

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 credit (whether or not their solution is correct).

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

Exams:  There are two hour exams and a final 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:  Tuesdays 1-2 PM or by appointment.

Teaching Assistant: Fu Zhou, fuz204@lehigh.edu; office: desk #14 on 6th floor, Packard Lab.  Office hour:  Thursdays 10:45-11:45 AM or by appointment.

BlackBoard site:  Design and Analysis of Algorithms (SP06), CSE-340-010-SP06.  We will use BlackBoard in this course to distribute lecture notes, homeworks, grades, etc. Browse bb.lehigh.edu, login using your Univ. email id and Portal password, and you should see that you have access to this course.

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 (with textbook section nos.):
Algorithm Basics:
    Definition, Properties (1.1, 1.2)

   Algorithm Performance Analysis (2.1)
   Asymptotic Analysis, Efficiency Classes (2.2)
   Non-recursive Algs: MaxElement, UniqueElement ( 2.3)
        Summations, Summation formulae (Appendix A)
   Recursive Algs (2.4)
        Recurrence relations (Appendix A)
Brute Force:
   Selection Sort, Bubble Sort (3.1)
   Sequential Search & String Matching (3.2)
   Closest-Pair & Convex Hull (3.3)
   Exhaustive Search (3.4)
Divide & Conquer I:
   Mergesort, QuickSort (4.0, 4.1, 4.2)
   Heaps & Heapsort (6.4)
Greedy Algorithms:
   Prim’s Alg (9,1)
   Kruskal’s Alg (9.2)
   Dijkstra’s Alg (9.3)
   Huffman Trees (9.4)
P, NP, NP-completeness (10.3)
   The Complexity Classes P & NP
   Polynomial-time reductions among problems
   NP-complete problems, P=NP?
Divide & Conquer II:
   Binary Search, Tree traversals (4.3, 4.4)
   Closest-Pair & Convex Hull (4.6)
Decrease & Conquer:
   Insertion Sort (5.1)
   Depth-First & Breadth-First Search (5.2)
   Topological Sort (5.3)
Space/Time Tradeoffs:

   Sorting by Counting: Radix Sort, etc (7.1)
   String Matching: Boyer-Moore, etc (7.2)
   Hashing (7.3)
   B-Trees (or AVL-trees) (7.4 (or 6.3))
Dynamic Programming: (if there's time)
   Warshall’s & Floyd’s Algs (8.2)

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


© 2003 P.C. Rossin College of Engineering & Applied Science
Computer Science & Engineering, Packard Laboratory, Lehigh University, Bethlehem PA 18015