Explore
For Enterprise
Join for Free
Log In

浏览
搜索
企业版
登录
免费加入

Implementation

Loading...

Computer Science: Algorithms, Theory, and Machines

普林斯顿大学

4.8（139 个评分） | 25K 名学生已注册

This course introduces the broader discipline of computer science to people having basic familiarity with Java programming. It covers the second half of our book Computer Science: An Interdisciplinary Approach (the first half is covered in our Coursera course Computer Science: Programming with a Purpose, to be released in the fall of 2018). Our intent is to demystify computation and to build awareness about the substantial intellectual underpinnings and rich history of the field of computer science. First, we introduce classic algorithms along with scientific techniques for evaluating performance, in the context of modern applications. Next, we introduce classic theoretical models that allow us to address fundamental questions about computation, such as computability, universality, and intractability. We conclude with machine architecture (including machine-language programming and its relationship to coding in Java) and logic design (including a full CPU design built from the ground up). The course emphasizes the relationships between applications programming, the theory of computation, real computers, and the field's history and evolution, including the nature of the contributions of Boole, Shannon, Turing, von Neumann, and others. All the features of this course are available for free. No certificate will be offered upon completion.

查看授课大纲

审阅

4.8（139 个评分）

5 stars
114 ratings
4 stars
20 ratings
3 stars
5 ratings

AN

Dec 05, 2018

Excellent clarity and pace with real-life problems and challenges to really understand the concepts and their motivation.

EG

May 12, 2018

Very pedagogical and enjoyable introduction to CS. Another great Princeton University Coursera course.

从本节课中

SYMBOL TABLES

The symbol table abstraction is one of the most important and useful programmer's tools, s we illustrate with several examples in this lecture. Extending the scientific approach of the previous two lectures, we introduce and study binary search trees, a classic data structure that supports efficient implementations of this abstraction.

APIs and clients23:41

A design challenge6:36

Binary search trees13:24

Implementation4:33

教学方

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Kevin Wayne
Phillip Y. Goldman '86 Senior Lecturer

脚本

We'll follow through the standard method that we do for implementing an abstract data type looking at the instance variables, and constructor, and then the client code, and methods. So, let's just review what it is that we want to do. So, we have an idealized model of an associated storage mechanism. And what we want is an ADT that allows us to write Java programs that use and manipulate symbol tables. And here's the API for that ADT that we articulated early on. And then we have these performance specs and we don't consider an implementation to be a symbol table unless it meets these specs. The order of growth of the running time should be logarithmic at worst. The memory usage should be linear in the size of the collection if it's not empty. And there shouldn't be any limits within the code on the collection size. So, that's the challenge we are going to embark on right now. Okay. So, we've made the data structure choice that we're going to use BST. So, what do the instance variables in the constructor look like? Well, there's only one instance variable that's the root. We do need this private class that we're going to use to build up the binary search tree and it's got those fields key in value, and then references to the left, and right subtree, and then a small constructor that will initialize the key in value. And that's it. That's one instance variable and then the private class that describes the data type that is a node. Okay. What about the test client? We already looked at that. That's the frequency counter test client that we looked at before that tries out all our code. And so, we expect it to do the frequency count and actually print out the keys in sorted order. The example we did before we sorted them again based on the frequency count, but this is the behavior that we expect from our symbol table. And then there's the methods. So, this is empty as the binary search tree empty. Well if the root's null it's empty. The put method that's the code that we looked at when discussing the BST data structure and we'll see it again in the next slide, and the same with the get method contains we just get the key and see if it's associated with null. That's our convention allows us to implement contains with that one liner. And then iterable we talked about that one as well, and we'll summarize it again in the next slide. So, those are the four components of the data type implementation. And here's the complete code, again it fits on the slide maybe a slightly smaller font than others, but not too bad. So, that's the instance variable, the nested class, the methods. So, those are the public methods that are in the API and then each one of those is supported by a recursive helper method that are private methods that are not visible to the clients and then we have our test client. So, that's a complete implementation of the symbol table using binary search tree. And this is just a quick trace to see what it does for example, so we have it and then was comes and not even showing the frequencies just focusing on the keys. And the arrives to the left of was best is smaller than it, so it gets added on the left of it. And then of is bigger than it, less than was, less than the and so forth. So, you can see the binary search tree getting built up by new nodes getting added at the bottom. Next, we have to look at the analysis and try to understand this performance. And do we meet the performance specifications that we've set?

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera

关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版
面向校园

社区

学生
合作伙伴
开发者
Beta 测试人员
专业译员
博客
技术博客

更多

条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司

随时随地学习

关注我们

© 2019 Coursera Inc.保留所有权利。