====================================================================== 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