Requirements for the Major
Honors Program and Honors in the Major
Natural Science Credit
Department Guidebook
Courses
Room 5355, 1210 West Dayton Street, Madison, WI 53706; 608/262-1204; www.cs.wisc.edu
Professors Bach, Banerjee, Barford, Cai, DeWitt, Dyer, Ferris, Fischer, Hill, Horwitz, Livny, Meyer, Miller, Naughton, Ramakrishnan, Reps, Ron, Shavlik, Sohi, Solomon, Vernon, Wood, Wright; Associate Professors A. Arpaci-Dusseau, R. Arpaci-Dusseau, Gleicher, Jha, Joseph; Assistant Professors Akella, Banerjee, Barford, Chawla, Doan, Estan, Liblit, Sankaralingam, Van Melkebeek, Zhang, Zhu
Undergraduate advisor in the major: See any member of the department's undergraduate advising committee. Office hours of committee members are posted outside the department office and at www.cs.wisc.edu/ugac/ ugrad.advisors.html.
Faculty diversity liaison: Miron Livny, miron@cs.wisc.edu
To be accepted into the computer sciences major, students must fulfill two requirements:
1. Complete Comp Sci 240, Comp Sci 302, and Comp Sci 367 (either here at UW-Madison, or via AP credit, or via transfer credit). Note that completing Comp Sci 367 alone counts as completing both Comp Sci 302 and Comp Sci 367.
2. Have a GPA of 2.6 or higher in an admissible sequence of Comp Sci courses taken here at UW-Madison. The rules that define an admissible sequence are:
a. The sequence must contain 2, or 3, or 4 courses.
b. Each of Comp Sci 240, 302, and 367 must be included in the sequence, provided that it was taken here at UW-Madison.
c. None of Comp Sci 298, 310, 368, 371, or 550 can be included.
d. Every other Comp Sci course taken at UW may be included or excluded at the student's discretion, provided that (a) above is satisfied, and provided that: if the student chooses to exclude from the sequence a certain Comp Sci course taken in a given semester, he or she must exclude from the sequence all Comp Sci courses (other than 302, 240, 367) that were taken in later semesters.
Note: If a student takes the same course twice, only the first grade is used in the GPA calculation, unless that grade is an F, in which case both grades are used.
Students who have difficulty interpreting or meeting the requirements for the computer sciences major may meet with a member of the department's Undergraduate Advising Committee. Office hours for members of this committee are posted at www.cs.wisc.edu/ugac/advisors.html. No appointment is required.
After completing the acceptance requirements, students should meet with a member of the department's Undergraduate Advising Committee to work out a course plan and file a Declaration of Major form. They should bring an up-to-date transcript to the meeting, which will be added to their file. Students may also wish to download the course plan form at www.cs.wisc.edu/ugac/courseplanform.pdf and fill it in before the meeting. This form allows students to list courses they intend to take for the major, and when they intend to take them. The course plan can be changed later, as many times as needed, with the approval of a member of the advising committee. Students who are unsure about which courses to take, or when to take them, can raise those issues during the meeting with an advisor. For subsequent meetings with an advisor, students can pick up their folder in Room 5351 of the Computer Sciences Building. Maintaining an up-to-date course plan is the student's responsibility.
In addition to all college requirements, students majoring in computer sciences must complete the following courses:
(1) Basic Comp Sci Courses: Comp Sci 240, 302, 367, 352, 354
(2a) Basic Calculus: Math 221 and 222.
(2b) Additional Mathematics Courses: Two mathematical courses that presuppose basic calculus. The recommended courses are Math 331 Introduction to Probability and Statistics and Comp Sci 416 Introduction to Scientific Computing. Note that some specific areas of computer sciences may recommend other choices.
Other courses that may be used to fulfill this requirement include: Comp Sci 412, 513, 514, 525, 526; Math 234, 319, 320, 321, 322, 340, 375, 419, 431, 443, 461, 475, 521, 541, 542, 567, 571; Stat 309, 310, 311, 312. For the purposes of this requirement, Math 375 may not be combined with Math 234, 320, or 340; and Comp Sci 412 may not be combined with Comp Sci 416.
(3) Advanced Comp Sci Courses: a total of six Comp Sci courses:
(3a) One course chosen from Comp Sci 577 (recommended) or Comp Sci 520. Students who intend to do graduate work in computer science should take both Comp Sci 577 and Comp Sci 520.
(3b) Two courses chosen from Comp Sci 536, 537, 538, 552, 564, or 640. Comp Sci 536 and 538 may not both be used to satisfy requirement (3b).
(3c) One course chosen from Comp Sci 412, 416, 425, 513, 514, 515, 525, 540, 547, or 559. If either Comp Sci 412 or Comp Sci 416 is used to satisfy requirement (2b), neither course may be used to satisfy requirement (3c).
(3d) The remaining two courses are considered general electives, and should be chosen in consultation with a member of the Undergraduate Advising Committee. Each elective must be a computer sciences course numbered 400 or higher and carrying a minimum of 3 credits.
Comp Sci 550 may not be used to fulfill this requirement, and Comp Sci 638 and 691-699 may be used only in exceptional cases. A description of the material studied must be included with the course plan. Note that Comp Sci 691 may not be used by itself; it must be followed by Comp Sci 692.
All students must fulfill the L&S requirement of 15 credits of upper level work in the major completed in residence. All computer sciences courses numbered 400 or above count toward this requirement.
Students should be aware that some of the courses listed above have prerequisite courses not specifically required for the major. It is the student's responsibility to meet prerequisite requirements, but courses taken to meet such requirements do not necessarily count toward the major.
Students enrolled in the honors program may elect to take computer sciences courses for honors credit. With the permission of the course instructor and the department honors advisor, any course numbered 300-699 may be taken for honors credit. In addition, any course numbered 700 or above carries honors credit for undergraduate students.
Here are the requirements for obtaining a Computer Sciences Major with Honors:
(1) Minimum GPA of 3.5, computed on all courses used for the major, and an overall GPA of at least 3.3 in all courses taken at UW-Madison at the time of graduation.
(2) A two-semester senior thesis or project (Comp Sci 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 department honors advisor. A thesis or project must be filed with the computer sciences department before a final [passing] grade for Comp Sci 682 can be awarded.)
(3) One of the courses counted for requirement (3d) for the computer sciences major must be taken at the 700 or 800 level, with a grade of B or better. (These courses must be approved by the department honors advisor and should be selected to complement the student's degree plan and to aid in the student's senior thesis/project.)
Please note that a minimum cumulative grade point average of 3.3 is required to earn any honors degree in the College of Letters and Science. This minimum cumulative GPA may be distinct from the minimum GPA requirement for courses in the major.
All Comp Sci courses except 550 carry natural sciences credit. Comp Sci 550 carries social studies credit.
A Guidebook containing up-to-date information about courses and degree requirements is available from the department and at its Web site.
All classes listed in the course descriptions section will be offered regularly unless otherwise noted. Please check with the department office for specific information.
240 Introduction to Discrete Mathematics. (Crosslisted with Math) I, II; 3 cr (N-I). Basic concepts of logic, sets, partial order and other relations, and functions. Fundamental principles of counting. Basic algebraic structures: modulo arithmetic, group, ring, and field structures, Boolean algebra. Introduction to graph theory: trees, depth first search, matching, max-flow min-cut, and other optimization algorithms. Applications. P: Math 221.
252 Introduction to Computer Engineering. (Crosslisted with ECE) I, II; 2 cr (E). Logic components built with transistors, rudimentary Boolean algebra, basic combinational logic design, basic synchronous sequential logic design, basic computer organization and design, introductory machine- and assembly-language programming. P: Open to Fr.
298 Directed Study in Computer Science. I, II; 1-3 cr (E). Undergraduate directed study in computer sciences. P: Open to Fr.
302 Introduction to Programming. I, II, SS; 3 cr (r-N-I). Instruction and experience in the use of an object-oriented programming language. Program design; development of good programming style; preparation for other computer science courses. P: Problem solving skills such as those acquired in a stats, logic, or adv HS algebra crse, or cons inst. Open to Fr. Stdts who take both Comp Sci 110 & 302 will receive a total of 3 cr for the two crses.
310 Problem Solving Using Computers. I, II; 3 cr (E). Gives engineering students an introduction to computer and analytical skills to use in their subsequent course work and professional development. Discusses several methods of using computers to solve problems, including elementary Fortran and C programming techniques, the use of spreadsheets, symbolic manipulation languages, and software packages. Techniques will be illustrated using sample problems drawn from elementary engineering. Emphasis on introduction of algorithms with the use of specific tools to illustrate the methods. P: Math 222.
352 Digital System Fundamentals. (Crosslisted with ECE) I, II, SS; 3 cr (r-P-I). Logic components, Boolean algebra, combinational logic analysis and synthesis, synchronous and asynchronous sequential logic analysis and design, digital subsystems, computer organization and design. P: Comp Sci/ECE 252.
354 Machine Organization and Programming. (Crosslisted with ECE) I, II; 3 cr (r-N-I). An introduction to computer organization using assembly and machine language. Number representation, computer arithmetic, instruction sets, I/O interrupts, and programming interrupts. Projects involve detailed study and use of a specific computer hardware and software system. P: Comp Sci 302 & ECE/Comp Sci 252.
367 Introduction to Data Structures. I, II, SS; 3 cr (r-N-I). Study of data structures (including stacks, queues, trees, graphs, and hash tables) and their applications. Development, implementation, and analysis of efficient data structures and algorithms (including sorting and searching). Experience in use of an object-oriented programming language. P: Comp Sci 302 or cons inst. Stdts are strongly encouraged to take Comp Sci 367 within two semesters of having taken Comp Sci 302.
368 Learning a New Programming Language. I, II; 1 cr (I). This course is for students who are familiar with at least one programming language, and are interested in learning a new language. Different sections will teach different languages. P: CS 302 or cons inst. Exper with data struct req (e.g. 5 wks of CS 367 or equiv). Stdts rec cr for lang once & not rec cr for same lang in CS 302 & 368 or 367 & 368. Open to Fr.
371 Technology of Computer-Based Business Systems. (Crosslisted with Info Sys) I or II or SS; 3 cr (S-I). Overview of computers, their attendant technology, and the implications of this technology for large-scale, computer-based information systems. Topics include hardware, system software, program development, files and data communications. P: Comp Sci 302 or cons inst.
412 Introduction to Numerical Methods. I, II, SS; 3 cr (N-I). Interpolation, solution of linear and nonlinear systems of equations, approximate integration and differentiation, numerical solution of ordinary differential equations. P: Math 222, either Comp Sci 240 or Math 234, Comp Sci 302 or equiv, & knowledge of matrix algebra.
416 Foundations of Scientific Computing. I, II; 3 cr (I). Basic techniques for scientific computing, including fundamentals of linear algebra and numerical linear algebra, rootfinding, floating-point arithmetic, interpolations and splines, linear and quadratic programming. P: Math 222 & Comp Sci 240; or Math 234 & Comp Sci 302.
425 Introduction to Combinatorial Optimization. (Crosslisted with ISyE, Math) II; 3 cr (P-I). Exact and heuristic methods for key combinatorial optimization problems such as: shortest path, maximum flow problems, and the traveling salesman problem. Techniques include problem-specific methods and general approaches such as branch-and-bound, genetic algorithms, simulated annealing, and neural networks. P: Math 221 or Comp Sci 302 or cons inst.
435 Introduction to Cryptography. (Crosslisted with ECE, Math) II; 3 cr (A). Cryptography is the art and science of transmitting digital information in a secure manner. This course will provide an introduction to its technical aspects. P: Math 320 or 340 or cons inst. Open to Fr.
475 Introduction to Combinatorics. (Crosslisted with Math, Stat) I, II; 3 cr (N-A). Problems of enumeration, distribution, and arrangement. Inclusion-exclusion principle. Generating functions and linear recurrence relations. Combinatorial identities. Graph coloring problems. Finite designs. Systems of distinct representatives and matching problems in graphs. Potential applications in the social, biological, and physical sciences. Puzzles. Problem solving. P: Math 320 or 340 or cons inst.
513 Numerical Linear Algebra. (Crosslisted with Math) I; 3 cr (N-A). Direct and iterative solution of linear and nonlinear systems and of eigenproblems. LU and symmetric LU factorization. Complexity, stability, and conditioning. Nonlinear systems. Iterative methods for linear systems. Qr-factorization and least squares. Eigenproblems: local and global methods. P: Math 340 or equiv, Comp Sci 302 or equiv.
514 Numerical Analysis. (Crosslisted with Math) II; 3 cr (N-A). Polynomial forms, divided differences. Polynomial interpolation. Polynomial approximation: uniform approximation and Chebyshev polynomials, least-squares approximation and orthogonal polynomials. Numerical differentiation and integration. Splines, B-splines and spline approximation. Numerical methods for solving initial and boundary value problems for ordinary differential equations. P: Math 340 or equiv, Comp Sci 302 or equiv.
515 Introduction to Splines and Wavelets. (Crosslisted with Math) I or II; 3 cr (P-A). Introduction to Fourier series and Fourier transform; time-frequency localization; wavelets and frames. Applications: denoising and compression of signals and images. Interpolation and approximation by splines: interpolation, least-squares approximation, smoothing, knot insertion and subdivision; splines in CAGD. P: Comp Sci 302 or equiv, Math 340 or equiv.
520 Introduction to Theoretical Computer Science. I or II; 3 cr (N-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. P: Comp Sci 367, Math 222 & 240 or cons inst.
525 Linear Programming Methods. (Crosslisted with ISyE, Math, Stat) I, II; 3 cr (N-A). Real linear algebra over polyhedral cones; theorems of the alternative for matrices. Formulation of linear programs. Duality theory and solvability. The simplex method and related methods for efficient computer solution. Perturbation and sensitivity analysis. Applications and extensions, such as game theory, linear economic models, and quadratic programming. P: Math 443 or 320 or 340 or cons inst.
532 Theory and Applications of Pattern Recognition. (Crosslisted with ECE, ME) Even yrs.; II; 3 cr (P-A). Pattern recognition systems and components; decision theories and classification; discriminant functions; supervised and unsupervised training; clustering; feature extraction and dimensional reduction; sequential and hierarchical classification; applications of training, feature extraction, and decision rules to engineering problems. P: ECE 331 or Math 431 or cons inst.
533 Image Processing. (Crosslisted with ECE) I; 3 cr (P-A). Mathematical representation of continuous and digital images; models of image degradation; picture enhancement, restoration, segmentation, and coding; pattern recognition, tomography. P: ECE 330 or cons inst; Math 320 or 340 or equiv.
536 Introduction to Programming Languages and Compilers. I, II; 3 cr (N-A). Introduction to the theory and practice of compiler design. Comparison of features of several programming languages and their implications for implementation techniques. Several programming projects required. P: Comp Sci/ECE 354 & Comp Sci 367.
537 Introduction to Operating Systems. I, II; 3-4 cr (N-A). Input-output hardware, interrupt handling, properties of magnetic tapes, discs and drums, associative memories and virtual address translation techniques. Batch processing, time sharing and real-time systems, scheduling resource allocation, modular software systems, performance measurement and system evaluation. P: Comp Sci/ECE 354 & Comp Sci 367.
538 Introduction to the Theory and Design of Programming Languages. I or II; 3 cr (D). Design and theory of programming languages: procedural, object-oriented, functional and logic paradigms. Serial and concurrent programming. Execution models and formal specification techniques. P: Comp Sci/ECE 354 & Comp Sci 367.
539 Introduction to Artificial Neural Network and Fuzzy Systems. (Crosslisted with ECE, ME) I; Odd yrs.; 3 cr (D). Theory and applications of artificial neural networks and fuzzy logic: multi-layer perceptron, self-organization map, radial basis network, Hopfield network, recurrent network, fuzzy set theory, fuzzy logic control, adaptive fuzzy neural network, genetic algorithm, and evolution computing. Applications to control, pattern recognition, nonlinear system modeling, speech and image processing. P: Comp Sci 302, or Comp Sci 310, or knowledge of C programming lang.
540 Introduction to Artificial Intelligence. I, II, SS; 3 cr (N-A). Principles of knowledge-based search techniques, automatic deduction, knowledge representation using predicate logic, machine learning, probabilistic reasoning. Applications in tasks such as problem solving, data mining, game playing, natural language understanding, computer vision, speech recognition, and robotics. P: Comp Sci 367.
545 Natural Language and Computing. Irr.; 3 cr (N-A). The course covers basic techniques and tools in natural language processing: generative grammars, parsing, dictionary construction, semantic networks, generation of text from a knowledge base, natural language interfacing, and machine translation. P: Comp Sci 536 or 537 or 564 or cons inst.
547 Computer Systems Modeling Fundamentals. I or II; 3 cr (N-A). An introduction to basic tools and applications for modeling and analysis of computer systems. Fundamentals of network flow graphs, graph models of computation and stochastic models of computer system performance. Network delay analysis and capacity planning, reachability analysis for deadlock detection in distributed systems, Markov Chains, elementary queueing theory, basic concepts of queueing network models and associated analyses. P: Math 223, Comp Sci 367, & Comp Sci/ECE 354.
552 Introduction to Computer Architecture. (Crosslisted with ECE) I, II; 3 cr (P-A). The design of computer systems and components. Processor design, instruction set design, and addressing; control structures and microprogramming; memory management, caches, and memory hierarchies; and interrupts and I/O structures. P: ECE/Comp Sci 352 & Comp Sci/ECE 354.
558 Introduction to Computational Geometry. (Crosslisted with ME, ISyE) II; 3 cr (D). Introduction to fundamental geometric computations and algorithms, and their use for solving engineering and scientific problems. Computer representations of simple geometric objects and paradigms for algorithm design. Applications from areas of engineering analysis, design and manufacturing, biology, statistics, and other sciences. P: Comp Sci 367 or equiv, Math 223 or equiv, or cons inst.
559 Computer Graphics. I, II; 3 cr (I). Survey of computer graphics. Image representation, formation, presentation, composition and manipulation. Modeling, transformation, and display of geometric objects in two and three dimensions. Representation of curves and surfaces. Rendering, animation, multi-media and visualization. P: Math 320 or 340 & Comp Sci 367.
564 Database Management Systems: Design and Implementation. I, II; 3-4 cr (P-D). What a database management system is; different data models currently used to structure the logical view of the database: relational, hierarchical, and network. Hands-on experience with relational and network-based database systems. Implementation techniques for database systems. File organization, query processing, concurrency control, rollback and recovery, integrity and consistency, and view implementation. P: Comp Sci/ECE 354 & Comp Sci 367.
576 Introduction to Bioinformatics. (Crosslisted with BMI) I; 3 cr (A). Algorithms for computational problems in molecular biology. The course will study algorithms for problems such as: genome sequencing and mapping, pairwise and multiple sequence alignment, modeling sequence classes and features, phylogenetic tree construction, and gene-expression data analysis. P: Comp Sci 367, Math 222.
577 Introduction to Algorithms. I, II; 3 cr (N-A). Survey of important and useful algorithms for sorting, searching, pattern-matching, graph manipulation, geometry, and cryptography. Paradigms for algorithm design, hints for efficient implementation. P: Comp Sci 367, Math 222 & 240 or cons inst.
635 Tools and Environments for Optimization. (Crosslisted with ISyE) Irr.; 3 cr (P-I). Formulation and modeling of applications from computer sciences, operations research, business, science and engineering involving optimization and equilibrium models. Survey and appropriate usage of software tools for solving such problems, including modeling language use, automatic differentiation, subroutine libraries and web-based optimization tools and environments. P: Comp Sci 302, Math 340 or equiv.
638 Undergraduate Topics in Computing. I, II; 3 cr (N-A). P: Cons inst.
640 Introduction to Computer Networks. I or II; 3 cr (D). Architecture of computer networks and network protocols, protocol layering, reliable transmission, congestion control, flow control, naming and addressing, unicast and multicast routing, network security, network performance widely used protocols such as Ethernet, wireless LANs, IP, TCP, and Http. P: Comp Sci 537.
642 Introduction to Information Security. II; 3 cr (A). Senior level undergraduate course covering various topics on information security. Covers a wide range of topics, such as cryptographic primitives, security protocols, system security, and emerging topics. P: Comp Sci 537 or cons inst. Elementary knowledge of mathematical logic and discrete probability theory also required.
679 Computer Game Technology. Irr.; 3 cr (A). Survey of software technology important to computer games and other forms of interactive technology. Real-time image generation, managing complex geometric models, creating virtual characters, simulating physical phenomenon, networking technology for distributed virtual environments. P: Comp Sci 559.
681 Senior Honors Thesis. I, II, SS; 3 cr (A). P: Honors cand and cons inst.
682 Senior Honors Thesis. I, II, SS; 3 cr (A). P: Honors cand and cons inst.
691 Senior Thesis. I, II; 2-3 cr (A).
692 Senior Thesis. I, II; 2-3 cr (A).
699 Directed Study. I, II; 1-6 cr (A). P: Graded on a lettered basis; Jr or Sr st. Requires cons inst.