Thu Jan 31 13:51:19 2013
Approvals Received: 



Approvals Pending:  College/Dean > Honors > Catalog > PeopleSoft Manual Entry  
Effective Status:  Active  
Effective Term:  1139  Fall 2013  
Course:  CSCI 4041H  
Institution: Campus: 
UMNTC  Twin Cities UMNTC  Twin Cities 

Career:  UGRD  
College:  TIOT  College of Science and Engineering  
Department:  11108  Computer Science & Eng  
General  
Course Title Short:  Algs. & Data Str.  
Course Title Long:  Algorithms and Data Structures  
MaxMin Credits for Course: 
4.0 to 4.0 credit(s)  
Catalog Description: 
Rigorous analysis of algorithms and their implementation. Algorithm analysis, sorting algorithms, binary trees, heaps, priority queues, heapsort, balanced binary search trees, AVL trees, hash tables and hashing, graphs, graph traversal, single source shortest path, minimum cost spanning trees.  
Print in Catalog?:  Yes  
CCE Catalog Description: 
<no text provided>  
Grading Basis:  AF only  
Topics Course:  No  
Honors Course:  Yes  
Online Course:  No  
Instructor Contact Hours: 
4.0 hours per week  
Years most frequently offered: 
Every academic year  
Term(s) most frequently offered: 
Fall  
Component 1: 
DIS (no final exam)  
Component 2: 
LEC (with final exam) 

AutoEnroll Course: 
Yes  
Graded Component: 
DIS  
Academic Progress Units: 
Not allowed to bypass limits. 4.0 credit(s) 

Financial Aid Progress Units: 
Not allowed to bypass limits. 4.0 credit(s) 

Repetition of Course: 
Repetition not allowed.  
Course Prerequisites for Catalog: 
1902, 2011, honors student, or #; cannot be taken for Grad CSci cr  
Course Equivalency: 
CSci 4041/CSci 4041H  
Consent Requirement: 
No required consent  
Enforced Prerequisites: (coursebased or noncoursebased) 
000571  honors student  
Editor Comments:  <no text provided>  
Proposal Changes:  <no text provided>  
History Information:  Jan 2013 adding course per Honors College request  
Faculty Sponsor Name: 
Maria Gini  
Faculty Sponsor Email Address: 
gini@cs.umn.edu  
Student Learning Outcomes  
Student Learning Outcomes: 
* Student in the course:
 Can identify, define, and solve problems
Please explain briefly how this outcome will be addressed in the course. Give brief examples of class work related to the outcome. CSci 4041H is focused on data structures and algorithms. The ability to select and use appropriate data structures and algorithms to solve problems is essential in most computer science applications. Students also learn to analyze the complexity of algorithms. How will you assess the students' learning related to this outcome? Give brief examples of how class work related to the outcome will be evaluated. This SLO will be assessed through homework, programming assignments, exams, and inclass exercises. Students will be given welldefined problems and asked to choose (and justify their choices) the appropriate data structures and algorithms to solve them. Students will also be given some openended problems where they need first to identify, define, and/or clarify what the problem is before solving it.  
Liberal Education  
Requirement this course fulfills: 
None  
Other requirement this course fulfills: 
None  
Criteria for Core Courses: 
Describe how the course meets the specific bullet points for the proposed core
requirement. Give concrete and detailed examples for the course syllabus, detailed
outline, laboratory material, student projects, or other instructional materials or method.
Core courses must meet the following requirements:
<no text provided> 

Criteria for Theme Courses: 
Describe how the course meets the specific bullet points for the proposed theme
requirement. Give concrete and detailed examples for the course syllabus, detailed outline,
laboratory material, student projects, or other instructional materials or methods. Theme courses have the common goal of cultivating in students a number of habits of mind:
<no text provided> 

Writing Intensive  
Propose this course as Writing Intensive curriculum: 
No  
Question 1 (see CWB Requirement 1): 
How do writing assignments and writing instruction further the learning objectives
of this course and how is writing integrated into the course? Note that the syllabus must
reflect the critical role that writing plays in the course. <no text provided> 

