Category Archives: Computer Science

► Nievergelt,"Algorithms and Data Structures – With Applications to Graphics and Geometry" (2011)

Nievergelt, Algorithms and Data Structures – With Applications to Graphics and Geometry” (2011)product_thumbnail.php

An Open Textbook by Jurg Nievergelt and Klaus Hinrichs

An introductory coverage of algorithms and data structures with application to graphics and geometry.”

This textbook, released under a Creative Commons Share Alike (CC BY SA) license, is presented in its original format with the academic content unchanged. It was authored by Jurg Nievergelt (ETH Zurich) and Klaus Hinrichs (Institut für Informatik) and provided by the University of Georgia’s Global Textbook Project.

Photo Credit: Renato Keshet (GFDL) commons.wikimedia.org

Buy Print Copy $39.99 (371 pages, paperback, B&W)

Free PDF Download  (5.5 Mb)

Table of Contents

Part I: Programming environments for motion, graphics, and geometry

Reducing a task to given primitives: programming motion
A robot car, its capabilities, and the task to be performed
Wall-following algorithm described informally
Algorithm specified in a high-level language
Algorithm programmed in the robot’s language
The robot’s program optimized
Graphics primitives and environments
Turtle graphics: a basic environment
QuickDraw: a graphics toolbox
A graphics frame program
Algorithm animation
Computer-driven visualization: characteristics and techniques
A gallery of algorithm snapshots

Part II: Programming concepts: beyond notation

Algorithms and programs as literature: substance and form
Programming in the large versus programming in the small
Documentation versus literature: is it meant to be read?
Pascal and its dialects: lingua franca of computer science
Divide-and-conquer and recursion
An algorithmic principle
Divide-and-conquer expressed as a diagram: merge sort
Recursively defined trees
Recursive tree traversal
Recursion versus iteration: the Tower of Hanoi
The flag of Alfanumerica: an algorithmic novel on iteration and recursion
Syntax
Syntax and semantics
Grammars and their representation: syntax diagrams and EBNF
An overly simple syntax for simple expressions
Parenthesis-free notation for arithmetic expressions
Syntax analysis
The role of syntax analysis
Syntax analysis of parenthesis-free expressions by counting
Analysis by recursive descent
Turning syntax diagrams into a parser

Part III: Objects, algorithms, programs

Truth values, the data type ‘set’, and bit acrobatics
Bits and boolean functions
Swapping and crossovers: the versatile exclusive-or
The bit sum or “population count”
Ordered sets
Sequential search
Binary search
In-place permutation
Strings
Recognizing a pattern consisting of a single string
Paths in a graph
Boolean matrix multiplication
Warshall’s algorithm
Minimum spanning tree in a graph
Integers
Operations on integers
The Euclidean algorithm
The prime number sieve of Eratosthenes
Large integers
Modular number systems: the poor man’s large integers
Random numbers
Reals
Floating-point numbers
Some dangers
Horner’s method
Bisection
Newton’s method for computing the square root
Straight lines and circles
Intersection
Clipping
Drawing digitized lines
The riddle of the braiding straight lines
Digitized circles

Part IV: Complexity of problems and algorithms

Computability and complexity
Models of computation: the ultimate RISC
Almost nothing is computable
The halting problem is undecidable
Computable, yet unknown
Multiplication of complex numbers
Complexity of matrix multiplication
The mathematics of algorithm analysis
Growth rates and orders of magnitude
Asymptotics
Summation formulas
Recurrence relations
Asymptotic performance of divide-and-conquer algorithms
Permutations
Trees
Sorting and its complexity
What is sorting? How difficult is it?
Types of sorting algorithms
Simple sorting algorithms that work in time T(n)
A lower bound O(n · log n)
Quicksort
Analysis for three cases: best, “typical”, and worst
Is it possible to sort in linear time?
Sorting networks

Part V: Data structures

