San Jose State University : Site Name

Navigation

Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Spring Semester 2018

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 180A: Data Structures and Algorithms in C++



Instructional Student Assistants
Weekly Tutoring Schedule


Amit Chougule
Monday 1:00-3:00 PM, room ENG 405
Zachary Zhong
Tuesday 3:00-5:00 PM, room ENG 405
Venkat Raja Iyer
Wednesday 2:00-4:00 PM, room ENG 405

Section 1: Th 6:00 - 8:45 PM, room ENG 189





Assignments


# Assigned Due Assignment
1 Jan 25 Feb 1 Pi Formulas

Sample solution: PiFormulas.cpp
2 Feb 1 Feb 8 The Monty Hall Problem

Sample solution: MontyHall.cpp
3 Feb 9 Feb 15 Hilbert Matrices

Sample solution: Hilbert.cpp
4 Feb 16 Feb 22 Big Pi

Sample solution: BigPi.cpp
5 Feb 23 Mar 1 Roman Numerals

Input file: RomanNumeral.txt
Sample solution: RomanNumeral.h    RomanNumeral.cpp    RomanNumeralTests.cpp
6 Mar 1 Mar 8 Book Catalog

Input file: commands.in
Expected output: output.txt
Sample solution: Book.h    Book.cpp    BookApp.cpp
7 Mar 8 Mar 22 U.S. maps

Input files: boundary-data.csv   city-data.csv
Sample solution: Assignment7Solution.zip
9 Mar 26 Apr 5 STL Vector and Linked List

Sample solution: Assignment9Solution.zip
10 Apr 5 Apr 12 Calculator

Sample solution (includes extra credit): Calculator.h    Calculator.cpp    CalculatorTester.cpp
11 Apr 14 Apr 19 STL Vector and Map

Input file: USConstitution.txt
Sample solution: Assignment11Solution.zip
12 Apr 21 Apr 26 Sorting Algorithms

Sample solution: Assignment12Solution.zip
13 Apr 27 May 3 BST and AVL trees

Expected output for Part 1: Assignment13-Part1-output.txt
Sample solutions: Assignment13-1-Solution.zip    Assignment13-2-Solution.zip    Assignment13-2-Graphs.xlsx


Lectures


Date Content
Jan 25 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
Feb 1 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:
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
Feb 8 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. Hilbert matrix

Savitch slides: 06 07 08
Feb 15 Slides: Assignment #2 sample solution; Assignment #3 sample solution; 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**; timing execution; Assignment #4 Big Pi

Savitch slides: 09
Dynamic array example: DynamicArray.cpp
Elapsed time example: TimeVector.cpp
Feb 22 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
Example class Birthday v1: Birthday1.cpp
Example class Birthday v2: Birthday2.cpp
Mar 1 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
Mar 8 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
Mar 15 Slides: Midterm; template function; template class "safe array" version 7; object-oriented programming; inheritance; subclasses; polymorphism; virtual destructors

Savitch slides: 15
Template function example: ExchangeTemplate.cpp
Template class example: Pair.h   PairTests.cpp
SafeArray example 7 (template): SafeArray7.h   SafeArrayTests7.cpp   Birthday7.h   Birthday7.cpp
Mar 22 Slides: Midterm solutions; Assignment #7 sample solution; exception handling; exception classes; throwing exceptions in a function; calculation puzzle; 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
Calculation puzzle: roundoff.cpp
Vector iterator examples: IteratorVector1.cpp   IteratorVector2.cpp
Apr 5 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   permutations.cpp   Hanoi.cpp   BinarySearchIterative.cpp   BinarySearchRecursive.cpp
Backtracking example: Queen.zip
Apr 12 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
Apr 19 Slides: Multiple inheritance (in solution to Assignment #11); 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
Apr 26 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
May 3 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
May 10 Slides: auto keyword; decltype pseudo-function; function definitions in header files; inline keyword; lambda expressions; multithreaded programming; race conditions; critical region; mutual exclusion; sleep and wakeup; semaphores and mutexes; POSIX threads; example multithreaded program

Inline examples: Inline1.h   InlineTest1.cpp   Inline2.h   InlineTest2.cpp   InlineTest3.cpp
Lambda examples: Person.h   Person.cpp   PersonTest1.cpp   PersonTest2.cpp
Multithreaded example: officehour-mac.c


Goals


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.


Prerequisites


Department policy is to enforce
all course prerequisites strictly

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