CSE 202, Algorithms and Data Structures, Fall, 2004

Prof. Russell Impagliazzo

Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 92093-0114

Office: 4248 Computer Science and Engineering Building
Phone: (858) 534-1332; Fax: (858) 534-7029;
Email: russell@cs.ucsd.edu

Russell's Office Hours: Mon, Thurs, 2-4, Room 4248 or B 225 if well-attended

Supplementary Text by Jeff Edmonds

Announcements:

Sashka will have office hours 10-11 on Wed.
Final Exam FAQ:
1. The problem is to decide whether there EXISTS a palindrome that the automaton accepts. (I think I should have used the plural palindromes as the last word, not the singular palindrome.)
Logical phrasing: Does UCSD CSE accept any MS students to the Ph.D. program? Yes, it accepted Ted, who was an MS student.
Not, `` No, it rejects some MS students.''
2. Reasonable run times. It has been pointed out that the instructions promised ball-park estimates for good runtimes for the various problems. Here are some not bad time complexities:

Palindrome path: O(|V|^2||\Sigma|)
Energy contracts: O(n \log n)
d-regular subgraph: O(d |V| |E|)
Approximate clustering: Algorithms time is less important than approximation ratio. My current best algorithm is in fact pretty trivial, but the analysis isn't.

Does the automaton accept any palindromes? Yes, it accepts 0110, which is a palindrome. Or, no, there are no palindromes at all accepted by the machine.
Neil Jones CSE 202 web page for F02. Has some good lecture notes.
Course Handouts