San Jose State University : Site Name


Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Department of Computer Science
Department of Applied Data Science
Fall Semester 2020

Office hours: TuTh: 4:30-5:30 PM online via Zoom
Office location: ENG 250 (but working from home)

CMPE/SE 180A: Data Structures and Algorithms in C++

Section 2: Tu 6:00 - 8:45 PM online via Zoom


# Assigned Due Assignment
1 Aug 25 Sep 1 Pi Recipes

Sample solution: PiRecipes.cpp
2 Sep 1 Sep 8 The Monty Hall Problem

Sample solution: MontyHall.cpp
3 Sep 8 Sep 15 War and Peace

Input file: WarAndPeace.txt
Sample solutions: WarAndPeace-NoNameSplits.cpp    WarAndPeace.cpp
4 Sep 15 Sep 22 Student Scores

Input file: students.txt
Sample solution (two versions): students.cpp    students-typedef.cpp    output.txt
5 Sep 22 Sep 29 Roman Numerals

Input file: RomanNumeral.txt
Sample solution: RomanNumeral.h    RomanNumeral.cpp    RomanNumeralTests.cpp
6 Sep 29 Oct 6 Book Catalog

Input file:
Expected output: output.txt
Sample solution:
7 Oct 6 Oct 20 U.S. maps

Input files: boundary-data.csv   city-data.csv
Sample solution:
9 Oct 20 Oct 27 Big Pi

Sample solution:
10 Oct 27 Nov 3 STL Vector and List

Sample solution:
11 Nov 3 Nov 10 U.S. Constitution

Input file: USConstitution.txt
Sample solution:
12 Nov 10 Nov 17 Sorting Algorithms

Sample solution:
13 Nov 17 Nov 24 BST and AVL trees

Expected output for Part 1: Part1-output.txt
Sample graphs for Part 2: Part2-graphs.pdf
Sample solutions:    Asgn13.2-BSTAVL.xlsx
14 Nov 24 Dec 4 Multithreading

Sample solutions:


Week Date Content
1 Aug 25 Zoom recording Password: yq8a#!XH
Slides: Course objectives; software to install; assignments; quizzes; exams; grading; what is C++; Hello World program; Pods and Peas program; identifier, variables, and keywords; assignment statements; input and output; #include and using namespace; formatting numbers; cin input; basic data types; string type; type compatibilities and conversions; arithmetic; operator shorthand; if statement; while loops; named constants; Boolean operators; precedence rules; enumeration types; nested if statements; switch statement; increment and decrement operators; for loops; break statement

Savitch slides: 01 02 03
Example programs: helloworld.cpp   nestedloop.cpp   Savitch_01-08.cpp   Savitch_03-06.cpp   Savitch_03-14.cpp
2 Sep 1 Zoom recording Password: @2Gdn%@3
Slides: Predefined functions; random numbers; type casting; programmer-defined functions: declarations, definitions, calls; void functions; top-down design; number translator example; scope and local variables; block scope; global constants and variables; overloading function names; call-by-value; call-by-reference; procedural abstraction; testing and debugging functions; assert macro; Assignment #2

Savitch slides: 04 05
Top-down design example:
translator1.cpp   translator2.cpp   translator3.cpp   translator4.cpp   translator5.cpp
Pass by value example: swap.cpp
Pass by reference example: exchange.cpp
Assert example: assert.cpp
3 Sep 8 Zoom recording Password: a!%m+7Ro
Slides: Assignment #2 sample solution; streams; file I/O; stream name vs. file name; formatting output; output manipulators; passing streams to functions; character I/O; predefined character functions; eof function; arrays; array initialization; array function parameters; multidimensional arrays; C strings; the standard string class; vectors; Assignment #3: War and Peace

Savitch slides: 06 07 08
4 Sep 15 Zoom recording Password: c.E@6pC*
Slides: Assignment #3 sample solutions; pointers; int vs. pointer to int; declaring and assigning pointers; pointers are addresses; address-of and dereferencing operators; new and delete operators; pointer parameters; use typedef; using pointers to pass-by-reference; pointers and arrays; pointer arithmetic; dynamic arrays; 2-D dynamic array; use typedefs; char* and char**; Assignment #4: Student Scores

Savitch slides: 09
Dynamic array examples: DynamicArray1.cpp   DynamicArray2.cpp   DynamicArray3.cpp
5 Sep 22 Zoom recording Password: HOX@PZ2d
Slides: Assignment #4 sample solution; structures; structures are types; scope of member names; structure variables; object-oriented programming (OOP); classes; member functions; public and private members; constructors; abstract data types (ADT); friend functions; operator overloading; overload <<; overload >>; Assignment #5 Roman Numerals

Savitch slides: 10 11
Example classes: Birthday1.cpp   Birthday2.cpp
6 Sep 29 Zoom recording Password: GWK=27!d
Slides: Assignment #5 sample solution; static class members; destructors; array of objects; vector of objects; copy constructor; "extra" constructor and destructor calls; how a vector grows; namespaces; search an array: linear search and binary search; Assignment #6 Book Catalog

Savitch slides: 12
Example classes:   BinarySearchIterative.cpp
7 Oct 6 Zoom recording Password: n4eBqF*z
Slides: Assignment #6 sample solution; a "safe" array type; assignment operator; overload the subscript operator []; copy constructor; the "big three"; linked list insertion and deletion; queue; stack; Assignment #7

