University of Minnesota
Computer Science & Engineering
http://www.cs.umn.edu/

CSCI 1902: Structure of Computer Programming II

Overall Description

CSci 1902 focuses on learning the key abstract data types (string, list, stack, queue, dictionary) and object oriented concepts (class, object, method, inheritance) in a modern language (currently Java). Upon successfully completing this class, students should be able to use abstract data types in solving a variety of problems, and be able to implement their solutions in an object oriented programming language.

1902 is a required undergraduate course which computer science and computer engineering students should take in their freshman or sophomore year. 1902 is one of the courses required for admission to the CSci major, and is a prerequisite for many of the higher level CSci classes.

Catalog Description:

Object-oriented programming using Java. Builds on 1901, presenting additional data structures/algorithms. Object-oriented approach to implement data structures/operations as abstract data types.

Content

WEEK 1: Overview of class. Introduction to Java.
WEEK 2: Basic introduction to classes. Class and method specification. Object oriented design. Control structures, standard I/O, scalar data types.
WEEK 3: Additional material on classes. Method definition and invocation, parameter passing, scopes.
WEEK 4: Composite data types: arrays, strings.
WEEK 5: Lists. Linked lists.
WEEK 6: Additional material on linked lists.
WEEK 7: Stacks.
WEEK 8: Queues.
WEEK 9: Review of recursion, introduction to trees: basic terminology and operations.
WEEK 10: Additional material on trees. Binary search trees. Heaps.
WEEK 11: Additional material on trees.
WEEK 12: Inheritance.
WEEK 13: Additional material on inheritance.
WEEK 14-15: Searching and sorting. Hash tables.

Why This Class is Important and its Role in the Curriculum

Much of computer science assumes familiarity with the common abstract data types (e.g. stacks) and basic concepts of an object oriented programming language. Moreover, many employers require programming skills in a modern object oriented programming language such as Java.

Most students will take 1902 in their first or second year. It is one of the courses required for admittance to the Csci major. Transfer students who have completed 2 years at another school should have taken an equivalent class.

Prerequisites and Rationale

Computer Science I (CSci 1901). 1902 assumes basic programming skills from its audience but no prior knowledge of C, C++ or Java. A semester of CS 1901 helps build fundamental programming skills, and prepares students for learning a more complex language such as Java. CSci 1901 uses Scheme, a typeless functional language, to enable students to explore deep programming concepts with little concern about syntax. CSci 1902 introduces a modern, industrial-strength programming language, including a sophisticated type system.

Classes Having 1902 as a Prerequisite and Rationale

These include CSci 2021 (Computer Organization), 3081 (Program Design and Development), and 4041 (Algorithms and Data Structures), which in turn are prerequisites for many other classes. 1902 teaches the notion of abstract data types as well as the fundamental abstract data types (stacks, queues, and trees), which are used extensively in the rest of Computer Science. To give a few quick examples, (i) the queue abstract data type is used for CPU and disk scheduling; (ii) stacks are used extensively in the compilers, architecture and programming languages courses to describe parsing algorithms for arithmetic expression, computer programs etc.; (iii) abstract data types and object oriented programming are used as basic tools for software engineering.

Class Format

4 credits, 3 large class + 1 recitation/lab hour per week. Recitation can be used for programming and review, or more in-depth discussion of topics and examples given in the large class. Since one of the emphases of the class is on developing students’ problem solving skill, the practice given in recitation will be highly valuable for many students.

Probable Text, If Any

Data Structures and Abstractions with Java, Second Edition, by Frank Carrano, Pearson Education, 2007, or Data Structures and Other Objects Using Java, Michael Main, Addison-Wesley, 2002.

Outcomes

Upon successful completion of the course students should have the following skills and proficiencies:

  1. For each of the abstract data types (e.g., stacks) discussed in class, the student should be able to:
    1. define the basic terminology and use it correctly,
    2. give an explanation of why it is important,
    3. provide and discuss specific CSci examples of its use,
    4. be able to identify its important characteristics as well as any important variants or special cases,
    5. perform the basic operations associated with it,
    6. use it, when applicable, to represent and solve problems.
  2. Students should also have the following additional programming, problem solving, and testing skills. Given a problem, students should be able to:
    1. identify which abstract data type and/or Java construct could be useful in representing or solving the problem, and why;
    2. modify or specialize abstract data types or techniques to make them applicable to problems that are not amenable to straightforward use of the abstract data types;
    3. develop a functioning object oriented program in Java, and document its functionality in terms of the given problem.
Contact CS&E | CS&E Employment | Site Map
Contact: 4-192 Keller Hall, 200 Union St, Minneapolis, MN 55455     Phone: (612) 625-4002