Honors Basic Algorithms, fall 2013
M 3:30-4:45, T, Th: 2-3:15 in room 109
Attendance in the Monday recitations is required.
Office: 330WWH. Office Hours: T, TH 3:15-4:15 and by appointment.
Final: Dec. 17, Room 109, 2:00 - 3:50.
An Introduction to Algorithms: their methods and madness,
by A.R. Siegel.
A NEW EDITION will be available soon. Details TBA
The entire book will be available at least one week before the start of the semester.
The projected cost will be about $55.00 for more than 1000 pages.
This page describes the honors version of Basic Algorithms, which is a
more demanding version of CSCI-UA.0310-002. The lectures, assignments,
recitations and tests are all part of the regular Basic Algorithms
CSCI-UA.0310-002. However, honors participants are required to complete a higher
percentage of the weekly assignments, and to
complete additional coursework.
This course covers the design and analysis of
combinatorial algorithms. The curriculum is concept-based and emphasizes the
art of problem-solving. The course features
weekly exercises designed to strengthen conceptual understanding and problem
solving skills. Students are presumed to have adequate programming skills and
to have a solid understanding of basic data structures and their implementation
in the programming languages of their choice. Although some mathematical
sophistication would be helpful for this course, the necessary mathematics is
contained within the curriculum.
Because of the emphasis on problem solving, everyone is
required to attend the Monday recitation sessions, where students will
practice applying sophisticated concepts to solve challenging exercises.
Algorithmic Design Paradigms
The Greedy Method
Sorting- and Selection-based processing
Algorithm Redesign and Adaptation
The Analysis of Algorithmic Performance
The Recursion Tree Solution Method
Managing Data for Efficient Processing
Lists, Stacks, Queues, Priority Queues, Trees and
Tarjan's Categorization of Data
Search Trees and their Enhancement
Sorting, Selection, and Hashing
Selected Representative Algorithms/problems
Biconnected Components and Strong Components
Representative styles of Dynamic Programming and their applications
Standard Sorting and Selection Algorithms
Selected topics in Hashing
Minimum Spanning Trees
Shortest Path Problems
There will be approximately 11 written homework assignments
that have, on average, about 12 exercises each. Perhaps one-third
to one-half of these problems will be extremely challenging. That is,
the necessary concepts will have already been taught, but a good deal
of thought will be needed to figure out how to apply these techniques
to solve the more challenging exercises.
- Students are not required to solve even half of the more difficult
but they are expected to write down what ideas/methods they used, and where
their solution method broke down.
- Students are also expected to compare their own answers with the
solution handouts to see what concepts and techniques were overlooked.
Because more than a third
of the course is embedded in the exercises, students are expected to study the
answers as a vehicle for mastering the material.
- Homework will receive two grades: overall performance, and quality of
effort. Incorrect and even fragmentary incorrect answers can receive full
credit for the QoE grade, which will have a weighting that is comparable
to the correctness grade for each assignment.
Course Grading Policy
19% Midterm Exam
8% Overall homework performance grade
8% Overall QoE homework grade
47% Final Exam Date and time TBD
8% Classroom participation
10% Additional coursework