The Computer Science Handbook

The Computer Science Handbook

By: Michael Young

The Computer Science Handbook

Michael Young May 8, 2015

i

Thanks to: Dr. Yuli Ye, for teaching me Gord Ridout, for encouraging me to make this book

Contents

1 Getting Started

9

1.1 Getting Started . . . . . . . . . . . . . . . . . . . 9

1.1.1 Format . . . . . . . . . . . . . . . . . . . . 10

2 Interviews

11

2.1 Interviews . . . . . . . . . . . . . . . . . . . . . . 11

2.1.1 Interview Preparation . . . . . . . . . . . . 11

2.1.2 Resume . . . . . . . . . . . . . . . . . . . . 12

2.1.3 Before the Interview . . . . . . . . . . . . . 12

2.1.4 During the Interview - Part 1: Behavioural 13

2.1.5 During the Interview - Part 2: Technical . . 14

2.1.6 End Interview . . . . . . . . . . . . . . . . . 15

I Fundamentals

17

3 Fundamentals

18

3.1 Runtime and Memory . . . . . . . . . . . . . . . 18

3.1.1 Limits . . . . . . . . . . . . . . . . . . . . . 19

3.1.2 Big O Notation . . . . . . . . . . . . . . . . 19

3.1.3 Runtime and Memory Analysis . . . . . . . 21

3.1.4 Exercises . . . . . . . . . . . . . . . . . . . 26

1

CONTENTS

2

II Recursion

27

4 Recursion

28

4.1 Recursion . . . . . . . . . . . . . . . . . . . . . . 28

4.1.1 Factorial . . . . . . . . . . . . . . . . . . . . 29

4.1.2 Sum of digits of a string . . . . . . . . . . . 31

4.1.3 Count . . . . . . . . . . . . . . . . . . . . . 33

4.1.4 Calculate Exponential . . . . . . . . . . . . 35

4.1.5 Exercises . . . . . . . . . . . . . . . . . . . 37

4.2 Advanced Recursion . . . . . . . . . . . . . . . . 37

4.2.1 Number of paths . . . . . . . . . . . . . . . 37

4.2.2 Towers of Hanoi . . . . . . . . . . . . . . . 40

4.2.3 Permutations . . . . . . . . . . . . . . . . . 47

4.2.4 Exercises . . . . . . . . . . . . . . . . . . . 51

III Data Structures

52

5 Stack

55

5.1 Stack . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.2 Vector . . . . . . . . . . . . . . . . . . . . . . . . 57

5.2.1 Class . . . . . . . . . . . . . . . . . . . . . . 57

5.2.2 Resize . . . . . . . . . . . . . . . . . . . . . 58

5.2.3 Add Element . . . . . . . . . . . . . . . . . 58

5.2.4 Pop . . . . . . . . . . . . . . . . . . . . . . 59

5.2.5 Remove . . . . . . . . . . . . . . . . . . . . 60

5.2.6 Get Element . . . . . . . . . . . . . . . . . 60

5.2.7 Insert Element . . . . . . . . . . . . . . . . 61

5.2.8 Exercises . . . . . . . . . . . . . . . . . . . 62

5.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . 63

6 Queue

64

6.1 Queue . . . . . . . . . . . . . . . . . . . . . . . . 64

6.2 Linked List . . . . . . . . . . . . . . . . . . . . . 66

6.2.1 Link Class . . . . . . . . . . . . . . . . . . . 67

CONTENTS

3

6.2.2 LinkedList Class . . . . . . . . . . . . . . . 67 6.2.3 Push . . . . . . . . . . . . . . . . . . . . . . 68 6.2.4 Pop . . . . . . . . . . . . . . . . . . . . . . 69 6.2.5 Get . . . . . . . . . . . . . . . . . . . . . . 70 6.2.6 Delete . . . . . . . . . . . . . . . . . . . . . 72 6.2.7 Exercises . . . . . . . . . . . . . . . . . . . 72 6.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . 74

7 Sets

75

7.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . 75

7.2 Hash Set . . . . . . . . . . . . . . . . . . . . . . . 76

7.2.1 Class . . . . . . . . . . . . . . . . . . . . . . 77

7.2.2 Hash code . . . . . . . . . . . . . . . . . . . 78

7.2.3 Resize . . . . . . . . . . . . . . . . . . . . . 79

7.2.4 Insert . . . . . . . . . . . . . . . . . . . . . 80

7.2.5 Contains . . . . . . . . . . . . . . . . . . . . 82

7.2.6 Remove . . . . . . . . . . . . . . . . . . . . 83

7.2.7 Exercises . . . . . . . . . . . . . . . . . . . 86

7.3 Tree Set . . . . . . . . . . . . . . . . . . . . . . . 86

7.4 Binary Search Tree . . . . . . . . . . . . . . . . . 87

7.4.1 Class . . . . . . . . . . . . . . . . . . . . . . 88

