The Computer Science handbook

所需积分/C币:9 2015-02-28 11:09:44 1.41MB PDF
收藏 收藏
举报

The Computer Science handbook
CONTENTS II Data Structures 32 4 Stack 35 .1 Slack 35 4.1.1 Implementation 37 4.1.2 Exercises .37 4.2 Vector 37 4.2.1 Clas 4.2.2 Resize ...38 4.2.3 Add Element 1.2.4Po 39 4.2.5 Remove 40 4.2.6 Get Element 40 4.2.7 Insert Element ,,,,41 4.2.8 Exercises 42 5 Queue 43 5.1 Queue 43 5.1.1 Implementation 44 ⑤.1,2 Exercises ,44 5.2 Linked List] 45 ⑤2, ink class 46 5.2.2 LinkedList class 47 ⑤,23Push 47 5.2.4POp 48 5.2.5Get 5.2.6 Deletel 50 5.2.7 Exercises 51 6 Sets 52 6.1 Sets 52 16.1.1 Implementation 52 ⑥12 xercises 52 ⑥6,2 hash set 53 6.2.1 Implementatio 54 6.2.2 Exercises 63 6.3 Binary Search Tree 64 16. 3. 1 Implementation 65 6.3.2 Exercises 77 ⑥4 Tree Set] 77 CONTENTS 6.4.1 Implementation 78 16.4.2 Exercises 78 7 Maps 79 79 Implementation 9 7.1.2 Exercises 80 7.2 Hash Map 80 2.1 Implemenlalic 80 7.2.2 Exercises 83 3 Tree Map 7.3.1 Implementation 83 7.3.2 Exercises 02 8 Priority Queue 93 8.0.3 Implcmcntation 8.0.4 Applications 94 8.0.5 Exercises 94 8.1 Heap 94 1.1 Implementation 96 1.2 Applications 102 8.1.3 Exercises 102 IV Graph Theory 103 9 Representation 105 9.1 Adjacency Matrix .,106 Implementation 106 9.2 Adjacency List .107 10 Tre 109 10.1 Prim's 110 10.1.1 IInplementalic 110 10.1.2 Applications 114 10. 1.3 Exercises 114 10.2 Kruskal 115 ) 2.1 Implementation 115 10.2 plications 118 10.2.3 Exercises 118 CONTENTS 4 11 Shortest Path 120 11.1 Dijkstras 120 11.1.11 mplementatlol 121 11.1.2 Applications 125 11.1. 3 Practice exercises 125 11.2 Bellman ford .,126 11.2.1 Implementation 126 11.2.2 Application 130 11.2.3 Exercises ,,,,130 11.3 Walsall 131 山.3.11 mplementation 11.3.2 Applications 133 11.3.3 Exercises ,,,,,,,,,,.,,,,134 12 Cycle Detection 135 12.0.4 Implementation 135 V Searches 137 13 Searches 138 13.1 Binary Search .,,138 .1.1 Binary Search 138 13.1.2 Implementation 140 13.1.3 Exercises 140 13.2 Ternary Search 140 13.2.1 Implementation 141 13.3 Depth First Search 148 13.3.1 Implementation 148 13.3.2 Memory ...152 13.3.3 Exercises 152 13.4 Breadth first search 152 13.4.1 Implementation 153 13.4.2 Exercises 153 13.5 Flood Fill 154 13.5.1 General solution 155 13.5.2 Bucket Fill 155 13.5.3 Exercises 159 3.6 BackTracking] ..159 13.6.I Gcncral Solutionl CONTENTS 13.6.2 List all sets ,,,,,161 13.6.3 N Queen Problem 164 13.6.4 Exercises .170 VI Dynamic Programming 171 14 Dynamic Programming 172 11.1 Dynamic Programming 172 14.1.1 Fibonacci Sequence 172 14.1.2 Coin problem ,,.,174 14.1.3 Knapsack Problem 178 14.1.4 Number of Paths ,,,,,,,,182 1.L.5巳 xercises. .183 14. 2 Advanced Dynamic Programming 183 14.2.1 Longest Common Subsequence .183 14.2.2 Zero-One Knapsack Problem 185 VII Interviews 186 15 Interviews l87 15.1 Interviews ,..,.,,,.187 15.1.1 Interview Preparation 187 15.1.2 Resume 187 15. 1.3 Before the Interview 188 15.1.4 During the Interview- Part 1: Behavioural 188 15.1.5 During the Interview- Part 2: Technical........189 15. 1.6 End Interview. 190 151 7 Practice problems 190 Chapter Getting Started 1.1 Getting started The Computer Science handbook is a handbook designed to explain algo- rithms and data structures in a way that anyone can understand. many websites(eg Wikipedia) contain lengthy and wordy explanations that are full of technical jargon. We have tried our hardest to simplify all language to make it easy to read without any math or computer science background We hope to share our knowledge with you and we ask only one thing from you. You must learn something before you leave xh. Before you get started with this handbook, it is highly recommended not meaning for learning programming basics since there are other resources better suited for that task 1.1.1 Format Each article with have multiple sections to help you understand the content Introduction The introduction section gives a brief overview of what the article is about It will usually come with a prerequisite section which will contain topics that will bc rccommcndcd to have bccn rcad bcforc the articlc 6 CHAPTER 1. GETTING STARTED Implementation The implementation scction will bc an implementation of the articlc in Java It is recommended that you try to implement things yourself first before looking at the implementation. If you truly understand the concept, the you will never have to memorize a single line of code. The code will come from your understanding of how it works Applications The applications section will be about real world applications of the concept that show why the concept is important Exercises The exercises section contains practice problems to test if you truly un derstand the concept. Many of these questions come from real interview questions Part I Fundamentals Chapter 2 Fundamentals Before we can learn about algorithms and data structures we must first learn how to analyze algorithms and data structures so we can apply them to the righ It is highly recommended that you understand syntax for Java or C+I before you continue 2.1 Runtime and memory Processing time and memory are two primary resources that computer pro grams use and it is important to analyze the limits we have. Computers are super fast at making calculations compared to humans, but humans have much more memorv than computers currently do. For example. comput ers can add two 100-digit numbers together much more quickly than any human possibly can. However, the human brain can contain much more memory than humans Brains have trillions of connections between neurons and the estimated storage capacity is about 2.5 petabytes. That is approximately 340 years of TV shows that you could watch! Computers on the other hand, have much less memory than human brains. Standard computers have around &GB of RAM and some higher end machines may have 16-32GB. Although hard disks can store terabytes of memory, we use RAM(fash memory) when analyzing computer memory because it is much faster than disk storage. As an analogy, RaM can be thought of as grabbing an object in another room whereas disk memory is driving 20 min away to get that object The neurons and connections in our brains allow us to store an immense amount of information in our brains and allows us to easily recognize pat-

...展开详情
试读 127P The Computer Science handbook
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
上传资源赚积分,得勋章
最新推荐
The Computer Science handbook 9积分/C币 立即下载
1/127
The Computer Science handbook第1页
The Computer Science handbook第2页
The Computer Science handbook第3页
The Computer Science handbook第4页
The Computer Science handbook第5页
The Computer Science handbook第6页
The Computer Science handbook第7页
The Computer Science handbook第8页
The Computer Science handbook第9页
The Computer Science handbook第10页
The Computer Science handbook第11页
The Computer Science handbook第12页
The Computer Science handbook第13页
The Computer Science handbook第14页
The Computer Science handbook第15页
The Computer Science handbook第16页
The Computer Science handbook第17页
The Computer Science handbook第18页
The Computer Science handbook第19页
The Computer Science handbook第20页

试读结束, 可继续阅读

9积分/C币 立即下载 >