CS499: Algorithmic Problem Solving (Fall 2006)

Most recent message posted: 11/30

Administrativa

Course Overview, Prerequisites, Syllabus, Textbook, Grading

This course aims to draw a connection between algorithms, theory, and problems in the real world. The goal is for students to develop an understanding of the core algorithmic challenges in real-world problems, learn which algorithms to apply, and write computer programs solving the problems.

The algorithms material will be drawn roughly from a standard undergraduate algorithms course (recursion, strings, basic graph algorithms, dynamic programming, geometric algorithms, logic). The focus will not be on proving correctness or detailed runtime analysis. Rather, students will use those algorithmic techniques to solve toy versions of real-world problems, and be required to draw connections of theory to the real world themselves. An important component will be implementing efficient solutions to the real-world problems, and verifying their correctness on given data sets.

The course is intended as a technical elective. It requires basic knowledge of algorithms, including some of the algorithmic techniques discussed below. The discussion of the underlying mathematics will be necessarily brief, as the focus is on applications. Having taken CSCI271 and CSCI303 successfully should certainly be sufficient, though talented younger students may also succeed in the course.

The textbook, used mostly for reference, is

The (rough) syllabus for the course is as follows. Topics may be added or removed depending on available time:

  1. Basic Programming Tasks (ca 2 weeks): string processing, simple mathematics, reading and writing data, basic data structures.
  2. Graph Algorithms (ca 3 weeks): shortest paths, topological sort, spanning trees, graph search, (networks flows, time permitting). Focus on real-world applications
  3. Paradigms (ca 2 weeks): recursion, exhaustive search, how to implement them.
  4. Dynamic Programming (ca 3 weeks)
  5. Geometric Algorithms (ca 3 weeks): line intersections, angles, convex hull, polygon area
  6. Logic (ca 1 week): inference and deduction

The course will consist of one or two lectures per week, and supervised lab sessions during which students implement algorithmic solutions to real-world applications. The lectures focus on a recap and explanation of the basic material and example applications.

The grading will be based, with roughly equal weights on homework programming assignments, other homework assignments, and programming challenges in class.

Academic Integrity, Collaboration

All students are expected to maintain the utmost level of academic integrity. Any attempts to cheat will lead to appropriate sanctions. Please consult the USC Student Conduct Code (general overview) for details on what is and is not appropriate, and for the possible consequences of infractions.

Messages