7.4.2 Insert . . . . . . . . . . . . . . . . . . . . . 90

7.4.3 Contains . . . . . . . . . . . . . . . . . . . . 93

7.4.4 Remove . . . . . . . . . . . . . . . . . . . . 95

7.4.5 Print Tree . . . . . . . . . . . . . . . . . . . 102

7.4.6 Exercises . . . . . . . . . . . . . . . . . . . 103

7.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . 103

8 Maps

104

8.1 Maps . . . . . . . . . . . . . . . . . . . . . . . . . 104

8.2 Hash Map . . . . . . . . . . . . . . . . . . . . . . 105

8.2.1 Class . . . . . . . . . . . . . . . . . . . . . . 105

8.2.2 Resize . . . . . . . . . . . . . . . . . . . . . 106

8.2.3 Put . . . . . . . . . . . . . . . . . . . . . . 107

CONTENTS

4

8.2.4 Get . . . . . . . . . . . . . . . . . . . . . . 108 8.2.5 Remove . . . . . . . . . . . . . . . . . . . . 109 8.2.6 Exercises . . . . . . . . . . . . . . . . . . . 109 8.3 Tree Map . . . . . . . . . . . . . . . . . . . . . . 109 8.3.1 Exercise . . . . . . . . . . . . . . . . . . . . 110 8.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . 111

9 Priority Queue

112

9.1 Priority Queue . . . . . . . . . . . . . . . . . . . 112

9.2 Heap . . . . . . . . . . . . . . . . . . . . . . . . . 113

9.2.1 Class . . . . . . . . . . . . . . . . . . . . . . 115

9.2.2 Resize . . . . . . . . . . . . . . . . . . . . . 115

9.2.3 Swap . . . . . . . . . . . . . . . . . . . . . . 115

9.2.4 Push . . . . . . . . . . . . . . . . . . . . . . 116

9.2.5 Pop . . . . . . . . . . . . . . . . . . . . . . 118

9.2.6 Heapify . . . . . . . . . . . . . . . . . . . . 122

9.2.7 Exercises . . . . . . . . . . . . . . . . . . . 122

9.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . 122

IV Sorting

124

10 Slow Sorts

126

10.1 Bubble Sort . . . . . . . . . . . . . . . . . . . . . 126

10.1.1 Implementation . . . . . . . . . . . . . . . . 127

10.2 Selection Sort . . . . . . . . . . . . . . . . . . . . 128

10.2.1 Implementation . . . . . . . . . . . . . . . . 128

10.3 Insertion Sort . . . . . . . . . . . . . . . . . . . . 129

10.3.1 Implementation . . . . . . . . . . . . . . . . 129

11 Fast Sorts

132

11.1 Heap Sort . . . . . . . . . . . . . . . . . . . . . . 132

11.1.1 Implementation . . . . . . . . . . . . . . . . 133

11.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . 133

11.2.1 Implementation . . . . . . . . . . . . . . . . 134

CONTENTS

5

11.2.2 Exercises . . . . . . . . . . . . . . . . . . . 137 11.3 Quick Sort . . . . . . . . . . . . . . . . . . . . . . 137

11.3.1 Implementation . . . . . . . . . . . . . . . . 138 11.3.2 Exercises . . . . . . . . . . . . . . . . . . . 140

12 Super Slow Sorts

141

12.1 Bozo Sort . . . . . . . . . . . . . . . . . . . . . . 141

12.1.1 Implementation . . . . . . . . . . . . . . . . 141

12.2 Permutation Sort . . . . . . . . . . . . . . . . . . 142

12.2.1 Implementation . . . . . . . . . . . . . . . . 143

12.3 Miracle Sort . . . . . . . . . . . . . . . . . . . . . 143

12.3.1 Implementation . . . . . . . . . . . . . . . . 143

13 Exercises

145

V Graph Theory

146

14 Graph Representations

149

14.1 Adjacency Matrix . . . . . . . . . . . . . . . . . . 149

14.1.1 Implementation . . . . . . . . . . . . . . . . 150

14.2 Adjacency List . . . . . . . . . . . . . . . . . . . 151

14.2.1 Implementation . . . . . . . . . . . . . . . . 152

15 Shortest Path

153

15.1 Dijkstra's . . . . . . . . . . . . . . . . . . . . . . 154

15.1.1 Implementation . . . . . . . . . . . . . . . . 155

15.1.2 Practice Exercises . . . . . . . . . . . . . . 160

15.2 Bellman Ford . . . . . . . . . . . . . . . . . . . . 160

15.2.1 Implementation . . . . . . . . . . . . . . . . 160

15.2.2 Exercises . . . . . . . . . . . . . . . . . . . 165

15.3 Floyd Warsahll . . . . . . . . . . . . . . . . . . . 166

15.3.1 Implementation . . . . . . . . . . . . . . . . 166

15.3.2 Exercises . . . . . . . . . . . . . . . . . . . 169

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download