Basic
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.
- Pseudocode: an informal understandable way of writing algorithms.
Data Structure
Arrays: like a set of bins (a box) 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 date. 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.