Lehigh University

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


Henry S. Baird    Spring 2014 Course

Design & Analysis of Algorithms

CSE/Math 340     3 credits

CRNs:  11264 (CSE);  17771 (Math)

Note to all students:  this is an undergraduate version of the graduate-level Algorithms course CSE/Math 441, which covers more topics and is significantly harder; no student may take both of these courses for credit.
Note to undergraduate students:  this is a required (core) course for several undergraduate degree programs: B.S. in CS (in RCEAS); B.A. in CS (in CAS); and the B.S. in Computer Science & Business (in RCEAS & CBE).

Algorithms are methods for solving information processing problems. Every algorithm must be automatable (for example, a computer can run it), and provably correct (that is, it must find the right answer for every instance of the problem it is given). We also often want it to run as fast as possible, and use as little memory as possible, even on huge instances. Fast algorithms for hard, practically important problems are among the key discoveries 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 the instructor). To review your Discrete Structures background, look at the textbook's Appendix sections A.1-2, B.1-3,  C.1., & D.1.

Course objective:  On completing this course, students will be able to design algorithms and apply knowledge of complexity; and, more generally, to apply mathematics to CS problems. They 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) provably 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 new problem is likely to have an efficient algorithm.  They will also have a grasp of basic engineering issues arising in the implementation, adaptation, and application of algorithms.

Textbook:  T. Cormen, C. Leiserson, R. Rivest, & C. Stein, Introduction to Algorithms, 3rd Edition, The MIT Press,  Cambridge, Massachusetts, 2009 (ISBN-13 978-0-262-03384-8 hardcover, or 978-0-262-53305-8 paperback).  If there are no copies available in the Univ. bookstore, email me immediately. You do not need to buy the companion Java CD-ROM.  A desk copy may be consulted in the CSE Dept office PL 354 when the office is open (but this copy cannot be taken away). Another extra copy is available in Dr. Baird's office PL380 when he's there (but, again, it can't be taken away).

We'll 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 assigned reading in the textbook completely. Unless stated otherwise, all material in assigned textbook sections is relevant to homework and tests.

Lectures Time and Place:  MonWedFri 11:10 AM - 12:00 noon, Packard Laboratory room 416.

Attendance and Quizes:   Attendance at lectures is not required. There may be, 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. There are no programming assignments.  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 the HW+Quiz score, up to a fixed maximum---and so can make up for points lost.

Exams:   There are two one-hour exams (in class), on Friday February 14, and again Monday March 31; and one three-hour final exam (during end-of-semester exam period):  these are all closed-book, written exams. Exams are never repeated: if under extraordinary circumstances a student cannot take an exam, it will be assigned a grade which is the average of the other two exams' grades.  If you anticipate that you must---for excellent reasons---miss any of these exams, please give me as much notice in advance as you can, and I will try to arrange for you to take the exam (or some roughly equivalent version of it) before the scheduled exam date.

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

Instructor:   Henry Baird, Prof., CSE Dept, hsb2@lehigh.edu. Office:  Packard Lab 380.   Office Hours:  Wednesdays 12:10-1:00 PM, or by appointment. He will grade all the exams.

Graders (for homeworks only): there are two graders, each responsible for grading homeworks for half the students:
Tyler Holcombe facepic

 Tyler Holcombe


 He grades students with last names:  A-M  

Nick Roessler facepic

 Nick Roessler


 He grades students with last names:  N-Z  

To ask questions about homework problems or grades, contact your grader by email; if you wish, he will arrange to meet you in person.

Course Site:   CSE-340-Math-340-SP14 Design & Analysis of Algorithms (Not Yet Posted). We will use the University's on-line CourseSite system to email announcements & to distribute lecture notes, homeworks, solution sets, grades, etc. Once you enrolled in the course, go ahead and browse coursesite.lehigh.edu, login using your Lehigh Id and password, and you should see that you have access to this course. If you can't login, email the instructor immediately.

Topics Covered (probable; chapters in textbook):
Algorithm Basics:

   Definitions, Properties (Ch. 1)
   Algorithm Performance Analysis (Ch. 2)
       Insertion Sort & MergeSort

   Growth of Functions:  O(.)-notation etc (Ch. 3)
   Divide and Conquer (Ch, 4)
       Recurrences & their Solution

   Heapsort, Priority Queues (Ch. 6)
   Quicksort (Ch. 7)
   Lower Bounds, Sorting in Linear Time (Ch. 8)
Data Structures:
   Stacks, queues, lists, graphs, trees (Ch. 10; review)
   Disjoint-Sets Union/Find (Ch. 21)
Graph Algorithms:
   Bread-first & Depth-first Search (Ch. 22)
       Topological Sort
   Shortest Paths:  Bellman-Ford, Dijkstra (Ch. 24)
Greedy Algorithms:
Huffman Trees (Ch. 16)
   Minimum Spanning Trees:  Kruskal (Ch. 23)
Dynamic Programming:

   All-Pairs Shortest Paths:  Floyd-Warshall (Ch. 25)
   Matrix-chain multiplication (Ch. 15)
   String Edit Distance (Section 15.4)
P, NP, NP-completeness:
   The Complexity Classes P & NP (Ch. 34)
       Polynomial-time Reductions among Problems
       NP-complete Problems; P=NP?
   Approximation Algorithms (Ch. 35)
Coping with NP-completeness
    Algorithm Engineering
Miscellaneous (if time permits):
   String Matching:  KMP, Rabin-Karp (Ch. 32)
   Computational Geometry:  Convex Hull (Section 33.3)
   Polynomials & the Fast Fourier Transform (Ch. 30)

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

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.

Lehigh University endorses The Principles of Our Equitable Community (http://www4.lehigh.edu/diversity/principles). We expect each member of this class to acknowledge and practice these Principles. Respect for each other and for differing viewpoints is a vital component of the learning environment inside and outside the classroom.


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