What is a data structure?
Data structures old and new
The range of data structures studied
Performance criteria and measures
Abstract data types
Concepts: What and why?
Stack
First-in-first-out queue
Priority queue
Dictionary
Implicit data structures
What is an implicit data structure?
Array storage
Implementation of the fixed-length fifo queue as a circular buffer
Implementation of the fixed-length priority queue as a heap
Heapsort
List structures
Lists, memory management, pointer variables
The fifo queue implemented as a one-way list
Tree traversal
Binary search trees
Height-balanced trees
Address computation
Concepts and terminology
The special case of small key domains
The special case of perfect hashing: table contents known a priori
Conventional hash tables: collision resolution
Choice of hash function: randomization
Performance analysis
Extendible hashing
A virtual radix tree: order-preserving extendible hashing
Metric data structures
Organizing the embedding space versus organizing its contents
Radix trees, tries
Quadtrees and octtrees
Spatial data structures: objectives and constraints
The grid file
Simple geometric objects and their parameter spaces
Region queries of arbitrary shape
Evaluating region queries with a grid file
Interaction between query processing and data access

Part VI: Interaction between algorithms and data structures: case studies in geometric computation

Sample problems and algorithms
Geometry and geometric computation
Convex hull: a multitude of algorithms
The uses of convexity: basic operations on polygons
Visibility in the plane: a simple algorithm whose analysis is not
Plane-sweep: a general-purpose algorithm for two-dimensional problems illustrated using line segment intersection
The line segment intersection test
The skeleton: Turning a space dimension into a time dimension
Data structures
Updating the y-table and detecting an intersection
Sweeping across intersections
Degenerate configurations, numerical errors, robustness
The closest pair
The problem
Plane-sweep applied to the closest pair problem
Implementation
Analysis
Sweeping in three or more dimensions

►Feher,"Introduction to Digital Logic" with Laboratory Exercises (2010)

James Feher,”Introduction to Digital Logic” with Laboratory Exercises (2010)

This lab manual provides an introduction to digital logic, starting with simple gates and building up to state machines. Students should have a solid understanding of algebra as well as a rudimentary understanding of basic electricity including voltage, current, resistance, capacitance, inductance and how they relate to direct current circuits.

Buy Print Format $23.49 (99 pages, B&W)

ISBN 978-1-312-50167-6

Download Free PDF (100 pages, color, 3.2 Mb)

Extra Features

  • Peer Reviewed
    Exercises & Solutions

Table of Contents

1. Introduction

2. The transistor and inverter

The transistor
The breadboard
The inverter

3. Logic gates

History of logic chips
Logic symbols
Logical functions

4. Logic simplification

De Morgan’s laws
Karnaugh maps
Circuit design, construction and debugging

5. More logic simplification

Additional K-map groupings
Input placement on K-map
Don’t care conditions

6. Multiplexer

Background on the “mux”
Using a multiplexer to implement logical functions

7. Timers and clocks

Timing in digital circuits
555 timer
Timers
Clocks
Timing diagrams

8. Memory

Memory
SR latch
Flip-flops

9. State machines

What is a state machine?
State transition diagrams
State machine design
Debounced switches

10. More state machines

How many bits of memory does a state machine need?
What are unused states?

11. What’s next?

Appendices

Appendix A: Chip pinouts
Appendix B: Resistors and capacitors
Resistors
Capacitors
Appendix C: Lab notebook
Appendix F: Solutions
Chapter 1 review exercises
Chapter 2 review exercises
Chapter 3 review exercises
Chapter 4 review exercises
Chapter 5 review exercises
Chapter 6 review exercises
Chapter 7 review exercises
Chapter 8 review exercises
Chapter 9 review exercises

►Bonaventure, “Computer Networking : Principles, Protocols and Practice” (2011)

18957436_cover-page-001“Computer Networking : Principles, Protocols and Practice”

Complementary textbook to Saylor Academy’s “Computer Communications and Networks” (CS402)

