CS is fun!

CS is fun!

He/Him/His

I love designing and evaluating technologies that mediate communications between humans and also computers, resulting in improved user experience and user empowerment.

CMPT 125 Intro. to CS & Programming II

Undergraduate course, Simon Fraser University, School of Computing Science, 2023

An continuation from CMPT 120 on programming and some CS-related concepts (e.g., history, problem-solving). Introduces students to some common data structures (e.g., stacks, queues, linked lists, trees) and algorithms (e.g., Mergesort, Quicksort). C and C++ are the programming languages of choice.

This is for reference only. For actual outline refer to the course webpage at Canvas (our LMS). Content is subject to change (plus I often update it). This is the schedule I used for Spring 2023.

Course 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.

Course Objectives

This course introduces students to fundamental concepts of computing science and programming. By the end of the course, students will be familiar with building blocks of a computer program such as variables, arrays, pointers, recursions; as well as higher level concepts such as analysis of algorithms and coding style. Students will gain valuable knowledge and experience by solving problems using computational thinking.

By the end of this course students should be able to:

  • Design and implement solutions to problems using C/C++
  • Explain, analyze, and compare algorithms in terms of performance
  • Describe and utilize fundamental computing science concepts such as data structures
  • Maintain good coding practice and style

Recommended Textbooks

Seacord, R. C. (2020). Effective C. In Effective C. No Starch Press. Online access (requires SFU login)
Stroustrup, B. (2024). Programming : principles and practice using C++ / Bjarne Stroustrup. (Third edition.). Addison-Wesley. Online access (requires SFU login)

Course Schedule

WeekTopicsReadings/Watchings1
1Course intro
  • Logistics, expectations
  • Intro to C, Coding Environments
Effective C chapters: 1
2C basics (Part 1)
  • Variables & strong typing
  • Data vs address
  • Pointers, references, arrays
  • Constant variabes
  • Strings
  • Reading from stdin
  • 2D arrays
Effective C chapters: 2 & 5
3C basics (Part 2)
  • Composite datatypes & enums
  • Functions, return values, & conditions
  • Global & static variables
  • Macros
  • Memory allocation
  • Execution stack
Effective C chapters: 2 & 5, 6
4C basics (Part 3)
  • Returning structs, pointers to functions
  • Binary encoding of numbers
  • Pseudo-code
  • Recursion
  • Algorithms & performance
Learn more about sorting with visualization [LINK]
5Basic algorithms & data structures (Part 1)
  • Big-O notation
  • Searching algorithms
Learn more about searching with visualization [LINK]
6Basic algorithms & data structures (Part 2)
  • Sorting algorithms

Abstract data types		Learn more about sorting with visualization [LINK]
7Basic algorithms & data structures (Part 3)
  • Stacks
  • Queues
External readings:
8Reading break-
9Basic algorithms & data structures (Part 4)
  • Linked lists
Recursion revisited		-
10Basic algorithms & data structures (Part 5)
  • Intro to graphs & trees
  • Tree traversals & operations
Additional references to Trees
11Basic algorithms & data structures (Part 6)
  • Binary Search Trees (BSTs)
Learn more about BSTs with visualization [LINK]
12Intro to C++ (Part 1)
  • cin/cout
  • strings
  • function overloading
  • templates
External readings:
13Intro to C++ (Part 2)
  • Pass-by-reference functions
  • Operator overloading
  • Exception handling
  • Intro to OOP
Additional references:
14Intro to C++ (Part 3)
  • Object-Oriented Design (OOD)
  • Examples in C++
Review		-
??Final Exam-

  1. References in Topics/Readings are for reference only. If there is any topic/concept that is in conflict between class slides and any of these references, what is taught in the classes will be used. ↩