Syllabus

Description: This course provides an introduction to the design and implementation of software for personal navigation systems. Specifically, it considers how prinicpals of object-oriented design can be applied in this particular domain and the algorithms and data structures that are used when implementing such systems.

Textbook: There is no textbook for this course. Readings are available on the Internet.

Outline: This course is organized as follows, though specific topics and dates may change. (Readings are listed in the right-most column.)

Part I: Introduction

1/10

About this Course

1/12

Review of OOP (and Java)

Review of Java

1/14

Review of Data Structures and Algorithms

Algorithms

Part II: Maps

1/19

Cartography and Remote Sensing

1/21-1/24

Vector Arithmetic: Introduction and Software Design Issues

1/26-1/28

Analytic Geometry: Introduction and Software Design Issues

1/31-2/2

Vector Graphics

2/4-2/9

Coordinate Systems: For \(\mathbb{R}^{2}\) , For \(\mathbb{R}^{3}\) and Software Design Issues

2/11-2/16

Map Projections: For a Spherical Planet

2/18

Exam 1

Part III: Location/Position Determination

2/21

Introduction

2/23

Event-Based Programming: The Observer Pattern and An Example

Observer

2/25-2/28

Data Acquisition: Checksums , Communications Ports and Software Design Issues

3/2-3/4

Partitioning Spatial Data: Introduction and Software Design Issues

3/14-3/18

The Global Positioning System , Triangulation Using Optimization: Part I and Part II

3/21

Exam 2

Part IV: Static Routing

3/23

An Introduction to Graphs and Modeling Road Networks

3/25

Routing Algorithms

3/28-4/4

Data Structures: Graphs , Routing , Trees and Heaps

4/6

Geocoding: Introduction and Text Matching

4/8

Design Issues

4/11

Review

Part V: Real-Time Routing

4/13

Computational Geometry: Metrics , Euclidean Calculations and Great Circle Distances

4/15

No Class -- ISAT Senior Project Presentations

4/18-4/20

Map Matching

4/22

Route Recalculation

4/25

Design Issues

4/27

Routing for En Route Commerce

4/29

Review

Attendance at lectures is not mandatory but is strongly encouraged. You are expected to come to class prepared to ask and answer questions. Hence, you should complete the readings on a topic before it is discussed in lecture.

Grading: Final grades will be based on your performance on: 2 in-class exams (25% each) , 1 final exam (25% total) and several programming assignments (25% total).

Programming Assignments: 5 programming assignments will be assigned during the semester. Note that their due dates are subject to change.

Programming Assignment 1 ; Due: 1/28 (Review)
Programming Assignment 2 ; Due: 2/16 (Maps)
Programming Assignment 3 ; Due: 3/16(Extended to 3/18) (Location/Position Determination)
Programming Assignment 4 ; Due: 4/6(Extended to 4/11) (Static Routing)
Programming Assignment 5 ; Due: 4/25(Extended to 4/29) (Real-Time Routing)

Make sure you read and understand all of the policies related to programming assignments.

Office Hours: You may meet with Prof. Bernstein during his scheduled office hours or you may schedule an appointment with him.