Introduction to Computing Science and Programming II

Lecture times and location:

• MWF 12:30-13:20, 10081 Saywell Hall

Instructor

• Mo Chen
  SFU Burnaby, TASC 1 8225
  mochen@cs.sfu.ca
  Office hours: Before and after lectures, Fridays 15:30-16:30

Teaching Assistants

• Pedram Agand, pagand@sfu.ca
  Office hours: Mondays 14:00-15:00 (ASB9810) , Virtual: Canvas link

• Elnaz Mehrzadeh, emehrzad@sfu.ca
  Office hours: Wednesdays 11:00-12:00, ASB9810

• Atefeh Sahraeekhanghah, asahraee@sfu.ca
  Office hours: Thursdays 12:00-13:00, ASB9808

Piazza Online discussion forum

• Sign up link
• Main page

Schedule / Lecture notes

• Jan. 6: Introduction
• Jan. 8: C and Programming basics
• Jan. 10: Pointer Operations
• Jan. 13: Arrays, Loops, Pointers
• Jan. 17: Array Comparison, Strings and Loops
• Jan. 20: Algorithm Performance
• Jan. 22: Big-O Revisited
• Jan. 24: Call Stacks and On Writing Good Code
• Jan. 24: Sorting and Searching
• Jan. 27: Insertion Sort
• Jan. 29: Simple Searching
• Jan. 31: Binary Search
• Feb. 3: Invariants 1
• Feb. 5: Invariants 2
• Feb. 7: Merge Sort | Animations
• Feb. 10: Quick Sort | Animations
• Feb. 12: Abstract Data Type | Animations
• Feb. 14: Linked List Operations I | Animations
• Feb. 24: Review Session
• Feb. 26: Midterm
• Feb. 28: Linked List Operations II | Code
• Mar. 2: Linked List Operations III | Code
• Mar. 4: Stack ADT | Animations
• Mar. 6: Queue ADT | Animations
• Mar. 9: Intro to C++ Classes | Code
• Mar. 11: More C++ | Code
• Mar. 13: Generics and STL | Code
• Mar. 16: Introduction to Trees
• Mar. 18: Binary Trees | Code
• Mar. 20: Binary Search Trees
• Mar. 23: Formal Languages and Finite State Machines
• Mar. 25: Finite State Machines and Regular Expressions
• Mar. 27: Regular Expressions and Regular Languages
• Mar. 30: Binary Encodings
• Apr. 1: Decidability
• Apr. 3: Intractability

• Lecture notes of this course are adapted from lecture notes of Brad Bart with minor modifications

Assignments

• Jan. 17: Assignment 1, due on Jan. 24. Solutions
• Jan. 24: Assignment 2, due on Jan. 31. Solutions
• Jan. 31: Assignment 3, due on Feb. 7. Solutions
• Feb. 7: Assignment 4, due on Feb. 14. Solutions
• Feb. 28: Assignment 5, due on Mar. 6. Solutions
• Mar. 6: Assignment 6, due on Mar. 13. Solutions
• Mar. 13: Assignment 7, due on Mar. 20. Solutions
• Mar. 20: Assignment 8, due on Mar. 27. Solutions
• Mar. 27: Assignment 9, due on Apr. 3. Solutions

Calendar Objective/Description

A rigorous introduction to computing science and computer programming, suitable for students who already have some background 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.

Instructor's Objectives

This course is a rigorous introduction to computing science, intended primarily for students who have already taken CMPT 120 as an introduction to algorithms and programming. Students will learn fundamental concepts of computing science and basic principles of algorithm design and software development. All case studies will be presented using a C-like subset of C++. The co-requisite to this course is CMPT 127, which is a 3-credit lab course. Students who enroll in CMPT 125 will be manually enrolled in CMPT 127. Students are required to take both courses at once, but their grades will be assigned independently of each other. CMPT 127 is a programming-intensive lab.

Prerequisites

CMPT 120. Corequisite: CMPT 127. Students with credit for CMPT 126, 129, 135 or CMPT 200 or higher may not take for further credit. Quantitative

Grading

• Homework: 20%
• In-class midterm (Feb. 26): 25%
  • Practice Midterm Solutions
  • Midterm Solutions
• Final (Apr. 19, 12:00-15:00): 55%
  • Study Tips
  • Practice Questions

Academic Honesty Statement

Academic honesty plays a key role in our efforts to maintain a high standard of academic excellence and integrity. Students are advised that ALL acts of intellectual dishonesty will be handled in accordance with the SFU Academic Honesty and Student Conduct Policies ( http://www.sfu.ca/policies/gazette/student.html ).