Original textbook © October 31, 2011 by Olivier Bonaventure, is licensed under a Creative Commons Attribution (CC BY) license made possible by funding from The Saylor Foundation’s Open Textbook Challenge in order to be incorporated into Saylor’s collection of open courses available at: http://www.saylor.org.

Print $29.95 USD, 282 pages, B&W

ISBN: 978-1-365-18583-0

Free PDF  Color, 282 pages, 8.6 MB

This open textbook aims to fill the gap between the open-source implementations and the open-source network specifications by providing a detailed but pedagogical description of the key principles that guide the operation of the Internet. The book is released under a creative commons licence. Such an open-source license is motivated by two reasons. The first is that we hope that this will allow many students to use the book to learn computer networks. The second is that I hope that other teachers will reuse, adapt and improve it. Time will tell if it is possible to build a community of contributors to improve and develop the book further. As a starting point, the first release contains all the material for a one-semester first upper undergraduate or a graduate networking course.

Table of Contents
1 Preface
2 Introduction
2.1 Services and protocols
2.2 The reference models
2.3 Organisation of the book
3 The application Layer
3.1 Principles
3.2 Application-level protocols
3.3 Writing simple networked applications
4 The transport layer
4.1 Principles of a reliable transport protocol
4.2 The User Datagram Protocol
4.3 The Transmission Control Protocol
5 The network layer
5.1 Principles
5.2 Internet Protocol
5.3 Routing in IP networks
6 The datalink layer and the Local Area Networks
6.1 Principles
6.2 Medium Access Control
6.3 Datalink layer technologies
7 Glossary
8 Bibliography

►Bourgeois, “Information Systems for Business and Beyond” (2014)

product_thumbnail.phpA college-level open education resource (CC BY) thanks to the Saylor Foundation and David T. Bourgeois, Ph.D.

This text is used in Saylor’s free course “Management Information Systems”  at  https://learn.saylor.org/course/view.php?id=41

Purchase a print copy (167 pages, b&w) $22.95

Download the PDF (free, 167 pages, 4.3 Mb)

The Saylor Academy also offers several e-book  formats of this open textbook.

 

ISBN: 978-1-304-94348-4

“This book is written as an introductory text, meant for those with little or no experience with computers or information systems. While sometimes the descriptions can get a little bit technical, every effort has been made to convey the information essential to understanding a topic while not getting bogged down in detailed terminology or esoteric discussions.  . . . At the end of each chapter, there is a set of study questions and exercises (except for chapter 1, which only offers study questions). The study questions can be assigned to help focus students’ reading on the learning objectives. The exercises are meant to be a more in-depth, experiential way for students to learn chapter topics. It is recommended that you review any exercise before assigning it, adding any detail needed (such as length, due date) to complete the assignment.”

Contents
Introduction
Part 1: What Is an Information System?
Chapter 1: What Is an Information System?
Chapter 2: Hardware
Chapter 3: Software
Chapter 4: Data and Databases
Chapter 5: Networking and Communication
Chapter 6: Information Systems Security
Part 2: Information Systems for Strategic Advantage
Chapter 7: Does IT Matter?
Chapter 8: Business Processes
Chapter 9: The People in Information Systems
Chapter 10: Information Systems Development
Part 3: Information Systems Beyond the Organization
Chapter 11: Globalization and the Digital Divide
Chapter 12: The Ethical and Legal Implications of Information Systems
Chapter 13: Future Trends in Information Systems
Answers to Study Questions 150
Bibliography 162

§ North, "Data Mining for the Masses" (2012)

Download Free pdfdatamining (17Mb, 264 pages)

View original website: A Global Text Project Book
Print Version: This book is available on Amazon.com by the author: ISBN-13: 978-0615684376
This book is licensed under a Creative Commons Attribution 3.0 License

Table of Contents

SECTION ONE: Data Mining Basics

Chapter One: Introduction to Data Mining and CRISP-DM 3