Question 2 (see CWB Requirement 2): 
What types of writing (e.g., research papers, problem sets, presentations,
technical documents, lab reports, essays, journaling etc.) will be assigned? Explain how these
assignments meet the requirement that writing be a significant part of the course work, including
details about multiauthored assignments, if any. Include the required length for each writing
assignment and demonstrate how the minimum word count (or its equivalent) for finished writing will
be met. <no text provided> 

Question 3 (see CWB Requirement 3): 
How will students' final course grade depend on their writing performance?
What percentage of the course grade will depend on the quality and level of the student's writing
compared to the percentage of the grade that depends on the course content? Note that this information
must also be on the syllabus. <no text provided> 

Question 4 (see CWB Requirement 4): 
Indicate which assignment(s) students will be required to revise and resubmit after
feedback from the instructor. Indicate who will be providing the feedback. Include an example of the
assignment instructions you are likely to use for this assignment or assignments. <no text provided> 

Question 5 (see CWB Requirement 5): 
What types of writing instruction will be experienced by students? How much class
time will be devoted to explicit writing instruction and at what points in the semester? What types of
writing support and resources will be provided to students? <no text provided> 

Question 6 (see CWB Requirement 6): 
If teaching assistants will participate in writing assessment and writing instruction,
explain how will they be trained (e.g. in how to review, grade and respond to student writing) and how will
they be supervised. If the course is taught in multiple sections with multiple faculty (e.g. a capstone
directed studies course), explain how every faculty mentor will ensure that their students will receive
a writing intensive experience. <no text provided> 

Readme link.
Course Syllabus requirement section begins below


