CS 180 Problem Solving and OO Programming

Report
CS 180 Problem Solving and Object Oriented
Programming
Fall 2011
http://www.cs.purdue.edu/homes/apm/courses/CS180Fall2011/
Notes for Week 1:
August 22-26, 2011
Revised: August 24, 2011
Aditya Mathur
Department of Computer Science
Purdue University
West Lafayette, IN, USA
About CS 180
8/22/11
CS 180. Fall 2011. Week 1
2
Course Web Site and Other Resources
Course Web site:
http://www.cs.purdue.edu/homes/apm/courses/CS180Fall2011/
Java Resources:
http://download.oracle.com/javase/1.4.2/docs/api/
http://download.oracle.com/javase/tutorial/
Technical Q&A via: www.piazza.com
Register your iClicker at
Blackboard by following the link “Register your iClicker”
8/22/11
CS 180. Fall 2011. Week 1
3
Please note….
Classes will begin at 3:30pm and end at 4:20pm. Please try to be
in your seat a few minutes before the class begins and leave after
the class ends.
All students are encouraged to ask questions. You may interrupt
the instructor at any time.
The instructor is here to help you learn. Make full use of the
instructor. Make full use of the instructor’s and GTAs office
hours.
I want you to succeed in this class and in your major. I will do all I
can to help you succeed; this is my primary responsibility as a
professor at Purdue.
8/22/11
CS 180. Fall 2011. Week 1
4
More “Please notes”….
College of Science has a Feast with Faculty program.
I will be available to have dinner with CS 180 students every
Wednesday at 6pm in Ford Dining Court, in the room on the
second floor.
Please join me when you have the time and we can discuss CS
180, Computer Science, Purdue, etc.
Sign-up sheets will be passed in recitation sections week-byweek.
8/22/11
CS 180. Fall 2011. Week 1
5
Assumptions
You have little or no expertise in computer programming using Java.
You are hard working.
You will not sleep during classes, an if you do, you will not snore!
You will not use phones during class and turn them off when you
enter the class and leave them off until the class is adjourned.
You will not disturb others by talking to your neighbors.
You will try to participate in the class by asking questions and
responding to questions asked by the instructor.
You will use iClickers in the class when requested.
8/22/11
CS 180. Fall 2011. Week 1
6
Impact of Assumptions
Some of you may get bored during the first four weeks of classes,
but others may find appealing the slow pace.
For those with some Java experience, we recommend participating in
the programming competition. Refer to the course web site for details.
Please buy an iClicker.
You should skip the class if you need to discuss important matters with your
friends. But skipping a class is not a good idea! So maybe you might consider
rescheduling the important matters with your friend.
8/22/11
CS 180. Fall 2011. Week 1
7
Expectations: Academic Honesty
Unless specified otherwise, all labs, projects, and exams
are to be completed by you without assistance from
anyone else other than the course instructor and the
graders.
Read the Policies page on the course web site.
8/22/11
CS 180. Fall 2011. Week 1
8
Expectations: Attendance
You will attend all lectures, labs, and recitations.
Attendance is not mandatory but highly recommended.
If you miss a lecture, lab or recitation then it is your
responsibility to (a) learn on your own the material
covered (b) find out if there were any announcements
that might affect your course grade.
8/22/11
CS 180. Fall 2011. Week 1
9
Textbook
Title
A Gentle Introduction to Concurrent Programming.
Authors
Barry Wittman, Aditya Mathur, and Tim Korb
Edition
Custom. Draft 4.0, 2011, Pearson Education
Avaialble at
Bookstores
Additional resource
iClickers
8/22/11
Java Tutorials on the Web
You may buy an iClicker from one of several local bookstores.
CS 180. Fall 2011. Week 1
10
Grading
Component
Weight (%)
Exam 1
10
Mon 10/3 08:00pm - 10:00pm
Exam 2:
15
Wed 11/09 08:00pm - 10:00pm
Lab exercises [14]
15
Homework [10]
5
Project 1 [Individual]
3
Project 2 [Individual]
4
Project 3 [Individual]
5
Project 4 [Team of 3]
8
Project 5 [Team of 3]
10
Final Exam
25
TOTAL
100
Relative grading (curved).
8/22/11
CS 180. Fall 2011. Week 1
11
Exams
You will be allowed to consult one book of your choice
during the exams.
8/22/11
CS 180. Fall 2011. Week 1
12
Want some challenge?
Programming competition exclusively for CS 180 students.
For details visit:
http://www.cs.purdue.edu/homes/apm/courses/CS180Fall2011/
ProgrammingCompetition.html
8/22/11
CS 180. Fall 2011. Week 1
13
Feedback
Weekly feedback: anonymous via iClickers
•
•
Tell us about the lectures, labs, recitations
How are we doing?
Weekly feedback: open
•
•
8/22/11
Tell us in an open forum what needs to improve.
Constructive criticism of the class is highly appreciated.
CS 180. Fall 2011. Week 1
14
Suggestions from students in Fall 2010
There appeared to be major disconnects between lecture
and labs.
I will try my best to ensure that this does not happen again.
There were also issues with grading projects.
We will ensure that project grading is standardized
across projects/sections.
I feel that the lab content needs to be better prepared ahead
of time.
All 14 labs and 5 project have been prepared during
summer.
8/22/11
CS 180. Fall 2011. Week 1
15
Suggestions from students in Fall 2010…
I wish he was better at explaining complicated topics.
Again, I will try my best to explain complex topics in clear
terms. Extra classes and my presence in recitation section
might also help.
Give students more time on the projects.
Will do but please make sure you start working on the
project soon after it is assigned.
Possibly give more assignments that are graded.
Yep! We have added homework to recitations.
8/22/11
CS 180. Fall 2011. Week 1
16
Suggestions from students in Fall 2010…
It would be nice if students knew ahead of time that most of
their classmates have had programming experience
Yes. But this class is for students with no programming
experience, those with a lot of experience have already
tested out of CS 180.
Make sure that the projectors work properly.
Will do.
The labs and projects seemed to be way too difficult for a
beginner class.
I hope you will have a different opinion this time, except
for Project 5!
8/22/11
CS 180. Fall 2011. Week 1
17
Suggestions from students in Fall 2010…
Make projects more difficult
Cannot do that, as this a beginning class. but one
project (Project 5) is quite challenging.
Some of the directions on projects were unclear
It would be much better this time.
There is only one thing that I want in this course to change
and that is focusing little more on basics.
Sure! Will do.
I wish Aditya would use a higher visibility laser pointer...
Let us try this one!
8/22/11
CS 180. Fall 2011. Week 1
18
Suggestions from students in Fall 2010…
Aditya has an fairly strong accent. There's no getting around
that fact, however he was still very understandable due to
his engaging personality and was still easily the best lecturer
I had this semester and one of the best overall.
Please please please…Interrupt me when you cannot
understand me!
8/22/11
CS 180. Fall 2011. Week 1
19
Week 1: August 22-26, 2011
What is Computer Science?
8/22/11
CS 180. Fall 2011. Week 1
20
Computer Science...
…started in the 60’s. Purdue claims to have the first CS department
in the USA….Stanford started CS a few years later…
…Grew out of Mathematics….primarily numerical computing, or
Electrical Engineering..
…since inception it has evolved into a new kind of engineering
discipline that, like other engineering, pervades nearly all fields of
human activity..
…students learn both hardware and software [Purdue is an exception
where students learn CS only in the College of Science, but we are
trying to change this by attempting to offer CS as an option to
engineering students]…
8/22/11
CS 180. Fall 2011. Week 1
21
Computer Science department(s)...
…are at nearly all major universities and colleges
…are mostly in Engineering colleges (MIT, Berkeley, Stanford,
Princeton, Michigan, Illinois, etc.) and offer students opportunities to
interact with other engineering and science disciplines….
…at Purdue is in the College of Science that denies students
opportunities available to students at top schools where
engineering, science, and liberal arts students are able to learn
Computer Science in the environment of heir choice…
8/22/11
CS 180. Fall 2011. Week 1
22
Computer Science...
…is an engineering discipline just as Mechanical Engineering,
Electrical Engineering, Biomedical Engineering,…
…educates and trains students to work as software engineers,
information security specialists, systems engineers,….
…deals with software that drives a large number of devices and
systems that we use in our day to day lives,…
…consists of subfields such as algorithms, artificial intelligence,
computational science and engineering, databases, graphics and
visualization, information retrieval, information security, machine
learning, modeling and simulation, networking, programming
languages and compilers, software engineering,…
8/22/11
CS 180. Fall 2011. Week 1
23
Computer Scientists...
…develop software that drives consumer devices such as smart
phones, TVs, stereo systems,…
…develop software systems that control and manage aircrafts,
automobiles, health care networks, power grids, intelligent
transportation systems,…
…develop systems software such as compilers, operating systems,
databases, and search engines on which are built a myriad of other
user applications,….
…work alongside engineers to develop software that drives devices
such as smart phones or more complex systems such as aircrafts,…
8/22/11
CS 180. Fall 2011. Week 1
24
Week 1: August 22-26, 2011
Readings And Learning Outcomes
8/22/11
CS 180. Fall 2011. Week 1
25
Readings and Exercises from the textbook:
Week 1
Your are expected to know well different number
systems. If you are not sure how much and how well you
know this subject, please read through Chapter 1.
In addition, read:
Chapter 2: 2.1, 2.2
and
Solve: 2.3, 2.4, 2.7, 2.11, 2.14, 2.26
8/22/11
CS 180. Fall 2011. Week 1
26
Learning Outcome-1
Through a sequence of well defined steps you will be
able to map a problem statement presented in natural
language to a computer program written in the Java
programming language.
8/22/11
CS 180. Fall 2011. Week 1
27
Learning Outcome-2
You will learn the basics of computer programming that
will aid you in learning programming languages other
than Java. Some of these other languages include C#,
Python, C, and C++.
8/22/11
CS 180. Fall 2011. Week 1
28
Learning Outcome-3
You will learn the differences between sequential and
concurrent solutions to given problem. This will allow
you to write concurrent programs that exploit the power
of multi-core microprocessors.
8/22/11
CS 180. Fall 2011. Week 1
29
Learning Outcome-4
You will learn about Computer Science as a discipline.
This will help you decide whether or not Computer
Science is for you!
8/22/11
CS 180. Fall 2011. Week 1
30
Learning Outcome-5
You will learn how to use DrJava to edit, compile, debug,
and execute Java programs.
8/22/11
CS 180. Fall 2011. Week 1
31
Learning Outcome-6
You will learn how to program Finch robots using Java.
8/22/11
CS 180. Fall 2011. Week 1
32
Learning Outcome-7
You will learn the basics of how to program Androidbased smart phones using Java.
8/22/11
CS 180. Fall 2011. Week 1
33
Learning Opportunities in CS 180
Lectures: Basic concepts and techniques
Labs: Practice solving simple problems on the computer;
use robots and smart phone in addition to desktops.
Recitations: Practice solving simple problems by hand;
lots of discussion and participation; work in small teams.
Projects: Solve more complex problems; design,
implement, test, document.
8/22/11
CS 180. Fall 2011. Week 1
34
Learning in CS 180: Prerequisite
Desire to learn and the ability to work hard.
8/22/11
CS 180. Fall 2011. Week 1
35
Learning in CS 180
Practice, practice and practice
You will write programs that do not compile at first
And when they compile they do not run as expected
And when they run as expected, you scream Yippee!
So do not be discouraged by errors, these are a part of
life’s challenges; overcome them! We are here to help
you.
8/22/11
CS 180. Fall 2011. Week 1
36
Week 1: Lecture 2
August 22-26, 2011
Problem Solving and OO Programming
8/22/11
CS 180. Fall 2011. Week 1
37
iClicker check
Q: I am
(a) A CS major
(b) Not a CS major
8/22/11
CS 180. Fall 2011. Week 1
38
iClicker check
Q2: Assuming that 1: I know very little and 10 I consider myself to be
pretty good in programming using Java, I rate my proficiency in Java
programming as
(a) 8-10
(b) 5-7
(c) 2-4
(d) 1
8/22/11
CS 180. Fall 2011. Week 1
39
What is “problem solving?”
“Problem solving” refers to a set of activities
performed in order to solve a given problem.
This is a generic term and applies to all
disciplines, not only to Computer Science.
Sequence of steps for solving a problem as
proposed by George Polya in the 1950’s :
Understand the problem
Devise a plan [Design]
Execute the plan [Code,
Test etc]
Review solution
8/22/11
CS 180. Fall 2011. Week 1
40
What is OO programming?
OO, or Object Oriented, programming refers to a set of
activities that lead to a computer program, written in an
object-oriented language, that when executed on a
computer will solve a problem.
Java is an OO language used in CS 180.
Other OO languages include C++, C#, Delphi, Modula,
Oberon, Objective C, Simula, Smalltalk, and many more!
8/22/11
CS 180. Fall 2011. Week 1
41
What is Problem solving and OO programming?
Problem solving and OO
programming refers to a set of
activities that allow the mapping of
a problem to a computer program,
written in an object-oriented
language, that when executed on a
computer will solves the problem.
Understand the problem
Design a solution using objects
Implement the design in
An OO language
Test, debug, and correct
the program
42
8/22/11
CS 180. Fall 2011. Week 1
What is a multi-core microprocessor?
A multi-core microprocessor is a microprocessor chip that contains
two or more cores. Each core is capable of executing its own
sequence of instructions.
A dual-core microprocessor contains 2-cores. A quad-core
microprocessor contains 4-cores, and so on.
8/22/11
CS 180. Fall 2011. Week 1
43
What is a parallel computer?
A computer capable of executing two or more programs in parallel is
often referred to as a parallel computer.
A computer containing a multi-core microprocessor is a parallel
computer.
A computer containing two or more single-core microprocessors is
also a parallel computer.
Nearly every desktop and laptop today is a parallel computer
containing a multi-core microprocessor.
8/22/11
CS 180. Fall 2011. Week 1
44
What is a sequential program?
A sequential program is one that is executed by a computer in a
strict sequence, one instruction at a time. Thus, every instruction in
the program is executed strictly in the specified sequence.
8/22/11
CS 180. Fall 2011. Week 1
45
What is a concurrent program?
A concurrent program is one that contains instructions that may be
executed in parallel, or concurrently, by a parallel computer.
A concurrent program written in Java contains two or more threads.
Each thread may be executed concurrently on a parallel computer.
8/22/11
CS 180. Fall 2011. Week 1
46
Example 1: Problem solving
Problem:
Find the maximum in a given set of N integers.
Step 1: Understand the problem
1. We know what is a set, an integer and what does
“maximum” mean.
2. Can N be zero? Can N be negative? We assume that N>0.
3. Suppose the given set is: {4, -5, 29, 4}. N=4.
4. The maximum in this set is 29.
8/22/11
CS 180. Fall 2011. Week 1
47
Example 1: Problem solving: Sequential program
Pictorial representation of a sequential algorithm:
Sequential
computation
Input: Given set
Find the maximum
Output: max integer in S
8/22/11
CS 180. Fall 2011. Week 1
48
Example 1: Sequential program
Step 2: Design a sequential solution
1. Let S denote the given set.
2. Let S.next() denote the next element from the set. S.next()
is empty if we have examined all elements of S.
3. Let currentMax=S.next();
4. Scan each element of S until we have scanned all. The
following two steps are performed for each element in S
starting from the second.
a) Let newElement=S.next();
b) If currentMax<newElement then reset currentMax to
newElement;
5. Display currentMax, it is the desired maximum.
8/22/11
CS 180. Fall 2011. Week 1
49
Example 1: Sequential program
Step 3: Implement the design as a well documented program in an
OO language
We will write a Java program later in this course.
Step 4: Test, debug, and correct the program
We will do this after we have written the program.
8/22/11
CS 180. Fall 2011. Week 1
50
Example 1: Problem solving: Parallel program
Problem:
Find the maximum in a given set of N integers.
Step 1: Understand the problem
1. We know what is a set, an integer and what does
“maximum” mean.
2. Can N be zero? Can N be negative? We assume that N>0.
3. Suppose the given set is: {4, -5, 29, 4}. N=4.
4. The maximum in this set is 29.
5. We can divide S into disjoint sets S1 and S2 such that their
union is S.
6. For example, S1={4, -5}, S2={29, 4}. Maximum of S1 is 4 and
of S2 is 29. The maximum of these two maximums is 29
which is the desired maximum.
8/22/11
CS 180. Fall 2011. Week 1
51
Example 1: Problem solving: Parallel program
Pictorial representation of the parallel algorithm:
Sequential
computation
Input: Given set
Split into S1 and S2
such that S=S1 U S2
Parallel
computation
Find max of each set
using sequential
method.
Find max of max of
each set.
Sequential
computation
Output: max integer in S
8/22/11
CS 180. Fall 2011. Week 1
52
Example 1: Problem solving: Parallel program
Step 2a: Design a concurrent solution assuming a dual core machine
is to be used for executing this solution.
1.
2.
3.
4.
5.
6.
8/22/11
Let S denote the given set.
Let S.next() denote the next element from the set. S.next()
is empty if we have examined all elements of S.
Divide S into sets S1 and S2 such that S=S1 U S2
Let maxS1= max(S1) and maxS2=max(S2).
Let max be the larger of maxS1 and maxS2
max is the desired maximum.
CS 180. Fall 2011. Week 1
53
Example 1: Problem solving: Parallel program
Step 2b: Design a concurrent solution: max(S) denotes the maximum
of integers in set S.
1. Let S.next() denote the next element from the set. S.next()
is empty if we have examined all elements of S.
2. Let currentMax=S.next();
3. Scan each element of S until we have scanned all. The
following two steps are performed for each element in S
starting from the second.
a) Let newElement=S.next();
b) If currentMax<newElement then reset currentMax to
newElement;
4. currentMax, is the desired maximum.
8/22/11
CS 180. Fall 2011. Week 1
54
Example 1: Problem solving: Parallel program
•
How many threads of computation do you see in our solution?
•
What does each thread do?
•
Will a thread wait? Why and when?
8/22/11
CS 180. Fall 2011. Week 1
55
Why parallel program?
For faster solution to a problem.
Example: search the entire internet for a keyword.
For quick response to a request.
Example: Customer request for bank balance.
8/22/11
CS 180. Fall 2011. Week 1
56
Example 2: Manipulating music
For faster solution to transposition to a different key. Each core
transposes one or more tracks.
For playing multiple tracks at the same time. Each core plays one of
more tracks and the audio is combined by one core.
8/22/11
CS 180. Fall 2011. Week 1
57
Example 3: Problem Solving
Problem:
Given real numbers a, b, and c, compute the value of the following
expression:
(b * b - 4 * a * c)
Step 1: Understand the problem
This one is easy! So let us say we have understood the problem!
8/22/11
CS 180. Fall 2011. Week 1
58
Example 3: Problem Solving: Sequential Solution
Step 2: Design a sequential solution
1: Get a, b, and c.
2: Compute x=b*b
3: Compute y=4*a*c
4: Compute z=x-y
5: Compute p= z
6: Output p
8/22/11
CS 180. Fall 2011. Week 1
59
Example 3: Problem Solving: Parallel Solution
Problem:
Given real numbers a, b, and c, compute the value of the following
expression:
(b * b - 4 * a * c)
1: Compute x=b*b and y=4*a*c in parallel.
3: Compute z=x-y
4: Compute p= z
5: Output p
8/22/11
CS 180. Fall 2011. Week 1
60
Example 3: Problem solving: Parallel program
Pictorial representation of the parallel algorithm:
Sequential
computation
Input: Given numbers
Parallel
computation
Compute subexpressions
Compute another,
dependent, sub-expression
Sequential
computation
z
Compute the square root
Output: value of the given
expression
8/22/11
CS 180. Fall 2011. Week 1
61
Example 3: Problem solving: Parallel program
•
How many threads of computation do you see in our solution?
•
What does each thread do?
•
Will a thread wait? Why and when?
8/22/11
CS 180. Fall 2011. Week 1
62
Discussion
What differences do you notice in the two problems?
What impact would these differences have on a concurrent solution?
We solved the problem assuming a dual core computer. Would your
solution be different of it were to for a quad-core computer?
A concurrent program consists of sequential and concurrent steps.
Why? What impact do these steps have on the total time to solve a
problem on a multi-core computer?
8/22/11
CS 180. Fall 2011. Week 1
63
Two types of parallelism
Data parallelism:
Distribute data across cores; all cores perform the same
computation
Task Parallelism:
Distribute tasks across cores; tasks might act on the same or
data.
Data and Task Parallelism:
Distribute tasks across cores; tasks might act on different data.
8/22/11
CS 180. Fall 2011. Week 1
64
Example 4: Rental car reservation
Problem:
Develop a program that will allow customers to reserve rental car.
Question:
Should this be a sequential or a concurrent program? Why?
In case it is a concurrent program, what form of parallelism do you
think it will use?
8/22/11
CS 180. Fall 2011. Week 1
65
Example 4: Sorting data
Problem:
Develop a program that will sort a given set of data.
Question:
Should this be a sequential or a concurrent program? Why?
In case it is a concurrent program, what form of parallelism do you
think it will use?
8/22/11
CS 180. Fall 2011. Week 1
66
Week 1: August 22-26, 2011
Java program compilation
8/22/11
CS 180. Fall 2011. Week 1
67
The edit, compile, execute cycle
.java file(s)
Edit a
Java program
.class file(s)
Compile your
program
Syntax
error
No syntax
error
Program correct
Execute your
program
Run time
Error or incorrect
output
In CS 180 we shall use DrJava for editing, compiling and execution. DrJava is an
Integrated Development Environment also known as an IDE. Eclipse, JBuilder, and
IntelliJ IDEA are a few other Java IDEs.
8/22/11
CS 180. Fall 2011. Week 1
68
Elements of a Sequential Java Program
Program to be dissected: Program 2.4 in Chapter 2 pages 45-46.
Go through this program line by line and understand the meaning of
each line.
8/22/11
CS 180. Fall 2011. Week 1
69
Elements of a Concurrent Java Program
Program to be dissected: Program 2.7 in Chapter 1 pages 58-59.
Go through this program line by line and understand the meaning of
each line.
8/22/11
CS 180. Fall 2011. Week 1
70
Week 1: August 22-26, 2011
Hope you enjoyed this week!
8/22/11
CS 180. Fall 2011. Week 1
71

similar documents