# Ronald Mak

Department of Computer Engineering
Fall Semester 2017

 Office hours: TuTh: 3:00-4:00 PM Office location: ENG 250 E-mail: ron.mak@sjsu.edu
Mission Control, Jet Propulsion Laboratory (JPL)
NASA Mars Exploration Rover Mission

# CMPE/SE 180-92: Data Structures and Algorithms in C++

#### Instructional Student Assistants Weekly Tutoring Schedule

Zachary Zhong
Monday 3:00-5:00 PM, room E405
Venkat Raja Iyer
Tuesday 1:00-3:00 PM, room E405
Amit Chougule
Wednesday 3:00-5:00 PM, room E405

### Assignments

# Assigned Due Assignment
1 Aug 24 Aug 31 Watering Plans
Input file: counts.txt

Sample solution: WateringPlans.cpp
2 Aug 31 Sep 7 Functional Decomposition
Input file: counts.txt

Sample solution: WateringPlans.cpp
3.a Sep 7 Sep 14 Prime Numbers

Sample solution: primes.cpp
3.b Sep 7 Sep 14 Spirals

Sample solution: spirals.cpp
3.c Sep 7 Sep 14 Prime Spirals

Sample solution: PrimeSpirals.cpp
4 Sep 14 Sep 21 Big Pi

Sample solution: BigPiNonic.cpp
Extra credit: BigPiNonicMillion.cpp
One million digits of pi: BigPiNonicMillion.txt
Compare to: https://www.exploratorium.edu/pi/numbers-of-pi
5 Sep 21 Sep 28 Roman Numerals

Sample solution: RomanNumeral.h    RomanNumeral.cpp    RomanNumeralTests.cpp
6 Sep 28 Oct 5 Book Catalog
Input file: commands.in
Expected output: output.txt

Sample solution: Book.h    Book.cpp    BookApp.cpp
7 Oct 7 Oct 19 Book Lists
Input files: categories.txt    childrens.txt    history.txt    mystery.txt    science.txt
Expected output: output.txt

Sample solution: BookNode.h    BookNode.cpp    Book.h    Book.cpp    BookList.h    BookList.cpp    BookListsApp.cpp
9 Oct 20 Oct 26 STL Vector and List
Expected output: output.txt
Expected extra credit output: outputx.txt

Sample solution: Node.h    Node.cpp    SortedVector.h    SortedVector.cpp    SortedList.h    SortedList.cpp    TestSuite.h    TestSuite.cpp    STLVectorList.cpp

Sample extra credit solution: Node.h    Node.cpp    SortedVector.h    SortedVector.cpp    SortedList.h    SortedList.cpp    TestSuite.h    TestSuite.cpp    STLVectorList.cpp
Can you find the three minor changes?
10 Oct 26 Nov 2 Calculator

Sample solution (includes extra credit): Calculator.h    Calculator.cpp    CalculatorTester.cpp
11 Nov 4 Nov 9 STL Vector and Map
Input file: USConstitution.txt

Sample solution: Asgn11Solution.zip
12 Nov 10 Nov 16 Sorting Algorithms

Sample solution: Asgn12Solution.zip
13 Nov 18 Nov 30 BST and AVL Trees
Expected output (Part 1): output-1.txt

Sample solutions: Asgn13.1Solution.zip    Asgn13.2Solution.zip    Asgn13.2Graphs.xlsx

### Lectures

Date Content
Aug 24 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   Savitch_01-08.cpp   Savitch_03-06.cpp   Savitch_03-14.cpp
Aug 31 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 Functional Decomposition

Savitch slides: 04 05
Top-down design example:
int2words_1.cpp   int2words_2.cpp   int2words_3.cpp   int2words_4.cpp   int2words_5.cpp
Pass-by-value example: swap.cpp
Pass-by-reference example: exchange.cpp
Sep 7 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; Assignment #3.a Prime Numbers; multidimensional arrays; Assignment #3.b. Spirals; C strings; the standard string class; vectors; Assignment #3.c. Prime Spirals

Savitch slides: 06 07 08
Sep 14 Slides: Assignment #3 solutions; 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; typedef; using pointers to pass-by-reference; pointers and arrays; pointer arithmetic; dynamic arrays; char* and char**; Assignment #4 Big Pi

