New Course Proposal - CMPT 125-3 Introduction to Computing Science and Programming II

G. Baker, B. Bart, T. Dixon, Q. Gu, A. Lavergne, D. Mitchell, Syllabus Working Group, School of Computing Science

October 23, 2003

Calendar Information

Course Number: CMPT 125

Course Title: Introduction to Computing Science and Programming II

Credit Hours: 3 Vector: 3-0-0

Course Description

A rigorous introduction to computing science and computer programming, suitable for students who already have some backgrounds in computing science and programming. Intended for students who will major in computing science or a related program. Topics include: fundamental algorithms; elements of empirical and theoretical algorithmics; abstract data types and elementary data structures; basic object-oriented programming and software design; computation and computability; specification and program correctness; and history of computing science.

Prerequisite: CMPT 120 or an equivalent background. A self-evaluation on the Computing Science web site can be used by students to decide whether they can skip CMPT 120 and start with CMPT 125.

Recommended: None.

Corequisite: None.

Special Instructions: None.

Course(s) to be dropped if this course is approved:

CMPT 101-4 and CMPT 201-4 are proposed to be replaced by the new three-course sequence CMPT 120-3, CMPT 125-3, CMPT 225-3.

Rationale for Introduction of this Course

At present, students enter CMPT 101 with diverse backgrounds and expectations. A large proportion of students have little or no exposure to programming, and a similarly large fraction have written substantial programs or written programs in more than one language. This creates a problem in choosing a rate and depth of coverage for the course. The CMPT 120/125 sequence is designed for those with little or no exposure to computing science and programming, with a bypass mechanism into CMPT 125 for those with substantial prior experience.

Will this be a required or elective course in the curriculum; probable enrolment when offered?

Required; enrolment estimated at 800 per year.

Scheduling and Registration Information

Indicate Semester and Year this course would be first offered and planned frequency of offering thereafter.

2004-3 and every semester thereafter.

Which of your present CFL faculty have the expertise to offer this course? Will the course be taught by sessional or limited term faculty?

Almost all present faculty could teach this course. Sessionals or limited term faculty may on occasion teach a parallel section to that taught by a CFL faculty member serving as course champion.

Are there any proposed student fees associated with this course other than tuition fees?

No.

