CS Theory Flashcards
What is recursion and give an example using javascript?
“Reading:
https://medium.com/backticks-tildes/iteration-vs-recursion-c2017a483890
Recursion: when a function calls itself
The concept of Recursion and Iteration is to execute a set of instructions repeatedly. The difference between them is that recursion is simply a method call in which the method being called is the same as the one making the call while iteration is when a loop is repeatedly executed until a certain condition is met. Under the hood, both recursion and iteration depends on a condition so as to know when to stop but recursion is simply a process, always applied to a function.
An example of recursion is shown below:
Example:
function factorial(x) {
if (x < 0) return;
if (x === 0) return 1;
return x * factorial(x - 1);
}
factorial(3);
// 6
and here’s an example of iteration:
Key Differences between Recursion and Iteration
A conditional statement decides the termination of recursion while a control variable’s value decide the termination of the iteration statement (except in the case of a while loop).
Infinite recursion can lead to system crash whereas, infinite iteration consumes CPU cycles.
Recursion repeatedly invokes the mechanism, and consequently the overhead, of method calls. This can be expensive in both processor time and memory space while iteration doesn’t.
Recursion makes code smaller while iteration makes it longer.
These are some of the key differences between iteration and recursion. I hope this has been explanatory.”
What are types?
“https://github.com/getify/You-Dont-Know-JS/blob/master/types%20%26%20grammar/ch1.md
JavaScript has seven built-in types: null, undefined, boolean, number, string, object, symbol. They can be identified by the typeof operator.
Variables don’t have types, but the values in them do. These types define intrinsic behavior of the values.”
What are data structures?
"Data structures are the way we are able to store and retrieve data. Examples: arrays and objects. Data structures handle four main functions for us: Inputting information Processing information Maintaining information Retrieving information "
OO or class oriented programming stresses that data intrinsically has associated behavior (of course, different depending on the type and nature of the data!) that operates on it, so proper design is to package up (aka, encapsulate) the data and the behavior together. This is sometimes called “data structures” in formal computer science.
What is an algorithm?
An algorithm is a step by step list of instructions telling the computer exactly what you want it to do. Within these instructions, the programmer tells the computer how to execute those actions.
“An algorithm is a self-contained series of instructions to perform a function.
In other words, an algorithm is a means of describing a way to solve a problem so that it can be solved repeatedly, by humans or machines. Computer scientists compare the efficiency of algorithms through the concept of ““Algorithmic Complexity”” or ““Big O”” notation.
For example:
A cooking recipe is a simple algorithm for humans
A sorting algorithm is often used in computer programming to explain a machine how to sort data
Common Algorithms are Pathfinding Algorithms such as the Traveling Salemen Problem, Tree Traversal Algorithms, etc..
There are also Machine Learning Algorithms such as Linear Regression, Logistic Regression, Decision Tree, Random Forest, Support Vector Machine, Recurrent Neural Network (RNN), Long Short Term Memory (LSTM) Neural Network, Convolutional Neural Network (CNN), Deep Convolutional Neural Network etc.”
What is scope / lexical scope in javascript?
“Scope determines where variables, functions, and objects are accessible in your code during runtime. This means the scope of a variable is controlled by the location of the variable declaration - the two locations are global and local.
Lexical Scope defines how variable names are resolved in nested functions: inner functions contain the scope of parent functions even if the parent function has returned.”
“A relatively basic concept in JavaScript is that each declared function creates its own scope. Lexical scope is the scope model used by the JavaScript language, which differs to some other languages which use dynamic scope. Lexical scope is the scope defined at lexing time.
This digs into the mechanics of how JavaScript engine works. Despite commonly being referred to as an interpreted language, JavaScript compiles code immediately before executing it. For example the statement:var a = 2;is split into two separate steps at lexing time: • var aThis declares the variable in the scope, before code execution. • a = 2This assigns the value 2 to the variable a, if it is found in the available scope.
http://astronautweb.co/javascript-lexical-scope/
“
What is polymorphism?
Polymorphism is the ability to write a function that handles many data-types — it is a fundamental form of abstraction and happens through inheritance in Object-Oriented Programming. Polymorphism allows the ability to create a variable, a function, or an object that takes on more than one form.
“In programming languages and type theory, polymorphism is the provision of a single interface to entities of different types[1] or the use of a single symbol to represent multiple different types.
The most commonly recognised major classes of polymorphism are:
• Ad hoc polymorphism: defines a common interface for an arbitrary set of individually specified types.
• Parametric polymorphism: when one or more types are not specified by name but by abstract symbols that can represent any type.
• Subtyping(also calledsubtype polymorphismorinclusion polymorphism): when a name denotes instances of many different classes related by some common superclass.[3]
https://en.wikipedia.org/wiki/Polymorphism_(computer_science)
The fancy word for the ability of multiple object types to implement the same functionality is polymorphism.
https://developer.mozilla.org/en-US/docs/Learn/JavaScript/Objects/Object-oriented_JS”
What is encapsulation?
“Is information hiding.
It’s about hiding as much as possible of the object’s internal parts and exposing aminimal information about an object to the public.
The easiest way to create encapsulation in JavaScript is by using closures. A closure in this instance can be created as a function with private state
“
“Inobject oriented programming languages,encapsulationis used to refer to one of two related but distinct notions, and sometimes to the combination thereof:
• A language mechanism for restricting direct access to some of theobject’s components.
• A language construct that facilitates the bundling of data with themethods(or other functions) operating on that data.
Some programming language researchers and academics use the first meaning alone or in combination with the second as a distinguishing feature ofobject-oriented programming, while some programming languages that providelexical closuresview encapsulation as a feature of the languageorthogonalto object orientation.
The second definition is motivated by the fact that in many OOP languages, components are not hidden automatically and this can be overridden; thus,information hidingis defined as a separate notion by those who prefer the second definition.
The features of encapsulation are supported using classes in most object-oriented programming languages, although other alternatives also exist.
https://en.wikipedia.org/wiki/Encapsulation_(computer_programming)
“
What is a Linked List
“stores data with nodes that point to other nodes.
Nodes, at its most basic it has one datum and one reference (another node).
A linked list chains nodes together by pointing one node’s reference towards another node.”
“A Linked List, that as its name says, is a linked list of nodes that are represents by a head that is the first node in the list and the tail that is the last one. Each node has a reference/pointer to the previous and the next node.
The linked list data structure have two types, the first one is single linked list, the nodes of this type have a pointer to the next one but not for their previous node.
https://hackernoon.com/the-little-guide-of-linked-list-in-javascript-9daf89b63b54”
What is a Doubly Linked List?
“A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
https://medium.com/dev-blogs/ds-with-js-linked-lists-ii-3b387596e27e
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field. The beginning and ending nodes’ previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.
https://en.wikipedia.org/wiki/Doubly_linked_list”
What is a Queue?
“FIFO (First In First Out)
Similar to a stack, queue is a linear data structure where it obeys the FIFO (First In First Out) mechanism. You can think of a queue as a single line of people at a fast food restaurants. The basic methods for a stack like push, pop, and peek.
https://medium.com/javascript-in-plain-english/javascript-what-are-stack-and-queue-79df7af5a566”
What is a Stack?
“stack of pancakes
LIFO (Last In First Out)
What is a Stack?
A stack is a type of data structure that is linear where order is conserved. For many people, stack is known to have a LIFO (Last In First Out) mechanism. Let’s take a look at an example of a stack in real life: stack of plates.
https://medium.com/javascript-in-plain-english/javascript-what-are-stack-and-queue-79df7af5a566”
“A stack is a data structure + a container of objects that are added and removed according to the last-in first-out (LIFO) principle - elements can be added and removed from the stack only at the top.
A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.
A stack is a recursive data structure.
“
What is a Hash Table
Hashtable is a data structure that associates keys with values;
“Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects.
https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/
In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions must be accommodated in some way.
https://en.wikipedia.org/wiki/Hash_table
”
What is a Heap?
” A heap is a tree-based data structure which satisfies the heap property:
Max heap: if the parent node is greater than the child node is called
Min Heap: if the parent node is less than the child node is called
The common heap is: binary heap, which is a binary tree”
“A Heap is a runtime concept in JavaScript. Objects are allocated in a heap which is just a name to denote a large mostly unstructured region of memory.
There are three runtime concepts in JS named: stack, heap, and queu. JavaScript has a concurrency model based on an ““event loop””. [Diagram to the right]
https://developer.mozilla.org/en-US/docs/Web/JavaScript/EventLoop#Heap
”
What is a Trie?
“It is a kind of search tree—an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.
Unlike the binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.
“
“Tries is a tree that stores strings. Maximum number of children of a node is equal to size of alphabet. Trie supports search, insert and delete operations in O(L) time where L is length of key.
https: //www.geeksforgeeks.org/advantages-trie-data-structure/
https: //www.geeksforgeeks.org/trie-insert-and-search/”
What is a Tree?
“a tree is a data structure that simulates hierarchical data with nodes. Each node of a tree holds its own data and pointers to other nodes.
Example: creating an HTML document and interacting with the DOM is an example of a working with a tree
“
“A tree is an important data structure of computer science which is useful for storing hierarchically ordered data. Unlike stack, queue and linear lists (arrays and linked lists) which are used to store linear data like marks of students in a class, list of tasks to be done, etc, trees are used to store non-linear data structures in a hierarchical order. A family tree is the most common example of hierarchical data. Directory structure, corporate structure, etc are also common examples of hierarchical data. The pictures given below show examples of a linear data structure as well as trees.
https://www.codesdope.com/blog/article/trees-in-computer-science/ “
