Summary computer science

Overview of
Computer Science




This textbook consists of notes for the CSci 1001 Overview of Computer Science
class at the University of Minnesota-Twin Cities. More information about that class
and these notes are in the opening chapter. The original version of these notes
was used in the Spring 2014 offering of that class. This current version, Version
1.2, is a small update, containing some minor clarifications and corrections, as well
as the addition of a chapter of example programming problems.


This work is licensed under a Creative Commons Attribution-ShareAlike 4.0
International License. Others are free to copy, reuse, etc. this work under the license terms
at http://creativecommons.org/licenses/by-sa/4.0/

,Contents

1 What is This Course About? 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 What This Course Isn’t . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 What Are These Note About? . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 CSci 1001 and Liberal Education ...................... 5
1.4.1 Why Liberal Education? . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.2 Mathematical Thinking . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.3 Technology and Society . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.4 How These Requirements Will Appear in the Coursework . . . . . . 9
1.5 Course Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Tips For Doing Well ............................. 11
1.7 Additional Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Algorithms 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Introductory Problem ......................... 13
2.1.2 Introductory Comments . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.4 Skills . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.5 Algorithms and the Liberal Education Requirements . . . . . . . . 15
2.2 Specifying Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Algorithm Characteristics . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Pseudocode Characteristics ...................... 18
2.3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Sequence, Selection, Repetition . . . . . . . . . . . . . . . . . . . . 19
2.3.2 Indentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Other Basic Pseudocode Commands ................. 20
2.4 Additional Comments on Pseudocode . . . . . . . . . . . . . . . . . . . . 21
2.4.1 Different Ways of Expressing an Operation . . . . . . . . . . . . . . 21
2.4.2 What is a Variable? . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.3 Lists, etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

,2.4.4 Variable Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

i

, ii CONTENTS



.
2.4.5 Pseudocode Summary ......................... 24
2.5 Some Practice . . . . . . . ......................... 24
2.5.1 Writing Pseudocode Fragments . . . . . . . . . . . . . . . . . . . . 24
2.5.2 Reading an Algorithm ......................... 25
2.5.3 Common Mistakes . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.6 Two Examples For Class . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.7 Writing Algorithms: How to Begin? . . . . . . . . . . . . . . . . . . . . . 27
2.8 Questions to Think About For Class .................... 29
2.9 Additional Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.10 Problem Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.10.1 Introductory Problem ......................... 30
2.10.2 Additional Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3 Data Representation 35
3.1 Introductory Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.1 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.2 Data Representation and Mathematics . . . . . . . . . . . . . . . . 37
3.2.3 Data Representation and Society and Technology . . . . . . . . . . 37
3.3 Representation Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.2 Why Binary? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.3 Review of the Decimal Number System . . . . . . . . . . . . . . . . 39
3.3.4 Unsigned Binary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.5 Decimal to Binary Conversion . . . . . . . . . . . . . . . . . . . . . 40
3.3.6 Addition of Binary Numbers . . . . . . . . . . . . . . . . . . . . . . 42
3.3.7 Subtraction of Binary Numbers . . . . . . . . . . . . . . . . . . . . 43
3.4 Other Representations Related to Binary . . . . . . . . . . . . . . . . . . 43
3.4.1 Hexadecimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.2 Sign/Magnitude Notation . . . . . . . . . . . . . . . . . . . . . . . 46
3.5 Two’s Complement Representation . . . . . . . . . . . . . . . . . . . . . 48
3.5.1 Two’s Complement Representation Basics . . . . . . . . . . . . . . 48
3.5.2 Addition and Subtraction . . . . . . . . . . . . . . . . . . . . . . . 49