Transcript Introduction - Computer Science

1
WEEK 1
CS 361: ADVANCED DATA STRUCTURES AND
ALGORITHMS
Dong Si
Dept. of Computer Science
2
Welcome to CS 361
• Instructor: Dong Si
• PhD candidate of Computer Science
• Joined ODU in 2009, probably this is my last semester
• Research interests: 3D image processing, feature detection, pattern
recognition, modeling & simulation, machine learning and
bioinformatics
• Office: ECSB 3318
• E-mail: [email protected]
• Office Hours: M&W, 11:00am-12:00pm or by appointment
• Textbook: Mark Allen Weiss , Data Structures and Algorithm Analysis
in C++ (4th edition)
3
Prerequisites
• CS 250, Problem Solving and Programming, or CS 333, Problem
Solving and Programming in C++
• I will assume that you are familiar with the basics of C++
including:
 the various C++ statements and control-flow constructs,
 the built-in data types,
 the use of arrays, vectors and linked lists,
 the use and writing of functions, and
 the basic use of structures and classes for implementing abstract data types.
4
Alert from Blackboard system
5
First things first
• Read the syllabus CAREFULLY and let me know if any question.
• Class materials will be distributed via Blackboard system and
class homepage (http://www.cs.odu.edu/~dsi/teaching_stuff/CS361).
Please check regularly for update.
• Read the readings list before each class. Slides will be posted
before of the class time.
• Class attendance is mandatory. Although slides will be used
occasionally to aid the lectures, the instructor will use the white board
heavily. Therefore, class attendance and interaction are required.
Please check the University’s rule of Absences.
6
First things first (cont.)
• Setup your
 ODU ITS account (for BlackBoard),
 CS account (for access the CS dept. computing resource) and
 Get familiar with CS Dept’s Linux servers (all your work will be tested on
these machines) and g++ compiler.
http://www.cs.odu.edu/
System Group :
[email protected]
7
Course policy
8
Course policy
Please read the syllabus CAREFULLY and let me know if any question.
9
Course overview
• You will learn
 Commonly used data structures and algorithms,
 Costs and benefits associated with each data structure,
 How to measure the effectiveness of a data structure or algorithm.
10
Programming
• Program = Algorithm + Data Structure + Implementation
• Algorithm: a sequence of steps to perform certain tasks
 E.g., sorting, shortest path
• Data structures: systematic ways of organizing and accessing data
 E.g., arrays, linked list, trees, graph
• Efficient Program = Good algorithm + Good data structures
1. How do we design the steps so that we can solve the
task effectively?
2. How do we organize data so that we can find, update,
add, and delete portions of it efficiently?
11
Example applications
1.
How does Google quickly find web pages that contain a search
term? Answer
2.
How can a subsequence of DNA be quickly found within the
genome? Answer
3.
How does your operating system track which memory (disk or
RAM) is free? Answer
4.
How to generate a Maze game? Answer, Example implementation
5.
Etc…
12
Data structures
• We need to define
 How to store data in memory,
 What operations we can perform on that data,
Abstract Data Types
(ADT)
 What changes in the data of the structure caused by the operation,
 What is the time/space efficiency for those operation.
• Ex. “vector” in C++ ADT:
 Objects are stored sequentially in memory
 Can access, change, insert or delete objects
 Operations for insert & delete will shift items as needed
 Space: O(n), Access/change = O(1), Insert/delete = O(n)
13
Abstract Data Type (ADT)
• An abstract model that specifies the structure type used to store the
data and the operations that support the data
• Abstract?
 Encapsulate data and functions that work with this data type,
 Implementation-independent view of the data structure,
 Interested in what the structure does and not how it does it,
• Operations?
 A process that can accept data values (arguments), execute
calculations, and return a value.
14
ADT example
• “Dictionary” class:
Member functions
Call the member functions in main program
15
My view of data structures and algorithms
Programming:
Java, C/C++, OOP,
Class, etc.
Data structures &
algorithms
Solving real-world
problems
How to systematically manipulate the data to achieve your goal?
How to systematically organize your data to make operations on the
data efficient?
 No single data structure works for all operations
 Which data structures are efficient for which situation?
16
Software design overview
• A computer program begins with a problem that the client wants
solved.
• The process of building the program starts with an analysis of the
problem.
 It proceeds through a series of stages to produce a product that is reliable
and easy to maintain.
17
Software development life cycle
• Programmers added code to software with little attention to its
integration into the system.
• Over time systems deteriorated and became so difficult to update that
programmers had to develop new software to replace them.
18
Software Design Stages
• Request:
 Client perceives a need for a software system to solve a problem.
 A computer consultant undertakes a feasibility study for the project.
• Analysis:
 A systems analyst develops the requirements of the system and
creates a functional specification that includes a list of needs and
special requirements.
• Design:
 Translate the functional specification into an abstract model of the
system.
 Identify the components of the system and develop algorithms
that will be used for implementation.
19
Software Design Stages (cont.)
• Implementation:
 Use a programming language and the design specification to code
the different components of the system.
• Testing:
 Check the program for logical and runtime errors and verify that the
system meets the specifications of the client.
• Maintenance:
 Periodically update of the software to stay current and to respond to
changing needs of the client.
20
Homework #1: Warming up
• Already assigned on BB, due on 9/3/2014, 11:59PM
• Make sure you have your computer accounts in working order
• Will not be graded, but if you do not submit, your homework grade (50
points) will be deducted by 5 points
21
Reading & Next class
• Book Chapter 1: “Programming: A General Overview”
• Book Chapter 2: “Algorithm Analysis”
• Next class: Algorithm, Complexity and Big O Analysis
• Remember: No class this Wednesday due to my conference
traveling.