Course web page
The web page for CS 383 is located at
http://www.cs.bc.edu/~hjiang/algorithms.
You should check this page regularly for updates,
including supplementary materials and homework assignments.
This course focuses on the time and memory requirements of the
algorithms (procedures) that are embodied in computer programs.
We will discuss both analysis of existing algorithms
as well as design of new algorithms with a view toward
achieving efficient computational procedures.
Course topics include divide and conquer design, fundamental data
structures, asymptotic notation, analysis of recurrence relations,
greedy algorithms, search, and dynamic programming.
Textbook
S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms, McGrawHill, 2008.
Reference Books
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
Introduction to Algorithms (3rd Edition), The MIT Press, 2009. (available in the electronic library at BC)
Prerequisites / Recommended background
The prerequisites for CS383 are programming
and data structures at the level of CS101 and CS102 (including a good grasp
of recursion), and discrete mathematics at the level of CS 245 (including
familiarity with basic proof techniques and mathematical induction).
Additional background in mathematics and computer science would help
but is not required.
If you have any questions about prerequisites, please contact me.
Grading
The course grade will be based on homework and exams.

Homework (30%)
Homework will be due in most weeks during the semester.
HW should be submitted
in hardcopy by the beginning of class on the due date. Source code for
any programs should be included in the hardcopy submission, and should
also be emailed to me and the TA before the submission deadline.
Late homework submissions will receive no credit except in unusual
circumstances, at the discretion of the instructor.
In order to be eligible to pass the course, you must complete and submit
at least 2 out of every 3 homework assignments.

Midterm Exams (30%)
Two inclass midterm exams will be given.
See the rough schedule above for exam dates. Note that one of the exams will be
held immediately prior to Spring Vacation. No makeup exams will
be given, so plan ahead..

Final Exam (30%)

Class Participation (10%)
Academic Honesty
You must individually design and write your own solutions for all assignments. Furthermore,
you should explicitly acknowledge any sources of ideas that are not your own; this includes
other people, books, web pages, etc. Behavior that is not in the spirit of these guidelines is
considered to be academically dishonest. Please also see the university's statement on academic
integrity. If you're unsure about what constitutes academic dishonesty in a particular
situation, ask me before proceeding further.
Course Material
Week 1
 Topics: Big O notation, proof of big O relations using
the definition, limit method and substitution method,
the concept of algorithm complexity, review of
program construction using iteration and loop invariant,
program construction with recursion.
 Reading: Text book chapter 0.
 Sample code and notes: note.txt.
Week 2
 Topics: Algorithms on numbers
 Reading: Text book chapter 1.
 Sample code and notes: notes.txt.
Week 35
 Topics: Divide and Conquer, decompositions of graphs
 Reading: Text book chapter 2, 3.
 Notes: notes.
Week 6
 Topics: Backtracking and exhaustive search
 Notes: notes.
Week 7,9
 Topics: Graph breadth first search, Dijkstra's shortest
path algorith, BellmanFord's algorithm,
shortest path on a DAG
 Reading: textbook chapter 4
Week 10,12
 Topics: Dynamic programming
 problems discussed: shortest path on a DAG,
longest increasing subsequence,
editting distance,
knapsack problem (2 versions),
robot's path, ways to go up stairs
 Applications: Stereo,
seam carving for image resizing
 Notes: note.txt
 Reading: textbook chapter 6.
Week 13,14
 Topics: Greedy algorithms (MST, Scheduling problems, Huffman coding)
 Reading: textbook chapter 5.
Week 1516
Week 17
 Topics: Algorithms in Computer Vision and Review