CSCI 4041H -- New Course

Thu Jan 31 13:51:19 2013

Approvals Received:
Department
on 01-29-13
by Mary Freppert
(freppert@umn.edu)
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
Max-Min 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: A-F 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)
Auto-Enroll
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:
(course-based or
non-course-based)		 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 E-mail 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 in-class exercises. Students will be given well-defined problems and asked to choose (and justify their choices) the appropriate data structures and algorithms to solve them. Students will also be given some open-ended 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:

  • They explicitly help students understand what liberal education is, how the content and the substance of this course enhance a liberal education, and what this means for them as students and as citizens.
  • They employ teaching and learning strategies that engage students with doing the work of the field, not just reading about it.
  • They include small group experiences (such as discussion sections or labs) and use writing as appropriate to the discipline to help students learn and reflect on their learning.
  • They do not (except in rare and clearly justified cases) have prerequisites beyond the University's entrance requirements.
  • They are offered on a regular schedule.
  • They are taught by regular faculty or under exceptional circumstances by instructors on continuing appointments. Departments proposing instructors other than regular faculty must provide documentation of how such instructors will be trained and supervised to ensure consistency and continuity in courses.

 <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:
  • thinking ethically about important challenges facing our society and world;
  • reflecting on the shared sense of responsibility required to build and maintain community;
  • connecting knowledge and practice;
  • fostering a stronger sense of our roles as historical agents.


 <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 multi-authored 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>
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 in-depth 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. McGraw-Hill, 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 NP-completeness.

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: NP-Completeness, proving hardness, approximation algorithms for dealing with hardness.

Content

WEEKS 1-2:     INTRODUCTION AND REVIEW: Elements of algorithm analysis. Review of mathematical background: proof by induction, big-O notation. Review of basic data structures: stacks, queues, linked lists.
WEEKS 3-4:     SORTING: Review of insertion sort. Analysis of mergesort and Quicksort. Lower bound results on sorting. Radix Sort and Bucket Sort.
WEEKS 5-6:     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. Red-Black Trees. Optional: AVL trees. Splay trees.
WEEK 7:     HASHING: Hash Tables and Hashing.
WEEK 8:     DISJOINT SETS: Equivalence problems and disjoint sets.
WEEKS 9-10:     ALGORITHM DESIGN: Greedy algorithms and Dynamic Programming
WEEKS 11-13:    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 NP-Completeness.


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 make-up 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., big-O 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.
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 follow-up 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>