Is this course considered a `duplicate' of any current or prior course under the University's duplicate course policy? Specify, as appropriate.

Students with credit for CMPT 101, 104 or any course numbered CMPT 200 or higher may not take this course for further credit.

Resource Implications

Note: Senate has approved (S.93-11) that no new course should be approved by Senate until funding has been committed for necessary library materials. Each new course proposal must be accompanied by a library report and, if appropriate, confirmation that funding arrangements have been addressed.

Provide details on how existing instructional resources will be redistributed to accommodate this new course. For instance, will another course be eliminated or will the frequency of offering of other courses be reduced; are there changes in pedagogical style or class sizes that allow for this additional course offering.

This course will use instructional resources currently used for CMPT 101 as well as new resources made available through the Double the Opportunity (DTO) program.

Does the course require specialized space or equipment not readily available in the department or university, and if so, how will these resources be provided?

No.

Does this course require computing resources (e.g. hardware, software, network wiring, use of computer laboratory space) and if so, describe how they will be provided.

This course will use instructional resources currently used for CMPT 101 as well as new resources made available through the Double the Opportunity (DTO) program.

Outline of CMPT-125 Syllabus

Fundamental Data Structures: (more) primitive types; arrays; strings; lists; queues; stacks

OOP: classes and instances; exception handling; GUI; references; event-driven programming; etc.

Software development process: problem statement->OO design (pseudo code)->OO solution->test/debugging.

Recursion: Concept of recursion; divide-and-conquer strateties.

Basic Algorithm Analysis: Big-O Notation; standard complexity classes.

quadratic and O(nlogn) sorting algorithms. sequential and binary search.

History of Computation: History of Computation as a Science; History of Computers ; History of Programming languages

Basic Computatiliby: Machine models (RAM; ASM; TURING MACHINE); Computable functions; tractable and intractable problems; the halting problems; uncomputable functions and implications of uncomputability.

Specifying correctness; proving correctness; designing tests.

Introduction to social aspects.

Prequisite: CMPT-120 or an equivalent background. A self-evaluation on the Computing Science web site can be used by students to decide whether they can skip CMPT120 and start with CMPT125.

Sample Course Outline

A number of case studies will be used to introduce software development process: problem statement-> OO design (pseudo code)-> OO S/W solution -> testing and debugging.

Unit Weeks Computing Science Algorithms Programming Language Assignment/Examples

1. 1 120 review, basic CS
Linear search, selection sort, dot product
Review of 120 using Java or C++ Implementation of basic
algorithms in Java or C++

2. 2
Case Study #1
Software Development Process: problem statement -> O.O. design (pseudocode) -> O.O. S/W Solution -> Testing and Debugging
Conditional
iteration (Java or C++) Classes
Exception Handling
(+ Applet,for graphics)
games (use random numbers)
(connect with exercise/assignement/example
seen in similar units of 120)

3. 2
Case Study #2

Explain binary search visually, introduce its two implementations:
iterative binarysearch Arrays, recursion, GUI intro Implement search,
"Hello World" GUI

4. 2 Recursion, divide and conquer, Induction, assertion, correctness, complexity analysis
computational model RAM Recursive Binary search,
Mergesort GUI intro
Snowflake (GUI worked into
other assignments as well)

5. 2
Case Study #3

Simple parsing
Strings
File I/O
More about Exception Handling parse an int/floating point, implement grep, paragraph formatting, line breaks, code prettyprinter

6. 2 Case Study #4,

stacks and queues (informal, simple implementation) parsing expressions
References
Linked List
List ADT simple expression parser

7. 1 Turing Machine and computability
Revisit Big O notation Review of sorting algorithms, selection or insertion sort
- mergesort
implement FSM, implement
sort, Turing machine paper work

8. 1 User Interface Design
Event-driven programming
(Applet, AWT, SWING) GUI

9.
1
Social issue of CS: privacy issue,
employment issue;
Program paradigms

Examples of different programming
languages

Unit	Weeks	Computing Science	Algorithms	Programming Language	Assignment/Examples
1.	1	120 review, basic CS	Linear search, selection sort, dot product	Review of 120 using Java or C++	Implementation of basic algorithms in Java or C++
2.	2	Case Study #1 Software Development Process: problem statement -> O.O. design (pseudocode) -> O.O. S/W Solution -> Testing and Debugging	Conditional iteration (Java or C++)	Classes Exception Handling (+ Applet,for graphics)	games (use random numbers) (connect with exercise/assignement/example seen in similar units of 120)
3.	2	Case Study #2	Explain binary search visually, introduce its two implementations: iterative binarysearch	Arrays, recursion, GUI intro	Implement search, "Hello World" GUI
4.	2	Recursion, divide and conquer, Induction, assertion, correctness, complexity analysis computational model RAM	Recursive Binary search, Mergesort	GUI intro	Snowflake (GUI worked into other assignments as well)
5.	2	Case Study #3	Simple parsing	Strings File I/O More about Exception Handling	parse an int/floating point, implement grep, paragraph formatting, line breaks, code prettyprinter
6.	2	Case Study #4,	stacks and queues (informal, simple implementation) parsing expressions	References Linked List List ADT	simple expression parser
7.	1	Turing Machine and computability Revisit Big O notation	Review of sorting algorithms, selection or insertion sort - mergesort		implement FSM, implement sort, Turing machine paper work
8.	1	User Interface Design		Event-driven programming (Applet, AWT, SWING)	GUI
9.	1	Social issue of CS: privacy issue, employment issue; Program paradigms		Examples of different programming languages