======================================================================
Course Syllabus (version: Sept 22, 2006)
CSI 3144, 4144, 4145
Competitive learning
======================================================================
======================================================================
Textbook and professors
======================================================================
Optional text:
Title: Programming Challenges
Authors: Steven Skiena and Miguel Revilla
Publisher: Springer-Verlag New York, Inc.
Publication place: New York, NY
Edition: 1
Publication date: May 12, 2003
ISBN: 0387001638
Names of professors: Drs. David Sturgill and Greg Hamerly
======================================================================
Course Overview and Goals
======================================================================
This three course sequence allows the student to learn and apply
algorithms, data structures and implementation techniques in a
problem-solving setting. Standard algorithms and data structures will
be reviewed and the student will have the opportunity to apply these
to new problems each week. After completing CSI 3144, the
successful student will demonstrate the following:
1. The student will be able to determine how to adapt and apply
standard algorithms to specific problems. For many of the problems
the standard solutions may not seem to immediately apply, so
students will learn to find connections between standard solutions
and specific problems.
2. The student will be able to read and understand a short problem
description, understand the associated technical and mathematical
language and anticipate special cases that are not obvious from
provided test cases.
3. The student will possess problem solving skills such as
estimating problem difficulty, identifying standard solutions,
time management, problem decomposition, implementation techniques,
designing tests and debugging.
4. The student will be able to implement the algorithms of the
course in an efficient manner. Efficient here means both
computationally efficient and time-efficient for the student
writing the solution.
5. The student will be able to work with a team of peers to solve
problems efficiently. This requires skill in communication,
cooperative implementation, resource allocation and negotiation.
The three courses will allow students to participate in this type of
activity multiple times, building on previous coursework. All of these
team-taught courses are offered concurrently. This gives more
advanced students the opportunity to assume leadership roles in team
problem-solving exercises. Students enrolled in any one of the
courses will be exposed to advanced topics in algorithms and data
structures. Students in CSI 3144 are expected to be able to implement
common algorithms and apply them to problems where the connection is
fairly obvious. Students in CSI 4144 and 4145 are expected to be able
to implement more sophisticated algorithms (such as disjoint sets,
convex hull, dynamic programming and memoization, input/output
formatting, number theory, network flow) and apply them to problems
where the connections are less obvious.
======================================================================
Course prerequisites
======================================================================
Prerequisites for Competitive Learning Level I:
- CSI 3334 (co-requisite) and Consent from instructor
Prerequisites for Competitive Learning Level II:
- Competitive Learning Level I and Consent from instructor
Prerequisites for Competitive Learning Level III:
- Competitive Learning Level II and Consent from instructor
======================================================================
Course structure
======================================================================
Each of the three courses is offered for 1-credit, consisting
of one 3-hour instructional lab session per week. In a typical
meeting, technical material such as implementation techniques,
algorithms or data structures will be presented by the instructors
during the first hour. In the remaining time, students will have the
opportunity to work individually and in teams of up to three to solve
problems related to the week's material.
Periodically each semester, the lecture component of the course is
omitted to give more time for problem solving. These meetings take
the form of a local problem-solving contest. They are important in
the development of problem solving skills in that they give students
the opportunity to think freely about what algorithms and other topics
are relevant to the problems at hand. They also give the students
practice in deciding where to concentrate their efforts.
======================================================================
Requirements, Evaluation, and Grading
======================================================================
Each week during the semester, students have several opportunities to
earn points toward their final grade. Points are awarded for each
programming problem the student successfully solves. During an
ordinary class meeting, students will have the opportunity to work on
two or three problems, chosen to exhibit ideas presented in the
lecture component. During the local contests, students will have the
opportunity to work on many more problems and to earn many more
points. Thus, the local contests are analogous to exams in a more
traditional course.
Grading components:
Weekly problem solving: 45%
First local contest: 15%
Second local contest: 15%
Final local contest: 25%
Grades assigned:
90% <= A <= 100%
80% <= B < 90%
70% <= C < 80%
60% <= D < 70%
0% <= F < 60%
======================================================================
Schedule of Topics
======================================================================
In order to cover a broad range of algorithms, data structures and
implementation techniques, course material is spread over two
semesters. Students may begin with CSI 3144 in either the spring or
the fall. For students enrolled in CSI 4144 or 4145, some lecture
material may be skipped in favor of more time for solving more
difficult problems. Likewise, students enrolled in CSI 3144
may skip some of the more advanced topics.
Fall Semester Schedule
Week 1
Introduction to Problem Solving
Students read and solve elementary problems from a variety of
areas
Week 2
Elementary Data Structures
The C++ Standard Template Library or Java Collections, including
sequence containers, iterators and basic template algorithms
Week 3
Sorted associative set and map data structures and their
implementations in C++ STL or Java Collections
Week 4
Input and output, with attention to robust techniques for
accommodating input formats and meeting specific output
requirements
Week 5
First Local Contest
Week 6
Graph representation and elementary algorithms, depth-first and
breadth-first traversal, loop detection, topological sort
Week 7
Intermediate graph algorithms, spanning trees, shortest path
Week 8
Introduction to computational geometry, basic representation,
vector operations, proximity tests
Week 9
Intermediate computational geometry, angle problems, convex
polygons, intersection problems
Week 10
Second Local Contest
Week 11
Advanced computational geometry, convex hull, closest pair of
points
Week 12
Introduction to dynamic programming, elementary algorithms,
memoization
Week 13
Dynamic programming, additional algorithms, theory and algorithm
development
Week 14
Final Local Contest
Spring Semester Schedule
Week 1
Introduction to Problem Solving
Students read and solve elementary problems from a variety of
areas
Week 2
Elementary Data Structures
The C++ Standard Template Library or Java Collections, including
sequence containers, iterators and basic template algorithms
Week 3
Sorted associative set and map data structures and their
implementations in C++ STL or Java Collections
Week 4
Strings and string algorithms, searching, sorting
Week 5
First Local Contest
Week 6
Sorting and applications to uniqueness testing, deleting
duplicates, selection, efficient searching, and set
intersection/union
Week 7
Arithmetic and algebra, big number implementation, prime
factorization
Week 8
Arithmetic and algebra, number theory, counting problems, modular
arithmetic
Week 9
Elementary Search Topics, recursive depth-first search,
combination and permutation generation, state space traversal
Week 10
Second Local Contest
Week 11
Intermediate Search Topics, search pruning and ordering
Week 12
Simulation problems
Week 13
Disjoint set data structure, path compression algorithm, and
applications
Week 14
Representing, counting, and computing on grid-oriented data;
rectangular, hexagonal, and triangular grids
Week 15
Final Local Contest
======================================================================
Additional requirements for graduate student credit
======================================================================
The following courses are being proposed as eligible for graduate
credit:
Competitive learning II, CSI 4144
Competitive learning III, CSI 4145
A graduate student who takes one of the competitive learning courses
is expected to do the following:
1. Solve 20% more problems to earn the same letter grade as an
undergraduate taking the same course.
2. Solve additional problems on selected advanced algorithmic
topics that are not given to undergraduates.
3. Design and implement solutions for course problems for
undergraduate students.
4. Prepare and lead the class in a lecture on a topic of
competitive learning