We will e u access to 1.00 Web site1/31/2010 1.204 Lecture 1 Course introduction Dt dl Data models Announcements • How-to install documents on Web: – Java, Eclipse, submit problem sets (1.00 Web site) – SQL Server, Visual Paradigm, JDBC (1.204 Web site) • We will give you access to 1.00 Web siteyogiv – Sign up as 1.00/1.001 listener if you plan to sit in on 1.001 • Software installation help – Email me with questions or to set up a time for help • MySQL: Mac users can use MySQL to avoid Boot Camp, etc. – No support for MySQL installation problems • Homework 0: Software installation, due Mon Feb 8. Ungraded. • Homework 1: Air schedule,, due Tue Feb 16. Graded. – Initial modeling/coding exercise, using straightforward solutionmethod – Homework 1 only: You may code in a language other than Java • Lecture notes: Printed notes handed out each lecture • Readings: On reserve at Barker, and on electronic reserve 1orge ) (1/31/2010 Course outline • Staff: – GeGeorge Kocur Kocur -• Class Monday, Wednesday 1-2:30pm • Office hours – George Kocur MW4:45-5:45 • Prerequisite: 1.00/1.001/6.005. – Can listen to 1.00 this semester • Grading: – 7 homework sets (70%)– 2 quizzes (30%) • Bring your laptop to office hours for help – Not needed in class, though you’re welcome to bring it Topics • Databases – Data modeling, normalization – SQL, JDBC • Data structures – Stacks, queues, trees/dictionaries, heaps, sets, graphs • Divide and conquer, greedy models – Sorting, selection – Knapsack, job scheduling, spanning trees, shortest paths • Dynamic programming – Resource allocation, job scheduling, knapsack • Branch and bound – Knapsack, facility location • Linear/nonlinear systems, linear programming – Nonlinear optimization, constrained and unconstrained – Network equilibrium (convex combinations), choice estimation – Solution of linear systems, linear programming • Approximate queuing theory – Time-varying queues, deterministic queues, graphical methods 21/31/2010 Homework • Homework topics 1. Informal algorithm design (warm-up homework) 2. Database 3. Network data structure 4. Greedy algorithm 5. Network algorithm 6. Dynamic programming 7. Branch and bound 8. Nonlinear optimization • Work individuallyWork individually – You may discuss approach to homework with others – You must write your own Java and SQL code – Please read Academic Honesty Guidelines in FAQ • Create one Eclipse project for the whole term – Create src.xxx packages for each lecture, homework Readings, computer systems • Readings (some on electronic reserve) are sections from these books: – Computer Algorithms in C++ (2nd ed), Horowitz, Sahni, Rajasekaran – Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein – Bigg Java,, Horstmann – Murach’s SQL Server 2008 for Developers, Syverson, Murach – JDBC API Tutorial and Reference, Fisher, Ellis, Bruce – Applications of Queuing Theory, Newell – Linear Programming, Chvatal – Numerical Recipes, Press et al (2nd or 3rd edition) – Urban Transportation Networks, Sheffi • Use your own laptop or desktop computer – All software available for download – Either open source or free – TA will help with installation and initial usage • 1.204 site on Stellar (stellar.mit.edu) – Lecture notes – Homework – Electronic reserve, online readings – Announcements 3Method to discover the and1/31/2010 Data models • Data model is representation ofData model is representation of – Things (or entities or classes) of importance to a system – How the things relate to each other • It is built and modified until it represents the system well enough to support a system model • Data models are extended to become class diagrams in the Unified Modeling Languagediagrams in the Unified Modeling Language [UML] by adding the behaviors of each entity to the model Logical data modeling • Method to discover the data, relationships anddata, relationships rules of a system, collectively called the system rules • Logical data models are the basis of: – Physical data models, or actual databases – Applications, parts of which can be automaticallygenerated from the data model •• Small model for aircraft Small model for aircraft – Says a lot about system structure – Gives good picture of what database should look like – Also gives good picture of underlying system rules 41/31/2010 Aircraft Data Model Aircraft System Rules • An aircraft can be in many categories • A category can be associated with manyy aircraftgy • An aircraft model is built by one aircraft manufacturer • An aircraft manufacturer builds many aircraft models • An aircraft model is of one type • An aircraft type can be associated with many aircraft models • An engine type can be represented by many engine models • Each engine model is of one engine type • An aircraft model has one engine typeAn aircraft model has one engine type • An engine type may be in many aircraft types • An aircraft has one engine model (it may have >1 engine) • An engine model may be in many aircraft • An engine manufacturer builds many engine models • An engine model is built by one engine manufacturer 5•1/31/2010 Data model purpose • Enggineer needs to build loggical data model so users and engineers both understand system rules – Models enable users and developers to have single view of system – Sometimes users note this is first time they understood system rules! • Converting logical to physical data model (database) is verystraightforward these days. – Little need for sepparate pphyysical model for online databases – Create integer system-generated keys instead of strings andcomposite keys for performance – We still create separate physical models for data warehouses, read-only databases and some other special cases • Model also serves as basis of class diagram for code Data modeling concepts • Entities (classes Entities (classes, tables)tables) • Attributes (properties) • Relationships • Keys (primary and foreign) • Referential integrity 61/31/20107Entity type and entity occurrenceEntity type Entity occurrenceDeptNbrDeptNameDeptTypeDeptStatusDepartmentDeptNbr DeptName DeptType DeptStatus930 Receiving Mfg Active378 Assembly Mfg Active372 Finance Adm