CSci 41

Introduction to Computer Science


Fall 2000

Main Lecturer: Michael Feldman, Professor, Dept. of Comp. Sci.
Office: Academic Center, Room T-715
Office Hours: T-Th 2 - 3:30 PM, W 2 - 5:30 PM,
Phone: 994-5919 (e-mail is better, though!)

E-mail: mfeldman@seas.gwu.edu
Lecturer website: http://www.seas.gwu.edu/~mfeldman
Course website: http://www.seas.gwu.edu/~csci41/fall00

Course schedule will be discussed in lecture on Wed., Oct. 25.
The course website will be operational at that time.

Today's subject: Curriculum and Registration


Laboratory Instructors


What Is Computer Science?


“Computer science is a discipline that involves the understanding and design of computers and computational processes. In its most general form it is concerned with the understanding of information transfer and transformation.

“A central focus is on processes for handling and manipulating information. Thus, the discipline spans both advancing the fundamental understanding of algorithms and information processes in general as well as the practical design of efficient reliable software and hardware to meet given specifications.”

source: Computing Sciences Accreditation Board (CSAB), “Defining the Computing Sciences Professions”, http://www.csab.org/comp_sci_profession.html


What Is a Computer Scientist?


“A well educated computer scientist should be able to apply the fundamental concepts and techniques of computation, algorithms, and computer design to a specific design problem.

“The work includes detailing of specifications, analysis of the problem, and provides a design that functions as desired, has satisfactory performance, is reliable and maintainable, and meets desired cost criteria.

“Clearly, the computer scientist must not only have sufficient training in the computer science areas to be able to accomplish such tasks, but must also have a firm understanding in areas of mathematics and science, as well as a broad education in liberal studies to provide a basis for understanding the societal implications of the work being performed.”

source: ibid.


University Computer Science Curricula

Subjects Studied in the GW CS Curricula

CS department website: http://cs.seas.gwu.edu


BS Required (plus 2 electives)

Intro to Computer Science (41)
Intro to Software Development (51)
Technology and Society (110)
Computer Organization (135)
Discrete Mathematical Structures (123)
Algorithms and Data Structures I (131)
Software Engineering I (141)
Software Paradigms (169)

Computer Architecture (136)
Algorithms and Data Structures II (151)
Software Engineering II (161)
Operating Systems Design (156)
Foundations of Computing (150)
Computer Translators (160)
Computer Networks (2 semesters) (183-4)
Database Systems (178)
Senior Design Project (2 semesters) (195-6)

BA Required (plus 3-5 electives)

Intro to Computer Science (41)
Intro to Software Development (51)
Technology and Society (110)
Computer Organization (52)
Discrete Mathematical Structures (123)
Algorithms and Data Structures I (131)
Software Engineering I (141)
Software Paradigms (169)

Additional Electives (BS and BA)

Artificial Intelligence (174)
Computer Animation (181)
Computer Graphics (185)
Numerical Methods (173)
User-Interface Development (187)
Real-Time Systems (190)
Simulation Methods (186)


Computer Science Minor


In GW terminology,
 

CSci Secondary Field Required (minor is similar)

Intro to Computer Science (41)
Intro to Software Development (51)
Algorithms and Data Structures I (131)
Software Engineering I (141)

(plus Math 21 or 31 and 2 CSci electives)


Inter-School Dual Majors:
Computer Science and ??

If you are a SEAS undergrad, there is an automatic "advising hold" on your registration every semester.

The registration process is:
 

  1. Complete a SEAS Undergraduate Advising Form with your course selections.
  2. Visit your advisor (currently Prof. Feldman or Prof. Meltzer) to discuss your program and obtain an advisor' signature on the form.
  3. Take the form to the SEAS Student Records Office, Tompkins 103. They will remove the advising hold.
  4. Complete your registration by web or phone.


It is in everyone's interest for you to register each semester during the early registration period. Do not wait till the next semester!


Course Website:


http://www.seas.gwu.edu/~csci41/fall00
 
 

Course Mailing List:

csci41@lyris.seas.gwu.edu

I have sent a message to this list. Please check your SEAS mail today, and e-mail me to indicate whether you got this message.
 
 
 
 

Assignment for Week of Oct. 23, 2000


READ Chapter 1 of textbook to get ready for lab on Friday.
Prof. Feldman's Computing History

