Introduction

This is a book on the Computer Science book list of Oxford. It is a good book for crossing the threshold of computer science.

The book briefly introduces the some fundamental knowledges of computer science through an interesting adventure story.

I recognized many computational terms in the book that I’ve already learned in Chinese. So it helped me to know the spelling of the computational terms in English. And I also learned a lot that I’ve not learned about. I’ll keep on studying computer science and be on the way for fulfilling my dream.

I note down all the essential terms in the book to sum it up and help me for review.

Base

Computer Science: a way of thinking about problems.

A set of core concepts-approaches to solving fundamental problems,and how combine them to solve larger and more complex problem.

Algorithm: a set of specific steps for solving a problem.

Variable: a place in memory where you can store a single piece of data.

IF-ELSE statements: branch off and execute one of different blocks of code.

Loops: programming constructs for repeating a set of instructions until some terminal criterion is met.

Boolean logic: base on two values: TRUE and FALSE

Binary: a number system which each digit can take one of 0 or 1.

101=(1x2^2^)(0x2^1^)(1x2^0^)

Pseudocode: an informal understandable way of writing algorithms.

Data Structure

Arrays: like a set of bins with a fixed number of slots.

Strings: sequences(array) of characters

Swapping two values:

1.put one into temporary storage

2.the other in the memory location of first entry

3.the data from temporary storage is written to second entry.

Pointers: variables that hold addresses in the computer memory. Flexible

Linked lists: data structures that store lists of items. Use pointer to store the next and previous node.

Stacks: last-in, first-out data structure.

Queues: first in, first out data structure.

Priority queues: return the highest priority data.

Binary search trees: efficient searches by value like a tree.

Caching data: storing a copy of data in a quickly accessible location to speed up future accesses of that data.

Recursion: a problem-solving technique that builds a solution to a problem from solutions to smaller subproblems of the same type.

Binary search: algorithm for efficiently finding a target value within a sorted list.

Insertion sort: simple inefficient sorting an array of number.

Bubble sort: Swapping adjacent elements if they are out of order.

Merge sort: Break the data in half, sort each half separately using merge sort and merge together.

*Oracle’s Array: Using algorithms and data structures together to create complex programs.

Graph: is defined by a set of nodes and a set of edges that link together the nodes.

Directed/Undirected

Weighted/Unweighted

Dijkstra’s algorithm: find the shortest path from a given starting node to all other nodes in the graph.

Representations of graphs: two common data structure representing graphs:

​ adjacency matrix: One row and one column for each node.

​ adjacency list: a separate list of neighbors for each node.

Traveling salesman problem: find the shortest path through a graph that visits each node and return to the starting node. NP-hard

Depth-first search: a search algorithm that fully explores a single path before backtracking to test other paths.

Minimum Spanning Tree: the smallest set of edges that all of the nodes are connected.

Hamiltonian path: visits each node in a graph exactly one time. NP-Hard

Computational Thinking

Complex algorithms build on a core set of fundamental concepts. Mastering them and learn to combine them is the key to solving to problems.

NP-Hard: computational problems for which there are no known efficient and exact solution.

Quicksort: a recursive sorting algorithm that is similar to merge sort but faster.

Comments: additional text within code that improve the read ability.