Introduction 3
A Note About Tools 4
The Data Mining Process 5
Data Mining and You 11

Chapter Two: Organizational Understanding and Data Understanding 13

Context and Perspective 13
Learning Objectives 14
Purposes, Intents and Limitations of Data Mining 15
Database, Data Warehouse, Data Mart, Data Set…? 15
Types of Data 19
A Note about Privacy and Security 20
Chapter Summary 21
Review Questions 22
Exercises 22

Chapter Three: Data Preparation 25

Context and Perspective 25
Learning Objectives 25
Collation 27
Data Scrubbing 28
Hands on Exercise 29
Preparing RapidMiner, Importing Data, and 30
Handling Missing Data 30
Data Reduction 46
Handling Inconsistent Data 50
Attribute Reduction 52
Chapter Summary 54
Review Questions 55
Exercise 55

SECTION TWO: Data Mining Models and Methods 57

Chapter Four: Correlation 59

Context and Perspective 59
Learning Objectives 59
Organizational Understanding 59
Data Understanding 60
Data Preparation 60
Modeling 62
Evaluation 63
Deployment 65
Chapter Summary 67
Review Questions 68
Exercise 68

Chapter Five: Association Rules 73

Context and Perspective 73
Learning Objectives 73
Organizational Understanding 73
Data Understanding 74
Data Preparation 76
Modeling 81
Evaluation 84
Deployment 87
Chapter Summary 87
Review Questions 88
Exercise 88

Chapter Six: k-Means Clustering 91

Context and Perspective 91
Learning Objectives 91
Organizational Understanding 91
Data UnderstanDing 92
Data Preparation 92
Modeling 94
Evaluation 96
Deployment 98
Chapter Summary 101
Review Questions 101
Exercise 102

Chapter Seven: Discriminant Analysis 105

Context and Perspective 105
Learning Objectives 105
Organizational Understanding 106
Data Understanding 106
Data Preparation 109
Modeling 114
Evaluation 118
Deployment 120
Chapter Summary 121
Review Questions 122
Exercise 123

Chapter Eight: Linear Regression 127

Context and Perspective 127
Learning Objectives 127
Organizational Understanding 128
Data Understanding 128
Data Preparation 129
Modeling 131
Evaluation 132
Deployment 134
Chapter Summary 137
Review Questions 137
Exercise 138

Chapter Nine: Logistic Regression 141

Context and Perspective 141
Learning Objectives 141
Organizational Understanding 142
Data Understanding 142
Data Preparation 143
Modeling 147
Evaluation 148
Deployment 151
Chapter Summary 153
Review Questions 154
Exercise 154

Chapter Ten: Decision Trees 157

Context and Perspective 157
Learning Objectives 157
Organizational Understanding 158
Data Understanding 159
Data Preparation 161
Modeling 166
Evaluation 169
Deployment 171
Chapter Summary 172
Review Questions 172
Exercise 173

Chapter Eleven: Neural Networks 175

Context and Perspective 175
Learning Objectives 175
Organizational Understanding 175
Data Understanding 176
Data Preparation 178
Modeling 181
Evaluation 181
Deployment 184
Chapter Summary 186
Review Questions 187
Exercise 187

Chapter Twelve: Text Mining 189

Context and Perspective 189
Learning Objectives 189
Organizational Understanding 190
Data Understanding 190
Data Preparation 191
Modeling 202
Evaluation 203
Deployment 213
Chapter Summary 213
Review Questions 214
Exercise 214

SECTION THREE: Special Considerations in Data Mining

217

Chapter Thirteen: Evaluation and Deployment 219

How Far We’ve Come 219
Learning Objectives 220
Cross-Validation 221
Chapter Summary: The Value of Experience 227
Review Questions 228
Exercise 228

Chapter Fourteen: Data Mining Ethics 231

Why Data Mining Ethics? 231
Ethical Frameworks and Suggestions 233
Conclusion 235
GLOSSARY and INDEX 237
About the Author 251