Savitch slides: 09
Dynamic array example: DynamicArray.cpp
Sep 21 Slides: Assignment #4 sample solutions; 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 Rationals

Savitch slides: 10
Example class Birthday v1: Birthday1.cpp
Example class Birthday v2: Birthday2.cpp
Sep 28 Slides: Assignment #5 sample solution; array of objects; destructors; vector of objects; copy constructor; "extra" constructor and destructor calls; namespaces; how a vector grows; search an array: linear search and binary search; Assignment #6 Book Catalog

Savitch slides: 11 12
Example class Birthday v3: Birthday3.h   Birthday3.cpp   BirthdayTester3.cpp
Example class Birthday v4: Birthday4.h   Birthday4.cpp   BirthdayTester4.cpp
Example class Birthday v5: Birthday5.h   Birthday5.cpp   BirthdayTester5.cpp
Oct 5 Slides: Assignment #6 sample solution; a "safe" array type; assignment operator; overload the subscript operator []; copy constructor; linked list insertion and deletion; queue; stack; Assignment #7; namespaces

Savitch slides: 13 17
SafeArray example 1: 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 (overload []): SafeArray4.h   SafeArray4.cpp   SafeArrayTests4.cpp
SafeArray example 5 (copy constructor): SafeArray5.h   SafeArray5.cpp   SafeArrayTests5.cpp
Oct 12 Slides: Midterm; template function; template class "safe array" version 6; object-oriented programming; inheritance; subclasses; polymorphism; virtual destructors

Savitch slides: 15
Oct 19 Slides: Midterm solutions; Assignment #7 sample solution; exception handling; exception classes; throwing exceptions in a function; random numbers; chrono; timing execution; Standard Template Library (STL), iterators; vector iterator; kinds of iterators; containers; list template class; linked list vs. vector; Assignment #9;

Savitch slides: 16 17 18

Exception handling examples: exception1.cpp   exception2.cpp   exception3.cpp
Vector iterator examples: IteratorVector1.cpp   IteratorVector2.cpp
Elapsed time example: TimeVector.cpp
Oct 26 Slides: Review of iteration; recursion; think recursively; recursive examples: factorials, multiplication, Fibonacci (iterative and recursive), member of, unique, reverse, Towers of Hanoi; linear search; binary search (iterative and recursive); queens problem; backtracking

Savitch slides: 14
Malik slides: 06
Recursion examples: Factorial.cpp   Multiply.cpp   Fibonacci1.cpp   Fibonacci2.cpp   Fibonacci3.cpp   MemberOf.cpp   Unique.cpp   Reverse.cpp   Hanoi.cpp   BinarySearchIterative.cpp   BinarySearchRecursive.cpp
Backtracking example: Queen.zip
Nov 2 Slides: 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; hash tables; hash function; collisions; keys for successful hashing; collision resolution; separate chaining; open addressing: linear probing and quadratic probing; load factor

Malik slides: 09
Nov 9 Slides: 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; Assignment #12; sorting animations

Malik slides: 10
Nov 16 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
Nov 30 Slides: Assignment #13 solution; 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; depth-first and breadth-first searches

Malik slides: 12
Dec 7 Slides: auto keyword; decltype pseudo-function; function definitions in header files; inline keyword; "The Big Three"; Qt; GUI programming; inversion of control

"Big Three" examples: Array1.cpp   Array2.cpp   Array3.cpp
Qt examples: factorial.zip   TextFinder.zip

### Goals

First goal: You will learn to design and write well-crafted programs in a useful subset of the C++ language.

Second goal: You will learn how to use C++ to implement some fundamental algorithms and data structures reliably and efficiently.

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.

### Prerequisites

Admission into the CMPE or SE masters program.

### Required books

 Problem Solving with C++, 9th edition Walter Savitch Pearson, 2015 ISBN: 978-0133591743 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 one of the following integrated development environments (IDE) 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 run use Microsoft Visual C++, or you run the risk of writing programs that will not port to other platforms. Windows users should install VirtualBox and run Linux as a virtual machine. Debian is a good Linux distribution. Download a .iso installation image and install it VirtualBox. Run Debian on the virtual machine and use its pre-installed GNU C++ compiler. Then you can install Eclipse or NetBeans for Linux.