Course Syllabus  
Course Syllabus: 
For new courses and courses in which changes in content and/or description and/or credits
are proposed, please provide a syllabus that includes the following information: course goals
and description; format;structure of the course (proposed number of instructor contact
hours per week, student workload effort per week, etc.); topics to be covered; scope and
nature of assigned readings (text, authors, frequency, amount per week); required course
assignments; nature of any student projects; and how students will be
evaluated. The University "Syllabi Policy" can be
found here
The University policy on credits is found under Section 4A of "Standards for Semester Conversion" found here. Course syllabus information will be retained in this system until new syllabus information is entered with the next major course modification. This course syllabus information may not correspond to the course as offered in a particular semester. (Please limit text to about 12 pages. Text copied and pasted from other sources will not retain formatting and special characters might not copy properly.) Sample Course Syllabus Overall Description 4 credits, 3 large class + 1 recitation hour per week. Recitation can be used for problem solving and review, or more indepth discussion of topics and examples given in the large class. Since many students struggle with topics like analyzing algorithms, identifying what algorithms/data structures are appropriate to use in given situations, etc., the practice given in recitation will be valuable. Text Introduction to Algorithms, 2nd ed., Cormen, Leiserson, Rivest, and Stein. McGrawHill, 2001. Learning goals: 4041 is a required course for computer science and computer engineering majors. It is a useful course for other students who desire to learn some core material in computing. We expect computer science and computer engineering students to take 4041 in their junior year. 4041 builds upon material from 2011 (Discrete Structures) and 1902 (CS II), and is a prerequisite for many CSci elective courses. Upon successfully completing this course students should know many fundamental algorithms and data structures commonly used in computer science. Moreover, they should be able to use these algorithms and data structures both in programming, and in problem analysis. Also, they should be familiar with other related topics such as NPcompleteness. Honors Class: This is the honors version of CSci 4041. It will therefore cover the usual 4041 material such as sorting and searching, advanced data structures, dynamic programming, greedy algorithms, and graph algorithms. However, as the honors version it will also allow looking at some of those topics in more detail, and including some additional material. Examples of possible additional topics include, but are not limited to: NPCompleteness, proving hardness, approximation algorithms for dealing with hardness. Content WEEKS 12: INTRODUCTION AND REVIEW: Elements of algorithm analysis. Review of mathematical background: proof by induction, bigO notation. Review of basic data structures: stacks, queues, linked lists. WEEKS 34: SORTING: Review of insertion sort. Analysis of mergesort and Quicksort. Lower bound results on sorting. Radix Sort and Bucket Sort. WEEKS 56: BINARY TREES: Review of general properties, traversals, and binary search trees. Applications such as prefix codes and Huffman's algorithm. Heaps. Priority queues. Heapsort. Balanced Binary Search trees. RedBlack Trees. Optional: AVL trees. Splay trees. WEEK 7: HASHING: Hash Tables and Hashing. WEEK 8: DISJOINT SETS: Equivalence problems and disjoint sets. WEEKS 910: ALGORITHM DESIGN: Greedy algorithms and Dynamic Programming WEEKS 1113: GRAPHS: Review of definitions, traversal, topological sorting, single source shortest path, minimum cost spanning trees. Maximum flow problems. Connected components. Strong components. Biconnectivity. WEEKS 14: COMPLEXITY: Introduction to NPCompleteness. Grading is absolute (i.e. not on a curve). A minimum of 60% is necessary for an S or C grade. Grading will be as follows: 94.0% or above yields an A, 90.0% an A, 85% = B+, 80% = B, 75% = B, 70% = C+, 65% = C, 60% = C, 55% = D+, 50% = D, and less than 50% yields an F. Policies Makeup Exam Policy: There will be no provision for makeup exams, except in extraordinary and documented circumstances. Academic Integrity Policy: Every student is expected to turn in his or her own work for all homeworks, assignments and exams. While students can generally discuss how to solve homework/assignment problems, they have to submit their own solutions/code for the problems. The University Student Conduct Code defines scholastic dishonesty as: submission of false records of academic achievement; cheating on assignments or examinations; plagiarizing; altering, forging, or misusing a University academic record; taking, acquiring, or using test materials without faculty permission; acting alone or in cooperation with another to falsify records or to obtain dishonestly grades, honors, awards, or professional endorsement. In this course, a student responsible for scholastic dishonesty will be assigned a penalty of an "F" or "N" for the course. If you have any questions regarding the expectations for a specific assignment or exam, please ask us. See the University of Minnesota Conduct Code for details. Special Circumstances: Students with special needs or circumstances should contact me as soon as possible to make any necessary arrangements. As outlined above, extensions are only granted for unforeseen and extraordinary circumstances. Other accommodations may be arranged in cooperation with disability services. Class outcomes 1. For each of the data structures (e.g., graphs), or techniques (e.g., bigO analysis, greedy algorithms) discussed in class, the student should be able to: a, define the basic terminology and use it correctly. b. give an explanation of why it is important. c. provide and discuss specific CSci examples of its use. d. be able to identify its important characteristics, as well as any variants or special cases. e. perform the basic operations associated with it. f. use it, when applicable, to analyze and solve problems. 2. For each of the algorithms covered, the student should be able to: a. explain the algorithm's purpose, key steps, major characteristics, and what types of problems it is applicable to; and given input, be able to trace through the workings of the algorithm. b. be able to analyze the time and space requirements of the algorithm (including variants or special cases of the algorithm). c. be able to analyze correctness of a purported algorithm. d. be able to explain general features of particular types of algorithms (e.g., greedy algorithms). 3. Students should also have the following additional analysis, problem solving, and presentation skills. Given a problem, students should be able to: a. identify which structures, algorithms, and/or techniques could be useful in analyzing or solving the problem, and why; and be able to modify or specialize structures, algorithms, or techniques to make them applicable to problems that are not amenable to straightforward use of the structure, algorithm or technique. b. present a clear, concise, logically accurate, and rigorous solution. c. tell whether a purported solution or analysis is accurate. d. if appropriate, be able to design and implement a coded solution. 

Readme link.
Strategic Objectives & Consultation section begins below


Strategic Objectives & Consultation  
Name of Department Chair Approver: 
<no text provided>  
Strategic Objectives  Curricular Objectives: 
How does adding this course improve the overall curricular objectives ofthe unit? <no text provided> 

Strategic Objectives  Core Curriculum: 
Does the unit consider this course to be part of its core curriculum? <no text provided> 

Strategic Objectives  Consultation with Other Units: 
In order to prevent course overlap and to inform other departments of new
curriculum, circulate proposal to chairs in relevant units and followup with direct
consultation. Please summarize response from units consulted and include correspondence. By
consultation with other units, the information about a new course is more widely disseminated
and can have a positive impact on enrollments. The consultation can be as simple as an
email to the department chair informing them of the course and asking for any feedback
from the faculty. <no text provided> 