Algorithms:
the Foundation of Systematic Problem-Solving

"algorithm, a finite collection of simple instructions that can be performed by a computer and is guaranteed to halt in a finite amount of time."

source: The Analytical Engine, p. 26

QUESTION: Suppose a program is designed not to halt in a finite amount of time? Is it implementing an algorithm?


Algorithms:
the Foundation of Systematic Problem-Solving

"algorithm A rigid mathematical (or logical) relationship which has only one starting point and one finishing point. ... Each algorithm must have a finite list of executable instructions which must eventually come to an end.

"The British mathematician Alan Turing proved [1936] that an algorithmic approach can be used to solve any mathematical or logical problem for which a solution is known to exist. This means that one can deduce that any solvable problem can be handled by a computer, provided the correct algorithm is used.

"In computing, an algorithm is the plan, routine, or process of defining a set of instructions so that a computer program can be written to find the answer / solution to a given problem or task."

source: Prentice-Hall's Illustrated Dictionary of Computing (3rd ed.) (Prentice-Hall, 1998), p. 19


Developing an Algorithm


Problem Specification. You are driving a car with two friends and suddenly get a flat tire. Fortunately, there is a spare tire and jack in the trunk.

Analysis. After pulling over to the side of the road, you might decide to subdivide the problem of changing a tire into the subproblems below.

Design. Here are the main steps in an algorithm to change a tire.

Algorithm.
1. Loosen the lug nuts on the flat tire; don’t remove them yet.
2. Get the jack and jack up the car.
3. Remove the lug nuts from the flat tire and remove the tire.
4. Get the spare tire, place it on the wheel, and tighten the nuts.
5. Lower the car.
6. Secure the jack and flat tire in the trunk.

Because these steps are relatively independent, you might decide to assign subproblem 1 to friend A, subproblem 2 to friend B, subproblem 3 to yourself, and so on. If friend B has used a jack before, the whole process should proceed smoothly; however, if friend B does not know how to use a jack, you need to refine step 2 further.

Step 2 Refinement
2.1. Get the jack from the trunk.
2.2. Place the jack under the car near the flat tire.
2.3. Insert the jack handle in the jack.
2.4. Place a block of wood under the car to keep it from rolling.
2.5. Jack up the car until there is enough room for the spare tire.

Step 2.4 requires a bit of decision making on your friend’s part. Because the actual placement of the block of wood depends on whether the car is facing uphill or downhill, friend B needs to refine step 2.4.

Step 2.4 Refinement

2.4.1 If the car is facing uphill, then place the block of wood in back of a tire that is not flat; if the car is facing downhill, then place the block of wood in front of a tire that is not flat.

This is actually a conditional action: One of two alternative actions is executed, depending on a certain condition.

2.4.1 If the car is facing uphill, then place the block of wood in back of a tire that is not flat.

2.4.2 If the car is facing downhill, then place the block of wood in front of a tire that is not flat.

QUESTION: What if the car is on flat ground?

Finally, step 2.5 involves a repetitive action: moving the jack handle until there is sufficient room to put on the spare tire. Often, people stop when the car is high enough to remove the flat tire, forgetting that an inflated tire requires more room. It may take a few attempts to complete step 2.5.

Step 2.5 Refinement.

2.5.1. Move the jack handle repeatedly until the car is high enough off the ground that the spare tire can be put on the wheel.


Evolution of Computers


Von Neumann's Masterpiece:
the Stored-Program Digital Computer

Code Symbolic form
16 ADD #670 ACC + 670 -> ACC
17 SUB #235  ACC - 235 -> ACC
18  MUL #160 ACC - 160 -> ACC
19 DIV #160 ACC / 160 -> ACC
20 LOD #265 number 265 -> ACC
4 LOD P contents of loc. P -> ACC
5 STO Y ACC -> loc. Y
0 ADD T ACC + contents of loc. T -> ACC
1 SUB W ACC + contents of loc. W -> ACC
2 MUL D ACC * contents of loc. D-> ACC
3 DIV Q ACC / contents of loc. Q -> ACC
12 JMP R Get next instruction from loc. R
13 JMZ S If ACC = 0, go to loc. S, 
otherwise go to next instruction
14 NOP Do nothing; just go to next instruction
15 HLT Halt execution; do nothing more