University of California at Berkeley
Dept. of Electrical Engineering & Computer Science

CS 198-23 / CS 98-23
Applications of Algorithms

Fall Semester 2010



Practical information

Lectures: 275 Soda Hall, Wednesday 6-8pm (A second section on Monday can be opened up if there is demand) .

CCN: CS 98 - 27256
CS 198 - 27259.

Grading and Units: P/NP, 2 Units

Instructors:

Swapnil Ralhan
Email: swap25 AT berkeley DOT edu
Veer Bawa
Email: vbawa AT berkeley DOT edu
Christos Papadimitriou
Email: christos AT cs DOT berkeley DOT edu
Phone: (510)642-1559

Attendance: Attendance is mandatory, and in accordance with decal course guidelines, only 2 unexcused absences are allowed.

Back to top

Course description: This is a lab based course that accompanies CS 170. While CS 170 explores the concepts and basic techniques in the design and analysis of algorithms, this course provides practical experience related to each concept. The class will closely follow the course material taught in CS 170, and will be a 2 hour lab session. The first half hour will be a discussion of the week's topics in relation to practical considerations during implementation, as well as application of the algorithms to different real life problems.The remainder of the class will be devoted to solving 3-5 problems of varying difficulty. There will be three types of questions: Interview Questions, CS 170 HW questions, and Competition Questions (from the likes of Google CodeJam and TopCoder). The last 15 minutes will be a discussion of the ideas needed to solve the problems. In the last two classes students will work on a project either involving applying multiple algorithm techniques in an open source setting or solving an NP-hard problem approximately (such as TopCoder Marathon Questions).

Prerequisites: CS 170 or Concurrent enrollment in CS 170; Programming experience at the level of CS 61B

Assignments: Each week an assignment will be released(on the Friday before the class, after the CS 170 HW is due). A Forum will be set up to solve the interview questions. For the programming questions, the grading will be done online as follows: for each problem there will be a Small and a Large Input set. For each input set, on downloading a timer will start. You must run your program on the input set and submit the output and the program used before the time expires. You can use as many tries as you want. These problems can be done in class as well.

Project: The last two homeworks will be a group project, details to follow. For the project, there will be multiple input sets, and the outputs for all of them will be evaluated.

Programming Languages: Any programming language for which the compiler/interpreter is freely available can be used for the programming assignments. However, the instructors can provide assistance with only C/C++, Java, Python, Ruby, PHP, Javascript.

Back to top

Updates and Announcements

Back to top

Presentations/Problems