CMSI 182 -  Introduction to Computer Science

Final Exam Information

• Thursday, May 4th, 2000, 11am
• You must take the final exam in order to pass the course.
• consists of two parts:
• Part 1 (test 3) Study Guide
• chapter 11  Computer Communications
• chapter 12  Execution Time
• tractable problems: searching, sorting
• intractable problems: the Traveling Salesperson Problem, the Subset Sum Problem / Knapsack Problem, the Graph Coloring Problem
• chapter 13  Parallel Computation
• > 1 processor
• searching - get dramatic time improvement
•  the Traveling Salesperson Problem - runs faster but still is intractable
• communicating processes - lose some of the time improvement due to program complexity and waiting for locked resources
• deadlock - two processes each waiting forever for a resource that the other has
• unsaturated machines - usually get a good speedup
• saturated machines - speedup usually poor
• architectures - row, ring, grid, hypercube,  complete connection
• one way to increase the speed of a computation
• chapter 14  Noncomputability
• f is computable if there exists a program P that computes function f
• f is noncomputable if there does not exist a program P that computes function f; i.e., it is impossible to ever write program P
• there are noncomputable functions
• example of a noncomputable function - a function f that when given any program Q can answer the question "Does Q halt on all inputs?"
• another example of a noncomputable function - a function f that when given any program Q can answer the question "Does Q print something on all inputs?"
• other examples of a noncomputable functions - any function that must answer a question about the runtime behavior of arbitrary programs
• videos - The Machine That Changed the World
• especially major points and concepts
• Questions on the following bullets are highly likely.  The list is not exhaustive.
• The Paperback Computer - How computers became small, affordable, and easy to use
• The book evolved from rare and hugely expensive to commonplace and extremely cheap.  Similarly, the computer has evolved from a few multimillion dollar machines to 250 million machines, most of them fairly inexpensive personal computers.
• Bill Gates - founder of Microsoft, the largest maker of software for personal computers, both PC and Mac.
• Steve Jobs and Steve Wozniak - founders of Apple Computers, the maker in 1984 of the MacIntosh, the first user-friendly personal computer with a graphical user interface to be marketed to the public.
• Doug Englebart - visionary creator of an early interactive system that used a display screen and a mouse.
• The Altair - the first personal computer, a kit that was very popular with hobbyists
• virtual reality - uses a helmet, data glove, treadmill, etc. to put user into a 3D environment that is created by the computer
• The Thinking Machine - The Successes and Failures of Artificial Intelligence
• neural net driving a truck
• the Turing Test for machine intelligence
• Eliza - a program that mimics a therapist using parlor tricks; not a serious attempt at building an intelligent machine; more of an example of how unintelligent computers are
• early failures of AI - overly optimistic expectations of AI pioneers
• expert systems - used where deep but narrow knowledge in required; the first successful AI systems
• Ethics - "Computers are presenting new challenges to society.  The same free flow of information that aids law enforcement is beginning to cost us our privacy.  We meet one man who was mistakenly declared dead by a computer.  Ultimately it is up to us, as members of society, to play a role in directing applications of this new and powerful technology."
• The Future - "Where is this powerful technology taking us?  This module examines some old predictions about computer technology and makes comparisons with the development of another earth-shaking source of information, the book.  We see predictions of how computers might help us communicate and store information in the future."
• Part 2 (test 4)
• cumulative.  See the previous study guides, etc.
• no programs to write, but may have some questions about programming concepts, e.g.:
• What are the three control structures used in structured programming?  (answer: sequence, selection, and repetition)
• What should you do before writing a program?  (answer:  Write the algorithm.)
• study guide for test 2
• test 3 study guide (see above)