2nd Edition
Discovering Computer Science Interdisciplinary Problems, Principles, and Python Programming
"Havill's problem-driven approach introduces algorithmic concepts in context and motivates students with a wide range of interests and backgrounds."
-- Janet Davis
, Associate Professor and Microsoft Chair of Computer Science, Whitman College"This book looks really great and takes exactly the approach I think should be used for a CS 1 course. I think it really fills a need in the textbook landscape."
--
Marie desJardins, Dean of the College of Organizational, Computational, and Information Sciences, Simmons University"Discovering Computer Science is a refreshing departure from introductory programming texts, offering students a much more sincere introduction to the breadth and complexity of this ever-growing field."
--
James Deverick, Senior Lecturer, The College of William and Mary"This unique introduction to the science of computing guides students through broad and universal approaches to problem solving in a variety of contexts and their ultimate implementation as computer programs."
--
Daniel Kaplan, DeWitt Wallace Professor, Macalester CollegeDiscovering Computer Science: Interdisciplinary Problems, Principles, and Python Programming
is a problem-oriented introduction to computational problem solving and programming in Python, appropriate for a first course for computer science majors, a more targeted disciplinary computing course or, at a slower pace, any introductory computer science course for a general audience.Realizing that an organization around language features only resonates with a narrow audience, this textbook instead connects programming to students’ prior interests using a range of authentic problems from the natural and social sciences and the digital humanities. The presentation begins with an introduction to the problem-solving process, contextualizing programming as an essential component. Then, as the book progresses, each chapter guides students through solutions to increasingly complex problems, using a spiral approach to introduce Python language features.
The text also places programming in the context of fundamental computer science principles, such as abstraction, efficiency, testing, and algorithmic techniques, offering glimpses of topics that are traditionally put off until later courses.
This book contains 30 well-developed independent projects that encourage students to explore questions across disciplinary boundaries, over 750 homework exercises, and 300 integrated reflection questions engage students in problem solving and active reading.
The accompanying website — https://www.discoveringcs.net — includes more advanced content, solutions to selected exercises, sample code and data files, and pointers for further exploration.
Preface
Acknowledgments
About the author
How to Solve It
UNDERSTAND THE PROBLEM
DESIGN AN ALGORITHM
WRITE A PROGRAM
LOOK BACK
SUMMARY AND FURTHER DISCOVERY
Visualizing Abstraction
DATA ABSTRACTION
DRAWING FLOWERS AND PLOTTING EARTHQUAKES
FUNCTIONAL ABSTRACTION
PROGRAMMING IN STYLE
A RETURN TO FUNCTIONS
SCOPE AND NAMESPACES
SUMMARY AND FURTHER DISCOVERY
Inside a Computer
COMPUTERS ARE DUMB
EVERYTHING IS BITS
COMPUTER ARITHMETIC
BINARY ARITHMETIC
THE UNIVERSAL MACHINE
Growth and Decay
ACCUMULATORS
DATA VISUALIZATION
CONDITIONAL ITERATION
CONTINUOUS MODELS
NUMERICAL ANALYSIS
SUMMING UP
FURTHER DISCOVERY
PROJECTS
RANDOM WALKS
PSEUDORANDOM NUMBER GENERATORS
SIMULATING PROBABILITY DISTRIBUTIONS
BACK TO BOOLEANS
DEFENSIVE PROGRAMMING
GUESS MY NUMBER
SUMMARY AND FURTHER DISCOVERY
PROJECTS
Text, Documents, and DNA
FIRST STEPS
TEXT DOCUMENTS
A CONCORDANCE
WORD FREQUENCY TRENDS
COMPARING TEXTS
TIME COMPLEXITY
COMPUTATIONAL GENOMICS
SUMMARY AND FURTHER DISCOVERY
PROJECTS
Data AnalysisSUMMARY STATISTICS
WRANGLING DATA
TALLYING FREQUENCIES
READING TABULAR DATA
DESIGNING EFFICIENT ALGORITHMS
LINEAR REGRESSION
DATA CLUSTERING
SUMMARY AND FURTHER DISCOVERY
PROJECTS
TABULAR DATA
THE GAME OF LIFE
DIGITAL IMAGES
SUMMARY AND FURTHER DISCOVERY
PROJECTS
Self-similarity and Recursion
FRACTALS
RECURSION AND ITERATION
THE MYTHICAL TOWER OF HANOI
RECURSIVE LINEAR SEARCH
DIVIDE AND CONQUER
LINDENMAYER SYSTEMS
9SUMMARY AND FURTHER DISCOVERY
PROJECTS
Organizing Data
BINARY SEARCH
SELECTION SORT
INSERTION SORT
EFFICIENT SORTING
TRACTABLE AND INTRACTABLE ALGORITHMS
SUMMARY AND FURTHER DISCOVERY
PROJECTS
MODELING WITH GRAPHS
SHORTEST PATHS
IT’S A SMALL WORLD
RANDOM GRAPHS
SUMMARY AND FURTHER DISCOVERY
PROJECTS
OPERATORS AND POLYMORPHISM
A FLOCKING SIMULATION
A STACK ADT
A DICTIONARY ADT
SUMMARY AND FURTHER DISCOVERY
PROJECTS
Bibliography
Appendix A ■ Python Library
Appendix B ■ Selected Exercise
Index
Biography
Jessen Havill is a Professor of Computer Science at Denison University. He has been teaching courses across the computer science curriculum for almost thirty years, and was awarded the College's highest teaching honor, the Charles A. Brickman Teaching Excellence Award, in 2013. Although his primary expertise is in the development and analysis of online algorithms, Dr. Havill has spent many years collaborating with colleagues across the curriculum to develop interdisciplinary academic opportunities for students. From 2016-2019, he became the founding Director of Denison University's interdisciplinary Data Analytics program. Dr. Havill earned his bachelor's degree from Bucknell University and his Ph.D. in computer science from The College of William and Mary.
“Havill's problem-driven approach introduces algorithmic concepts in context and motivates students with a wide range of interests and backgrounds.”
-- Janet Davis, Associate Professor and Microsoft Chair of Computer Science, Whitman College
“This book looks really great and takes exactly the approach I think should be used for a CS 1 course. I think it really fills a need in the textbook landscape.”
-- Marie desJardins, Dean of the College of Organizational, Computational, and Information Sciences, Simmons University
“Havill's broad and applications-driven introduction gives students a strong foundation as they begin to explore our field. Topics that students will study in more depth in later courses are introduced in context along a path of discovery for the fundamentals and breadth of computing. Problem solving paradigms and the structures to implement and test their results are presented as intuitive solutions to real-world problems like DNA sequencing and social network analysis, empowering the reader to understand why programming structures exist and how to use them to solve problems effectively and efficiently. Discovering Computer Science is a refreshing departure from introductory programming texts, offering students a much more sincere introduction to the breadth and complexity of this ever-growing field.”
-- James Deverick, Senior Lecturer, The College of William and Mary
“Programming is an essential skill of modern problem solving. But students can gain traction on authentic problems only when they have learned to model, decompose, approximate, and recompose real-world systems into a form suited to computing. This unique introduction to the science of computing guides students through broad and universal approaches to problem solving in a variety of contexts and their ultimate implementation as computer programs.”
-- Daniel Kaplan, DeWitt Wallace Professor, Macalester College
