# Computational Fairy Tales Notes

# 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.