Fichas
Program Analysis Theory Questions
Fichas del conjunto (24)
- 1What is a problem?A specification of a relationship between inputs and outputs. Usually, there is one valid output for a given input (mapping).
- 2What is an algorithm?An algorithm is a specification as to how to tackle a problem. Informal pseudo code is used in algorithms and they can be abstract.
- 3What are the differences between a problem and an algorithm?Problems are not about doing something in a particular way. Algorithms are.
Programs implement algorithms - 4What is an asymptotic analysis?An indication on how running time increases as input size grows.
A rough classification of the rate of growth - 5What are the three asymptotic bounds?Upper bound O(.)
Lower bound Ω(.)
Tight bound Θ(.) - 6Draw a graph with an example of an asymptotic upper bound.
- 7Write down the relative growth rates starting from the faster one.O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < . . . < O(2n)
- 8Draw a graph with an example of an asymptotic lower bound.
- 9What are the two alternative ways to implement a priority queue?Heap implementation
Unsorted list implementation - 10How do we add an element to a binary heap?Insert new element to end of sequence
Repeatedly swap with parent if higher priority
This is operation is called heapify - 11How do we remove an element from a binary heap?The highest priority element is at the front of the sequence
Need to restore heap property
Insert last element in sequence at front and put down tree as
required - 12What is a directed acyclic graph?A directed graph with no directed cycles
- 13What is a tree?A tree is a special kind of graph that is connected and there are no cycles. It has n nodes and n − 1 edges.
- 14What are the two alternative data structures we can use to store a graph?Adjacency matrix
Adjacency list - 15What data structure do we use for BFS?A queue
- 16What data structure do we use for DFS?A stack
- 17What data structure do we use for the topological sorting problem?A stack
- 18What is a topological sorting?A topological sorting of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
- 19What are greedy algorithms?Greedy algorithms are algorithms that make a series of choices and a solution is built up as these choices are made. The locally best option is made at each.
- 20What is a spanning tree?A spanning tree is a subgraph that includes all of the vertices of the original graph that is a tree
- 21What are two possible implementation of the minimum spanning tree problem?Kruskal's Algorithm
Jarnik's Algorithm - 22When are recursive algorithms suitable?They are suitable when a problem instance can be broken into smaller instances of the same problem.
- 23What is dynamic programming?Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems
- 24In the network flow problem, what is the path's bottleneck edge?The edge of the path with the lowest capacity. The flow of network can be augmented by the capacity of the bottleneck edge.
Información
- Descripción
- Fichas sobre Program Analysis Theory Questions, creado por Alexandros Parpas el 09/01/2015.
- Creado por
- Alexandros Parpas
- Visitas
- 11
- Valoración