Henry S. Baird Spring 2015 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, moves significantly faster, and assumes strong Math skills; 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 (so that, 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.
iteration, recursion, divide-and-conquer,
greediness, dynamic programming---are stressed. Limits on algorithm
efficiency are
explored using 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).
(You do not need to buy the companion Java CD-ROM since there will be no programming assignments.) If there are no copies available for sale in the Univ. bookstore, consider other sources:
- Amazon.com: (a) Hardcover new, $76 (as fast as two-day delivery); (b) Hardcover used, $59-$70 (2-7 day delivery); (c) Kindle edition, $72 (autodelivered wirelessly); (d) Paperback new or used, $26-$40.
- Buy or borrow from a former CSE/Math 340 student: ask the instructor for a list of students to ask.
A "desk copy"
of this textbook 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 PL 380 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, in Packard Laboratory 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 (software) 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 "Midterm" exams (in class),
probably taking place Friday February 20 and Friday April 3; 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, please---miss any exam, please give the instructor as much notice in advance as you can, and he/she 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 will be three graders, each responsible for grading homeworks for about 1/3 of the students:
To
ask questions about homework problems or grades, contact your grader by
email; if you wish, he will arrange to meet you in person. He is also willing to help explain ideas in the course.
Course
Site:
CSE-340-Math-340-SP15 Design
& Analysis of Algorithms.
We'll use the University's on-line
CourseSite system to email
announcements & to distribute lecture
notes, homeworks, solution sets, grades, etc. 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
Sorting:
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)
Heuristics:
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.