Savitch slides: 13
SafeArray example 1: (crashes) SafeArray1.h   SafeArray2.cpp   SafeArrayTests1.cpp
SafeArray example 2 (operator =): SafeArray2.h   SafeArray2.cpp   SafeArrayTests2.cpp
SafeArray example 3 (fix operator =): SafeArray3.h   SafeArray3.cpp   SafeArrayTests3.cpp
SafeArray example 4 (another fix operator =): SafeArray4.h   SafeArray4.cpp   SafeArrayTests4.cpp
SafeArray example 5 (overload []): SafeArray5.h   SafeArray5.cpp   SafeArrayTests5.cpp
SafeArray example 6 (copy constructor): SafeArray6.h   SafeArray6.cpp   SafeArrayTests6.cpp
8 Oct 13 Zoom recording Password: 28s.zQS8
Slides: Midterm; template function; template class "safe array" version 7; object-oriented programming; inheritance; subclasses; polymorphism; virtual destructors

Savitch slides: 15
Template function example: TemplateExchange.cpp
Template class example: Pair.h   PairTests.cpp
SafeArray example 7 (template):
Virtual destructors:
9 Oct 20 Zoom recording Password: +7dK4?5J
Slides: Midterm solutions; Assignment #7 sample solution; calculation puzzle; chrono; auto; decltype; Assignment #9; exception handling; exception classes; throwing exceptions in a function; review of iteration; recursion; think recursively; recursive examples: factorials, multiplication

Savitch slides: 14 16
Malik slides: 06
Polymorphism example: Animal.cpp
Calculation puzzle: roundoff.cpp
Exception handling examples: exception1.cpp   exception2.cpp   exception3.cpp
Timed vector examples: TimeVector1.cpp   TimeVector2.cpp
Recursion examples: Factorial.cpp  
10 Oct 27 Zoom recording Password: S!4eX2Am
Slides: Pointer to a function; Assignment #9 suggested solution; Recursion examples: multiplication, Fibonacci, member of, unique, reverse; binary search: iterative and recursive; Towers of Hanoi; mergesort; the Standard Template Library (STL); iterators; containers; STL lis template class; Assignment #10

Sample programs: Multiply.cpp   Fibonacci1.cpp   Fibonacci2.cpp   Fibonacci3.cpp   MemberOf.cpp   Unique.cpp   Reverse.cpp   Permutations.cpp   Hanoi.cpp   BinarySearchRecursive.cpp
FunctionParm1.cpp   FunctionParm2.cpp
11 Nov 3 Zoom recording Password: ze&%5iB9
Slides: Hash tables; hash function; collisions; keys for successful hashing; collision resolution; separate chaining; open addressing: linear probing and quadratic probing; load factor; Assignment #11; introduction to algorithm analysis; how well an algorithm scales; Towers of Hanoi puzzle recurrence relation; proofs by induction; big-O notation and its cousins; rates of growth; rules for computing running time; scalability of different algorithms

Malik slides: 09
12 Nov 10 Zoom recording Password: Q6.x4?tE
Slides: Nasty C++ puzzle; sorting algorithms; selection sort; insertion sort; Shellsort; insertion sort vs. Shellsort; suboptimal and optimal Shellsort; mergesort for linked lists; analysis of mergesort; partitioning a list; partition using a pivot; quicksort; pivot strategy; suboptimal and optimal quicksort; median-of-three pivot strategy; sorting animations; Assignment #12

Malik slides: 10
Nasty C++ puzzle: Thing.h   Thing.cpp   IteratorEndTest.cpp
13 Nov 17 Zoom recording Password: +$0mt.V9
Slides: Trees; implementation; traversals: preorder and postorder; binary trees; infix ==> postfix; binary search trees; inorder tree traversal; min and max; contains; insert; remove; AVL trees; balancing: cases 1 - 4; AVL tree implementation; Assignment #13

Malik slides: 11
14 Nov 24 Zoom recording Password: X1M@=k36
Slides: Multithreaded programming; single-threaded and multithreaded Fibonacci example; pthread library; concurrency vs. parallelism; race condition; critical regions; shared resources; mutual exclusion; shared printing example; condition variables; producer-consumer model; unsynchronized and synchronized queue example; a multithreaded program example; pointers vs. references; raw pointers vs. smart pointers; unique pointer; shared pointer

Example programs: FibonacciST.cpp   FibonacciMT.cpp   PrintNoMutex.cpp   PrintMutex.cpp   QueueNoSync.cpp   QueueSync.cpp   OfficeHour.cpp
15 Dec 1 Zoom recording Password: @16a572d
Slides: Multithreading results; raw pointers vs. smart pointers; unique pointer; shared pointer; graphs: terms, examples, and representation; topological sort; unweighted shortest path algorithms; weighted least cost path; Dijkstra's algorithm; minimum spanning tree (MST); Prim's algorithm for MST; breadth-first and depth-first searches

Savitch slides: 17 18
Malik slides: 12 13
Smart pointer examples:


CMPE 180A is an introduction to data structures and algorithm design with C++. The course emphasizes important data structures, such as linked lists, stacks, queues, hash tables, trees, and graphs. It also introduces recursive algorithm design and algorithm analysis techniques. Learning to program well in a language like C++ requires much practice! You should expect to write one or more programs each week. The programming assignments will become increasing more challenging during the semester.


Department policy is to enforce
all course prerequisites strictly

Admission into the CMPE or SE masters program.

Required books

Problem Solving with C++, 10th edition
Walter Savitch
Pearson, 2017
ISBN: 978-0134710747
Data Structures Using C++, 2nd edition
D.S. Malik
Cengage Learning, 2010
ISBN: 978-0324782011

Software to install

GNU C++ is usually pre-installed on the Mac and Linux platforms. For those platforms, install an integrated development environments (IDE) such as Eclipse for C++ development:

Do not use Apple's Xcode on the Mac, or you run the risk of writing programs that will not port to other platforms.

On Windows, do not use Microsoft Visual C++, or you run the risk of writing programs that will not port to other platforms. Windows users should install Ubuntu.