Computer Science Department

Deborah Joseph
Associate Professor
Computer Science Department
University of Wisconsin - Madison

Research

• Computational Biology - Design and Analysis of Algorithms

My research in computational biology is focussed on computational tools for genome sequencing and analysis. This includes the development of dynamic data structures and algorithms for fragment assembly, the development of algorithmic techniques for identifying repetitive sequences, and the utilization of graph theoretic methods for rapid homology detection in the analysis of anonymous sequences.

• Complexity Theory

Nearly a half century of research has yielded a plethora of complexity classes, and yet major questions remain open: Does P = NP? Does P = Pspace? My research investigates the structural properties of sets in these classes and proof techniques for separating and collapsing complexity classes.

Courses Taught

• CS 520: Introduction to Theoretical Computer Science

  CS 520 presents a survey of the basic concepts of theory, including context-free and context-sensitive languages, regular sets, finite and pushdown automata, Turing machines, undecidable problems, complexity with respect to time and space, NP-completeness, and reducibilities. Prereq: CS 367, Math 222, and CS 240, or consent of instructor.

• CS 577: Introduction to Algorithms

  CS 577 presents a survey of important and useful algorithms for sorting, searching, pattern-matching, graph manipulation, geometry, and cryptography. Paradigms for algorithm design. Techniques for efficient implementation. Prereq: CS 367, Math 222, and CS 240, or consent of instructor.

• CS 810: Models and Formalisms for Computation

  Models of computation, Turing machines, recursive functions, Church's thesis, undecidable problems, degrees of unsolvability. Denotational semantics, logic of programs. Applications to automata, formal languages, program verification, programming languages, and complexity. Prereq: CS 520.

Undergraduate Advising - Freshman and Sophomore advising for CS students

Are you a freshman or sophomore wanting to earn a liberal arts degree? If so, the L&S Advising Center is the place for you! Featuring a mix of faculty and academic staff advisors, we are the primary source for academic advising for students who want to choose a major within Letters & Science. In addition to pre-major advising we also help transfer students. More information can be found on the LSAC website: www.lssaa.wisc.edu/lsac

 

Undergraduate Honors in Computer Science

I am the Computer Science department's undergraduate honors advisor.

Students enrolled in the honors program may elect to take any CS course numbered 300-699 for Honors credit. But to do so you need my permission (as departmental honors advisor) and the permission of the course instructor. In addition, any course numbered 700 or above carries Honors credit for undergraduate students.

Junior and Senior cs majors should consider the Computer Sciences Major with Honors. Here are the requirements:

1. Minimum GPA of 3.5, computed on all courses used for the major.
2. A 2-semester senior thesis or project (CS 681- 682) involving at least 6 credits of work. (The student will be responsible for obtaining a thesis/project advisor. The thesis or project must be approved by both the thesis/project advisor and the Departmental Honors Advisor. A thesis or project must be filed with the CS Department before a final (passing) grade for CS 682 can be awarded.)
3. 3 of the elective credits counted in Requirement (7) for the Computer Sciences Major must be obtained at the 700 or 800 level, with a grade of B or better. (These courses must be approved by the Departmental Honors Advisor and should be selected to complement the student's degree plan and to aid in the student's senior thesis/project.)

If you would like more information about the honors program in computer science please send me email: joseph@cs.wisc.edu. You can find an application form for the L&S Honors in the Major progam at the L&S Honors website.

Additional Interests

I live on an 80 acre farm in the driftless region of SW Wisconsin. Much of our land is tall grass prairie and oak savanna. I share the farm with my husband Paul Young and our five Labrador Retrievers who compete in agility, obedience, hunting, and tracking.